Теорема 8.1. Числа Фибоначчи можно рассчитать по формуле
.
Доказательство. Убедимся в справедливости этой формулы для n = 0, 1, а затем докажем справедливость данной формулы для произвольного n по индукции. Вычислим отношение двух ближайших чисел Фибоначчи:
Мы видим, что отношение этих чисел колеблется около значения 1.618 (если игнорировать несколько первых значений). Этим свойством числа Фибоначчи напоминают члены геометрической прогрессии. Примем , (). Тогда выражение
преобразуется в
,
которое после упрощений выглядит так
.
Мы получили квадратное уравнение, корни которого равны:
Теперь можем записать:
(где c является константой). Оба члена и не дают чисел Фибоначчи, например , в то время как . Однако разность удовлетворяет рекуррентному уравнению:
.
Для n=0 эта разность дает, то есть: . Однако при n=1 мы имеем . Чтобы получить , необходимо принять: .
Теперь мы имеем две последовательности: и , которые начинаются с одинаковых двух чисел и удовлетворяют одной и той же рекуррентной формуле. Они должны быть равны: . Теорема доказана.
При возрастании n член становится очень большим, в то время как , и роль члена в разности сокращается. Поэтому при больших n приближенно можем записать
.
Мы игнорируем 1/2 (поскольку числа Фибоначчи возрастают до бесконечности при росте n до бесконечности).
Отношение называется золотым сечением, его используют за пределами математики (например, в скульптуре и архитектуре). Золотым сечением является отношение между диагональю и стороной правильного пятиугольника (рис. 8.1).
Рис. 8.1. Правильный пятиугольник и его диагонали
Для обозначения золотого сечения принято использовать букву в честь известного афинского скульптора Фидия.