Числа Фибоначчи: рекуррентная формула и примеры

Числа Фибоначчи - последовательность, в которой каждый член, начиная с третьего, равен сумме двух предыдущих. Одного этого правила недостаточно: нужны ещё два начальных значения. Возьмём соглашение и ; тогда ряд начинается так: . Как получить число с нужным номером и почему иногда ответы отличаются на один индекс? Переместите ползунок и сравните выбранный член с двумя слагаемыми перед ним.
Рекуррентная формула и начальные значения
Определение состоит из двух начальных условий и правила перехода:
Индекс - номер члена, а не само значение. Чтобы найти , необходимо знать именно два соседних предыдущих значения: и . Например, , затем . После задания двух первых членов правило однозначно определяет все следующие: на каждом шаге складывать уже известные числа можно только одним способом.
В других источниках нумерацию могут начинать с , . Это совместимо с принятой здесь записью, если просто не выписывать . Но иногда первую единицу называют нулевым членом: тогда индексы сдвигаются. Перед сравнением ответов всегда проверяйте начальные условия, а не только само правило сложения.
Как вычислить член по шагам
Найдём . В таблице под каждым номером записано его значение; строка не начинается с единицы, потому что нулевой индекс тоже занимает место.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 |
Последний переход использует и : получаем . Ещё два шага дают и . Если продолжить тот же процесс до двадцатого индекса, получится . В калькуляторе можно проверить любой индекс от 2 до 20; высота столбца соответствует значению, а золотой столбец - выбранному члену.

Для вычисления вручную удобно держать рядом пару чисел. Начните с , сложите их и сдвиньте пару: , затем , и так далее. Каждое продвижение на один шаг увеличивает оба индекса на единицу. Записывая индекс над числом, легче избежать ошибки: одинаковые значения и - разные члены последовательности.
Как восстановить предыдущие члены
Правило работает и в обратную сторону, если известны два соседних члена. Из равенства получаем . Например, зная, что два соседних члена равны 13 и 21, вычитаем: предыдущий равен 8. Ещё один шаг даёт . Порядок важен: из более позднего члена вычитают непосредственно предшествующий, иначе знак результата изменится.
Эта операция полезна для проверки таблицы. Если каждое число, начиная с третьего записанного, равно сумме соседних слева, а первые два значения совпадают с условиями, вся таблица построена верно. Совпадения одного или двух значений в середине недостаточно для проверки нумерации: одинаковые единицы в начале особенно легко принять друг за друга. Поэтому сверяйте не только числовую пару, но и её индексы.
Задача о подъёме по ступенькам
Предположим, что за ход можно подняться на одну или две ступеньки. Пусть - количество способов оказаться на ступеньке , причём порядок ходов различается. На нулевой ступеньке есть один способ ничего не делать: . На первую ведёт один ход, поэтому .
Любой путь на ступеньку заканчивается либо одиночным шагом со ступеньки , либо двойным со ступеньки . Эти случаи не пересекаются и исчерпывают все варианты. Значит,
Правило совпадает с правилом Фибоначчи, но начало другое: , а не ноль. Поэтому . Например, для трёх ступенек есть три пути: , и ; это . Для восьми ступенек получится . Сдвиг индекса возникает из начальных условий, а не из изменения рекуррентного правила.
Аналогичный приём применяют шире: разбивают объекты по последнему действию, убеждаются, что случаи не пересекаются, и складывают количества. В статье о числах Стирлинга первого рода похожая идея приводит к другой рекурсии для перестановок и циклов.
Можно проверить разбиение на последнем ходе на небольшом примере. Для четырёх ступенек к каждому пути на третью добавим один шаг: получится три варианта. К каждому пути на вторую добавим двойной шаг: получится ещё два. В первой группе все пути заканчиваются единицей, во второй - двойкой, поэтому повторного подсчёта нет. Итого пять вариантов, как и предсказывает . Если бы порядок ходов не различался или были разрешены другие размеры шага, модель и рекурсия изменились бы.
Вычисление и рекурсия в программе
Прямой перевод формулы в рекурсивную функцию вызывает два подвычисления для каждого . При этом одни и те же значения пересчитываются: например, при вычислении число понадобится и непосредственно, и внутри вычисления . Дерево вызовов быстро разрастается; число операций растёт экспоненциально.
Итеративный способ идёт снизу вверх: хранит пару соседних членов и заменяет её парой . Для потребуется сложений при и лишь два текущих числа. Это оценка числа арифметических операций; при очень больших сами целые числа становятся длинными, и стоимость одного сложения уже нельзя считать постоянной. В статье про динамическое программирование разобрано, как сохранение промежуточных результатов устраняет повторную работу.
Ещё один способ ускорить повторные запросы - заранее построить таблицу до самого большого нужного индекса. Тогда каждое значение вычисляется один раз, а затем его можно взять по номеру. Таблица занимает больше памяти, чем пара переменных, зато позволяет быстро обращаться ко всем ранее найденным членам. Важно заранее определить границу таблицы и формат хранения больших целых чисел.
Формула Бине и золотое сечение
Рекурсия позволяет получить член по предыдущим, а формула Бине выражает его непосредственно через индекс. Обозначим
Оба числа удовлетворяют уравнению . Поэтому последовательности и по отдельности удовлетворяют тому же правилу сложения, что и числа Фибоначчи. Их подходящая разность также удовлетворяет рекурсии:
При правая часть равна нулю, при - единице. Значит, она совпадает с последовательностью, заданной нашими начальными условиями. Формула полезна для доказательств и оценки роста, хотя вычисление с обычными числами с плавающей точкой может давать ошибки округления при больших индексах. Итерация с целыми числами сохраняет точность при условии, что выбранный тип способен хранить результат.
Поскольку , вклад уменьшается по модулю. Отсюда для больших следует приближение , а отношение соседних членов при стремится к . Делить можно только при , поэтому отношение не определено для . Само золотое число также возникает в методе золотого сечения при поиске минимума функции; это отдельное применение того же числа.
Из предельного отношения не следует, что каждый объект с двумя размерами в отношении, близком к , связан с последовательностью Фибоначчи. Для содержательной связи нужно показать правило построения или вычисления, а затем проверить, какие именно значения оно даёт. При малых индексах отличие от предела особенно заметно: например, отношение равно двум. Члены ряда целые, тогда как предельное отношение иррационально; переход к пределу описывает тенденцию, а не точное значение отдельной дроби.
Сумма первых членов и доказательство
У первых членов есть удобное тождество:
Проверим его математической индукцией. При левая часть равна , правая - . Пусть равенство верно для некоторого . Прибавив к обеим частям, получим справа . Это и есть требуемая формула для следующего индекса. Значит, она верна для всех неотрицательных .
Например, сумма от до равна , что совпадает с . Другой способ изучать такие равенства - метод производящих функций, который собирает члены последовательности в коэффициенты одного ряда.
Частые ошибки
- Пропускать начальные условия. Одно правило сложения задаёт множество последовательностей; начальная пара определяет конкретную.
- Путать номер и значение. При принятой нумерации , а 34 - это .
- Считать две единицы одним членом. Значения и совпадают, но их индексы различны.
- Забывать сдвиг в прикладной задаче. Для ступенек с результат равен , а не .
- Принимать предел отношения за точное равенство. Отношение соседних членов приближается к , но для конечного индекса не равно ему.
FAQ
Почему нужны именно два начальных значения?
Потому что правило использует два предыдущих члена. Первая пара запускает вычисление; выбрав другую пару, обычно получим другую последовательность с тем же правилом.
Можно ли найти без выписывания всех предыдущих членов?
Да, для этого есть формула Бине и алгоритмы быстрого удвоения. При точном программном вычислении важно учитывать размер целых чисел и погрешность приближённой арифметики.
Все ли отношения соседних чисел равны золотому сечению?
Нет. Например, , а . Они приближаются к при росте индекса, но в каждом таком случае являются рациональными числами, тогда как иррационально.
Коротко
При и рекуррентная формула последовательно задаёт все числа Фибоначчи. Чтобы решить задачу, сначала зафиксируйте нумерацию и начальные значения, затем складывайте соседние члены или используйте подходящую формулу. В задачах подсчёта такое же правило может давать сдвинутый ряд из-за другой начальной пары.
Читайте также

Числа Люка: формула, примеры и связь с Фибоначчи
Числа Люка начинаются с 2 и 1 и строятся сложением двух предыдущих членов. Разбираем формулу, связь с числами Фибоначчи, примеры и алгоритм вычисления.

Числа трибоначчи: формула и примеры вычисления
Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.

Последовательность Падована: формула и примеры
Последовательность Падована: начальные члены и рекуррентная формула, вычисление по шагам, пластическое число, производящая функция и комбинаторная модель.

Теорема Больцано-Вейерштрасса: доказательство и примеры
Теорема Больцано-Вейерштрасса для последовательностей: формулировка, доказательство вложенными отрезками, примеры подпоследовательностей и связь с компактностью.

Динамическое программирование: основы и идея мемоизации
Что такое динамическое программирование простыми словами: перекрывающиеся подзадачи, оптимальная подструктура, мемоизация и табуляция на примере чисел Фибоначчи, разница с наивной рекурсией.

Числа Стирлинга первого рода: перестановки и циклы
Числа Стирлинга первого рода: что считают знаковые и беззнаковые числа, рекуррентная формула, связь с циклами перестановок, факториалом и нисходящим факториалом, разбор примеров.