Формула Бине и сходимость к фи

Числа Фибоначчи можно получить без рекурсии — прямой формулой через золотое сечение.

Формула Бине — выражение $n$-го числа Фибоначчи через степени золотого сечения $\varphi$ и сопряжённого числа $\psi$.

Удивительно, но иррациональные $\varphi$ и $\psi$ способны дать целые числа Фибоначчи. Это мост между двумя предыдущими уроками: последовательность из задачи про кроликов и пропорция золотого сечения оказываются двумя сторонами одной медали.

Формула Бине

Пусть $\varphi = \dfrac{1+\sqrt5}{2}$ и $\psi = \dfrac{1-\sqrt5}{2}$ — два корня уравнения $x^2 = x + 1$. Тогда

$$F_n = \frac{\varphi^n - \psi^n}{\sqrt 5}.$$

Откуда такое чудо? Любая последовательность с правилом $F_n = F_{n-1} + F_{n-2}$ — это комбинация степеней корней её характеристического уравнения $x^2 = x + 1$. Подобрав коэффициенты под начальные условия $F_0 = 0, F_1 = 1$, получаем ровно формулу Бине. Поскольку $|\psi| \approx 0{,}618 \lt 1$, слагаемое $\psi^n$ быстро стремится к нулю, и $F_n$ — это просто ближайшее целое к $\varphi^n / \sqrt5$.

Сходимость отношений

Отсюда вытекает второй знаменитый факт:

$$\lim_{n \to \infty} \frac{F_{n+1}}{F_n} = \varphi.$$

Отношение соседних чисел Фибоначчи всё точнее приближает золотое сечение. Проверим обе формулы:

from math import sqrt

phi = (1 + sqrt(5)) / 2
psi = (1 - sqrt(5)) / 2

# Формула Бине против прямого счёта
for n in [5, 10, 20, 30]:
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    binet = round((phi**n - psi**n) / sqrt(5))
    print(f"n={n:>2}: прямо={a:>7}, Бине={binet:>7}, совпало={a == binet}")

print("--- отношение F(n+1)/F(n) ---")
a, b = 1, 1
for i in range(2, 12):
    a, b = b, a + b
    print(f"шаг {i:>2}: {b / a:.8f}")
print(f"phi      = {phi:.8f}")

Вывод:

n= 5: прямо=      5, Бине=      5, совпало=True
n=10: прямо=     55, Бине=     55, совпало=True
n=20: прямо=   6765, Бине=   6765, совпало=True
n=30: прямо= 832040, Бине= 832040, совпало=True
--- отношение F(n+1)/F(n) ---
шаг  2: 2.00000000
шаг  3: 1.50000000
шаг  4: 1.66666667
шаг  5: 1.60000000
шаг  6: 1.62500000
шаг  7: 1.61538462
шаг  8: 1.61904762
шаг  9: 1.61764706
шаг 10: 1.61818182
шаг 11: 1.61797753
phi      = 1.61803399

Как работает под капотом

Отношения «прыгают» вокруг $\varphi$: то выше, то ниже, но амплитуда колебаний быстро гаснет. Это прямое следствие формулы Бине: $\dfrac{F_{n+1}}{F_n} = \dfrac{\varphi^{n+1} - \psi^{n+1}}{\varphi^n - \psi^n}$, и поскольку $\psi^n \to 0$, дробь стремится к $\varphi$. Знак $\psi^n$ чередуется (ведь $\psi \lt 0$), отсюда и колебания то сверху, то снизу. В вычислениях формулой Бине надо помнить про погрешность чисел с плавающей точкой: для больших $n$ округление спасает, но при $n$ за сотню даже double может ошибиться.

Частые ошибки

Первая — забыть про деление на $\sqrt5$ или про вычитание $\psi^n$ (только $\varphi^n/\sqrt5$ даёт близкое, но не точно целое значение, потому и нужен round). Вторая — думать, что отношение монотонно растёт к $\varphi$: оно колеблется. Третья — применять формулу Бине к огромным $n$ в float и удивляться ошибке: для точности нужны целочисленные методы.

Итог

Формула Бине: $F_n = (\varphi^n - \psi^n)/\sqrt5$.
Слагаемое $\psi^n$ исчезает, $F_n$ — ближайшее целое к $\varphi^n/\sqrt5$.
$F_{n+1}/F_n \to \varphi$, колеблясь вокруг предела.
В float формула страдает от погрешности при больших $n$.