🔀 Дискретка

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

Q: Как быстро найти F₅₀ без перебора?

Формулой Бине: $F_n$ — ближайшее целое к $\varphi^n/\sqrt5$. Для точной арифметики на больших $n$ возводят матрицу $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ в степень $n$ быстрым возведением — порядка $\log n$ умножений вместо $n$ сложений.

Q: Чему равна сумма первых n чисел Фибоначчи?

Удивительно аккуратно: $F_1 + F_2 + \dots + F_n = F_{n+2} - 1$. Проверка: $1 + 1 + 2 + 3 + 5 = 12$ и $F_7 - 1 = 13 - 1 = 12$. Доказательство — телескопированием: сдвиньте каждое слагаемое и следите, как соседние гасят друг друга.

Q: Причём здесь диагонализация матрицы?

Матрица $\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$ имеет собственные значения $\varphi$ и $\psi$ — корни того самого $\lambda^2 = \lambda + 1$. Диагонализуя её, вы в пять строк получаете формулу Бине: замкнутая формула — это диагональный вид рекуррентности.

англ. Fibonacci numbers

Последовательность, где каждое число — сумма двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55; отношение соседних членов стремится к золотому сечению.

Числа Фибоначчи — последовательность, где каждый член — сумма двух предыдущих: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. Леонардо Пизанский по прозвищу Фибоначчи вывел её в 1202 году из задачи о кроликах: пара кроликов ежемесячно приносит новую пару, молодая созревает месяц — считайте потомство. Получилась последовательность с удивительной биографией: она всплыла потом в подсолнухах, шишках, алгоритмах и даже на бирже.

F_{n} = F_{n - 1} + F_{n - 2}, F_{1} = F_{2} = 1

рекуррентное соотношение: два предыдущих знают следующий

Рекуррентность — машина с двумя ячейками памяти: засыпали единицы, дальше она работает сама. $8 + 13 = 21$ , $13 + 21 = 34$ — и так хоть до миллиона. Классическая комбинаторная переформулировка: сколькими способами подняться по лестнице из $n$ ступенек шагами в одну или две? Для $n = 4$ способы: $1 + 1 + 1 + 1$ , $2 + 1 + 1$ , $1 + 2 + 1$ , $1 + 1 + 2$ , $2 + 2$ — всего пять, и это ровно $F_{5}$ . Причина прозрачна: последний шаг был либо с $n - 1$ , либо с $n - 2$ ступеньки — в точности правило Фибоначчи.

Выводим формулу Бине

Открывай шаги

Сначала попробуйте сделать шаг сами, потом открывайте и сверяйтесь. За полный проход начисляется XP.

Побочный эффект формулы Бине — мост к золотому сечению. Отношения соседних членов падают к $φ$ : $34/55 = 0.61818$ , $55/89 = 0.61798$ , а $φ = 0.61803 \dots$ Члены растут как $φ^{n}$ : $F_{10} = 55$ , и это заметно скромнее факториала $10! = 3628800$ . Экспонента $1.61 8^{n}$ проигрывает гонку факториалу, но уверенно обгоняет любой полином — эта иерархия скоростей ещё сыграет роль в анализе алгоритмов.

В информатике числа Фибоначчи — витрина двух подходов к рекурсии. Наивная рекурсия пересчитывает одно и то же миллионы раз: число вызовов растёт само как Фибоначчи. Мемоизация или итерация с двумя переменными сводят всё к линейному времени. А возведение матрицы $(1110)$ в степень даёт $(F_{n + 1} F_{n} F_{n} F_{n - 1})$ — за $O (lo g n)$ умножений, и это прямое приложение диагонализации матрицы. Систематический разбор таких соотношений — в уроке про рекуррентные соотношения, а комбинаторные задачи с лестницами отрабатываются в тренажёре комбинаторики.

Частые вопросы

Как быстро найти F₅₀ без перебора?

Формулой Бине: $F_{n}$ — ближайшее целое к $φ^{n} / 5$ . Для точной арифметики на больших $n$ возводят матрицу $(1110)$ в степень $n$ быстрым возведением — порядка $lo g n$ умножений вместо $n$ сложений.

Чему равна сумма первых n чисел Фибоначчи?

Удивительно аккуратно: $F_{1} + F_{2} + \dots + F_{n} = F_{n + 2} - 1$ . Проверка: $1 + 1 + 2 + 3 + 5 = 12$ и $F_{7} - 1 = 13 - 1 = 12$ . Доказательство — телескопированием: сдвиньте каждое слагаемое и следите, как соседние гасят друг друга.

Почему Фибоначчи появляются в растениях?

Семечки в подсолнухе нарастают по одному правилу: каждый новый элемент поворачивается на постоянный «золотой» угол около $137. 5^{\circ}$ — он равномернее всего заполняет круг. Число спиралей в шишках и корзинках выходит соседними членами последовательности: 34 и 55, у крупных подсолнухов 89 и 144.

Причём здесь диагонализация матрицы?

Матрица $(1110)$ имеет собственные значения $φ$ и $ψ$ — корни того самого $λ^{2} = λ + 1$ . Диагонализуя её, вы в пять строк получаете формулу Бине: замкнутая формула — это диагональный вид рекуррентности.

пошагово

Решатель квадратных уравнений

Вывести формулу Бине по шагам

Явная формула чисел Фибоначчи — корни уравнения x² = x + 1: решатель найдёт их через дискриминант.

Открыть решатель