Задача на числа Фибоначчи

Perce

Последовательность чисел Фибоначчи F(n) = F(n-1) + F(n-2 F(1)=1, F(2)=1.
Доказать, что F(n+k) = F(n+1)F(k) + F(n)F(k-1)
Интересует наиболее короткие, простые и красивые решения

griz_a

индукция?

Perce

Слишком банально. Хотя не пробовал. Может и получится "красиво"

griz_a

Нет. Получится просто.

mcfly67

F(n+2) = F(n+1) + F(n)
умножаем обе части равенства на F(k-1) и пользуемся F(k-1) + F(k-2) = F(k)
получаем F(n+1)F(k) + F(n)F(k-1) = F(n+2)F(k-1) + F(n+1)F(k-2)
затем еще раз так поступаем (только для тождества F(n+3) = F(n+2) + F(n+1) ) итп пока не получим F(n+k-1)F(2) + F(n+k-2)F(1) (= F(n+k.
P.S. Тьфу, написал индукцию в чистом виде Ступил, сорри
P.P.S. Хотя вроде и не индукция - просто возимся с определением чисел Фибоначчи

ARTi

в такое время, в такое утро... ты ботаешь?!

NHGKU2

F(k-1) + F(k-2) = F(k+1)
?

mcfly67

подправил, опечатка

griz_a

вот это и т.п. и есть индукция =) слегка завуалированная - ты ее применяешь в обратную сторону

mcfly67

ну я не спорю
просто всегда не нравилась эта занудность "база-предположение-доказательство", а тут вроде так завуалированно и ненапряжно)

z731a

k=2: F(n+2)=F(n+1)F(2)+F(n)F(1)

k=m+1: F(n+m+1)=F(n+m)+F(n+m-1)=F(n+1)F(m)+F(n)F(m-1)+F(n+1)F(m-1)+F(n)F(m-2)=F(n+1F(m)+F(m-1+F(nF(m-1)+F(m-2=F(n+1)F(m+1)+F(n)F(m)

ARTi

по-моему, этот факт - простое следствие из матричного представления

Perce

Ладно, тогда уж расскажу как появилась эта задачка.
Если воспользоваться тем фактом, что








(11)n=(F(n+1)F(n))
10 F(n)F(n-1)


То легко получить, что








(F(n+k+1)F(n+k))=(F(n+1)F(n))(F(k+1)F(k))
F(n+k)F(n+k-1)F(n)F(n-1)F(k)F(k-1)


Откуда F(n+k) = F(n+1)F(k) + F(n)F(k-1) = F(n)F(k+1) + F(n-1)F(k)

ARTi

ну вот, а я что говорил
ты зеленую книжку слишком много читал

Perce

Этот факт я кстати почерпнул не из зеленой книжки. А из синей

DarkDimazzz

Если очень не хочется использовать индукцию, можно воспользоваться явным выражением для чисел Фибоначчи. При этом несложно доказать более общее утверждение, которое по индукции уже доказать заметно сложнее:
F(m)F(n+k) = F(n+m)F(k) - (-1)^m F(n)F(k-m)

z731a

а в чем тогда тайный смысл решать эту задачу другим способом?

Perce

В том, что из определения последовательности сразу не следует ее матричное представление

griz_a

в том, чтобы сослаться на индукцию ее раньше, так чтобы никто совсем не заметил =)
Оставить комментарий
Имя или ник:
Комментарий: