Шпаргалки / Математика / Школа / Дискретная математика

Числа Фибоначчи

Числа Фибоначчи — это особая последовательность, где каждое следующее число равно сумме двух предыдущих.

Описывает естественный рост, развитие, самоподобие — от спирали ракушки до ветвления деревьев и деления клеток.

Каждый шаг строится на основе прошлого. Это — модель накопления, эволюции, памяти.

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

F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2}, \quad n \ge 2

Ряд:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots

Зачем они нужны

В математике — для анализа рекурсий, роста, комбинаторики, числовых закономерностей.
В природе — у растений (расположение листьев, семян, спиралей).
В программировании — как база для рекурсий, динамики, алгоритмов и хэширования.
В искусстве — через золотое сечение $\varphi \approx 1.618$, связанное с Фибоначчи.
В экономике и теории вероятности — модели роста, рисков, волн.

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

где

\varphi = \frac{1 + \sqrt{5}}{2} \quad (\text{золотое сечение})

\psi = \frac{1 - \sqrt{5}}{2}

При больших $n$, член с $\psi^n$ можно отбросить:

F_n \approx \frac{\varphi^n}{\sqrt{5}}

Рост почти экспоненциальный .

G(x) = \frac{x}{1 - x - x^2}

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

\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}

Эта запись нужна для быстрого вычисления — можно найти $F_n$ за $O(\log{n})$ через быстрое возведение матриц в степень.

Свойство	Формула	Зачем нужно
Рекуррентность	( F_{n+2} = F_{n+1} + F_n )	Базовая зависимость
Сумма первых n чисел	( \sum_{k=0}^{n} F_k = F_{n+2} - 1 )	Быстро считать сумму ряда
Сумма квадратов	( \sum_{k=0}^{n} F_k^2 = F_n F_{n+1} )	Привязка геометрическая (площади квадратов)
Двойной индекс	( F_{2n} = F_n(2F_{n+1} - F_n) )	Для ускоренных расчётов
Отношение соседних	( \frac{F_{n+1}}{F_n} \to \varphi )	Показывает связь с золотым сечением
Чётность	( F_n \text{ чётно, если } n \bmod 3 = 0 )	Упрощение в модульных системах

\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.618

Отношение двух соседних чисел Фибоначчи всё ближе к $\varphi$:

Это и есть математическая основа “золотой гармонии” — соотношения, приятные глазу и природе.