пользователей: 21252
предметов: 10461
вопросов: 177855
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


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

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

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

Обозначим Ф=(1+sqrt5)/2 - золотое сечение.

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

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

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

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

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

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

Fn-1 ≤Ф^(n-2) , Fn ≤Ф^(n-1)

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

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

Ф^2 = ((1+sqrt5)/2)^2 = (1/2)^2 + 2*1/2*sqrt5/2 + (sqrt5/2)^2 = 1/4 + sqrt5/2 + 5/4 = 6/4 + sqrt5/2 = 1 + Ф => 1+Ф = Ф^2 (***)

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

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

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

 

 


20.06.2014; 21:38
хиты: 77
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь