Формула для чисел Фибоначчи

Теорема 8.1. Числа Фибоначчи можно рассчитать по формуле

.

Доказательство. Убедимся в справедливости этой формулы для n = 0, 1, а затем докажем справедливость данной формулы для произвольного n по индукции. Вычислим отношение двух ближайших чисел Фибоначчи:

Мы видим, что отношение этих чисел колеблется около значения 1.618 (если игнорировать несколько первых значений). Этим свойством числа Фибоначчи напоминают члены геометрической прогрессии. Примем , (). Тогда выражение

преобразуется в

,

которое после упрощений выглядит так

.

Мы получили квадратное уравнение, корни которого равны:

Теперь можем записать:

(где c является константой). Оба члена и не дают чисел Фибоначчи, например , в то время как . Однако разность удовлетворяет рекуррентному уравнению:

.

Для n =0 эта разность дает , то есть: . Однако при n =1 мы имеем . Чтобы получить , необходимо принять: .

Теперь мы имеем две последовательности: и , которые начинаются с одинаковых двух чисел и удовлетворяют одной и той же рекуррентной формуле. Они должны быть равны: . Теорема доказана.

При возрастании n член становится очень большим, в то время как , и роль члена в разности сокращается. Поэтому при больших n приближенно можем записать

.

Мы игнорируем 1/2 (поскольку числа Фибоначчи возрастают до бесконечности при росте n до бесконечности).

Отношение называется золотым сечением, его используют за пределами математики (например, в скульптуре и архитектуре). Золотым сечением является отношение между диагональю и стороной правильного пятиугольника (рис. 8.1).

Рис. 8.1. Правильный пятиугольник и его диагонали

Для обозначения золотого сечения принято использовать букву в честь известного афинского скульптора Фидия.