Автор Анна Виняр задал вопрос в разделе Домашние задания
Последовательность Фибоначчи и получил лучший ответ
Ответ от Excelsior[гуру]
Ну вот вам простенькое доказательство, которое не использует страшных слов типа "характеристический многочлен" и т. п. Используется только решение квадратных уравнений и метод математической индукции, но это вроде как в школе проходят. Обозначим n-ый член последовательности Фибоначчи через F(n). Кроме того, введем обозначения R и T для следующих чисел:
R = (1 + sqrt(5))/2,
T = (1 - sqrt(5))/2.
(sqrt(5) - это квадратный корень из 5.) Кстати, число R - это золотое сечение. Легко проверить, что числа R и T являются корнями квадратного уравнения x^2 = х + 1. Докажем теперь по индукции следующее: если х является корнем уравнения x^2 = х + 1 (то есть или числом R, или числом Т) , то х удовлетворяет также уравнению
x^n = F(n) * x + F(n - 1)
для любого n > 0. Действительно, при n = 1 получаем тождество:
x^1 = F(1) * x + F(0) = 1 * x + 0 = x.
Для n = 2 уравнение выше принимает вид
x^2 = F(2) * x + F(2 -1) = 1 * х + 1 = х + 1,
что верно по условию. Теперь допустим, что формула верна при n = k,
x^k = F(k) * x + F(k - 1),
и выведем из этого ее справедливость при n = k + 1, то есть
x^(k + 1) = F(k + 1) * x + F(k).
Имеем:
x^(k + 1) = x^k * х
= (F(k) * x + F(k - 1)) * х
= F(k) * x^2 + F(k - 1) * х
= F(k) * (x + 1) + F(k - 1) * х
= (F(k) + F(k - 1)) * х + F(k)
= F(k + 1) * х + F(k),
что и требовалось доказать. Таким образом,
R^n = F(n) * R + F(n - 1)
T^n = F(n) * T + F(n - 1)
Вычитая второе равенство из первого, получаем
R^n - Т^n = F(n) * (R - T),
откуда
F(n) = (R^n - Т^n) / (R - T)
Но R - T = sqrt(5), откуда и следует формула Бине
F(n) = (R^n - Т^n) / sqrt(5).