Примеры доказательств с использованием метода МИ

Пусть задана последовательность чисел Фибоначчи

0,1,1,2,3,5,8,13,21,34,55,89…F(n)(каждое следующее число равно сумме двух предыдущих)

Обозначим - золотое сечение.

Доказать что F_n≤Ф^n-1 (*)

Доказательство: если n=1, то F_n=1

F₁=Ф^n-1=Ф⁰=1 соотношение (*) выполняется для n=1.Тем самым выполнен пункт а) в построении доказательства по методу МИ.

Если n=2 F₂=1<1,6(округленное)<Ф¹=Ф^2-1

Для n=2 соотношение (*) выполняется

Если P(1),P(2),…P(n) справедливы и n>1, то справедливы в частности P(n-1) и P(n). Получим P(n+1):

F_n-1 ≤Ф^n-2, F_n ≤Ф^n-1

F_n+1 = F_n-1 +F_n≤Ф^n-2+Ф^n-1= Ф^n-2(1+Ф¹) (**)

1+Ф=?.Докажем что 1+Ф=Ф² (***)

Используя (***) и (**) получим F(n+1)≤Ф^n-2*Ф²=Фⁿ, т.е. F_n+1≤Фⁿ.Тем самым мы выполнили пункт б).В данном доказательстве мы выполнили пункт б) двумя разными способами:

1.Непосредственно доказали P(n+1) при n=1,т.е. доказали P(2)

2.Использовали предположение индукции при n>1 здесь мы были вынуждены так поступить, т.к. при n=1 ссылка на P(0)=P(n-1) была бы не законной, т.к. мы начинали доказательство с n=1, а не с n=0.