Формула Бине: вывод и вычисление чисел Фибоначчи

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

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

Задача Иосифа Флавия: формула и решение
Задача Иосифа Флавия: разбор счёта по кругу, рекуррентная формула, пример с семью участниками и решение для каждого второго с помощью двоичной записи.

Алгоритм LZ77: сжатие с помощью ссылок назад
Алгоритм LZ77 на пошаговом примере: как скользящее окно находит повторы, что означают расстояние и длина, как работает перекрытие и от чего зависит размер результата.

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

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

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

Дерево двоичного поиска: построение и операции
Дерево двоичного поиска: как устроены узлы, как построить BST по ключам, выполнить обход и удалить элемент, от чего зависит высота и сложность операций.