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

Ну вот вам простенькое доказательство, которое не использует страшных слов типа "характеристический многочлен" и т. п. Используется только решение квадратных уравнений и метод математической индукции, но это вроде как в школе проходят. Обозначим 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).