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

Последовательность Фибоначчи 1, 1, 2, 3, 5, 8, 13, … начинается с двух единиц; каждый следующий член равен сумме двух предыдущих. Та же рекурсия $x_k = x_{k-1} + x_{k-2}$ может начинаться с любых положительных чисел $x_1 = a$ и $x_2 = b$; начало 2, 1 даёт числа Люка (2, 1, 3, 4, 7, 11, …). Здесь можно построить такую последовательность, добавляя квадраты к прямоугольнику, проследить приближение отношения соседних членов $r_k = x_k / x_{k-1}$ к золотому сечению φ и увидеть на паутинной диаграмме, почему это происходит при любом положительном начале.

В начале дан прямоугольник ширины a и высоты b. Каждый новый член получается добавлением квадрата к стороне длиной с последний член: к прямоугольнику со сторонами $x_{k-1}$ и $x_{k-2}$ прикладывается квадрат со стороной $x_{k-1}$, и получается прямоугольник $x_k$ на $x_{k-1}$. Поэтому с третьего члена $r_k$ — это длинная сторона, делённая на короткую, то есть форма прямоугольника. На рисунке его размер остаётся постоянным: видно, как стабилизируется форма, а не как растут числа.

Квадрат меняет отношение по фиксированному правилу $r_{k+1} = (x_k + x_{k-1})/x_k = 1 + 1/r_k$. Чтобы добавление квадрата сохраняло форму, нужно $r = 1 + 1/r$, то есть $r^2 = r + 1$. Положительный корень этого уравнения — золотое сечение $\varphi = (1 + \sqrt5)/2 \approx 1.618$. Так устроен золотой прямоугольник: добавление квадрата даёт ту же форму с линейным масштабом в φ раз больше. Паутинная диаграмма изображает правило. От отношения r поднимитесь к кривой $y = 1 + 1/r$, чтобы прочитать следующее отношение, затем двигайтесь по горизонтали к диагонали $y = r$, чтобы начать новый шаг с него. Кривая и диагональ пересекаются в (φ, φ).

Почему отношение меняет сторону и сходится при любых положительных начальных значениях? Поскольку $\varphi = 1 + 1/\varphi$, один шаг преобразует отклонение от φ в точности по формуле

Знак минус переносит каждое отношение на другую сторону от φ по сравнению с предыдущим, кроме случая точно золотого начала. Начиная с $r_3$ все отношения больше 1, поэтому на каждом шаге модуль отклонения умножается на число меньше $1/\varphi \approx 0.618$ и стремится к 0. Удалить может лишь первый шаг: если $r_2 = b/a$ меньше 1/φ, отклонение растёт. Вблизи φ множитель стремится к $-1/\varphi^2 \approx -0.382$, наклону кривой в точке пересечения с диагональю; в итоге каждый шаг оставляет примерно 0.382 прежнего отклонения.

Сами члены растут почти как геометрическая прогрессия: каждый всё ближе к предыдущему, умноженному на φ. Для чисел Фибоначчи $F_1 = F_2 = 1$ формула Бине даёт точное выражение:

Поскольку $|\psi| < 1$, $F_n$ — ближайшее к $\varphi^n/\sqrt5$ целое число. На странице собственных векторов эти же два числа появляются как собственные значения матрицы, переводящей пару соседних членов в следующую пару.