EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 8 минут
#формула Бине#числа Фибоначчи#рекуррентные соотношения#золотое сечение#алгоритмы
Формула Бине: вывод и вычисление чисел Фибоначчи

Формула Бине выражает число Фибоначчи через его индекс: вместо последовательного сложения предыдущих членов в неё подставляют nn. Выражение содержит квадратный корень из пяти и степени иррациональных чисел, но его точное значение всегда целое. Чтобы увидеть, как это происходит, выберите индекс в калькуляторе: он отдельно показывает главную часть и небольшую поправку, которую из неё вычитают.

Что говорит формула

Зафиксируем нумерацию: F0=0F_0=0, F1=1F_1=1, а при n≥2n\geq2 каждый следующий член равен сумме двух предыдущих:

Fn=Fn−1+Fn−2.F_n=F_{n-1}+F_{n-2}.

Получается последовательность 0,1,1,2,3,5,8,13,21,…0,1,1,2,3,5,8,13,21,\ldots. Например, F5=5F_5=5: отсчёт начинается с нулевого индекса. Для тех же начальных условий формула Бине имеет вид

Fn=φn−ψn5,φ=1+52,ψ=1−52.F_n=\frac{\varphi^n-\psi^n}{\sqrt5},\qquad \varphi=\frac{1+\sqrt5}{2},\quad \psi=\frac{1-\sqrt5}{2}.

Здесь φ≈1,618034\varphi\approx1{,}618034, а ψ≈−0,618034\psi\approx-0{,}618034. Формула справедлива для целых n≥0n\geq0. Первый корень больше единицы, поэтому его степень растёт; модуль второго меньше единицы, поэтому его степень уменьшается. При этом второй корень отрицателен, и знак его степени чередуется.

Золотая точка проходит по значениям поправки: они меняют знак и приближаются к нулю с ростом индекса.

Отрезки показывают расстояние каждого дискретного значения от нуля: индексы последовательности здесь целые. Движение показывает, что уменьшается именно поправка ψn/5\psi^n/\sqrt5, а не само число Фибоначчи. У неё важная роль: вычитание этой величины превращает главную часть в точное целое.

Как получить формулу из рекурсии

Ищем частные решения рекурсии в виде rnr^n. Для ненулевого rr подстановка даёт rn=rn−1+rn−2r^n=r^{n-1}+r^{n-2}. Разделив на rn−2r^{n-2}, получаем характеристическое уравнение

r2−r−1=0.r^2-r-1=0.

Его два различных корня - именно φ\varphi и ψ\psi. Поскольку каждый из них удовлетворяет равенству r2=r+1r^2=r+1, обе последовательности φn\varphi^n и ψn\psi^n подчиняются исходному правилу сложения. Значит, этому правилу подчиняется и любая их линейная комбинация:

Fn=Aφn+Bψn.F_n=A\varphi^n+B\psi^n.

Коэффициенты выбираем по двум начальным условиям. При n=0n=0 получаем A+B=0A+B=0, а при n=1n=1 - Aφ+Bψ=1A\varphi+B\psi=1. Следовательно, B=−AB=-A, A(φ−ψ)=1A(\varphi-\psi)=1. Разность корней равна 5\sqrt5, поэтому A=1/5A=1/\sqrt5, B=−1/5B=-1/\sqrt5. Подстановка даёт формулу Бине.

Это одновременно объясняет целочисленность результата. Выражение справа имеет начальные значения 00 и 11 и удовлетворяет той же рекурсии, что и FnF_n. Два стартовых значения однозначно определяют все следующие, поэтому выражение совпадает с целой последовательностью на каждом неотрицательном целом индексе. Приближённые десятичные записи корней для этого доказательства не нужны.

Пример: пятый член

Подставим n=5n=5. Обозначим главную часть φ5/5\varphi^5/\sqrt5, а поправку - ψ5/5\psi^5/\sqrt5. С точностью до шести знаков после запятой получаем

φ55≈4,959675,ψ55≈−0,040325.\frac{\varphi^5}{\sqrt5}\approx4{,}959675,\qquad \frac{\psi^5}{\sqrt5}\approx-0{,}040325.

Вычитаем отрицательную поправку: F5≈4,959675−(−0,040325)=5,000000F_5\approx4{,}959675-(-0{,}040325)=5{,}000000. Округлённые промежуточные значения здесь иллюстрируют расчёт; точное равенство следует из формулы с корнями. Проверка рекурсией даёт F4+F3=3+2=5F_4+F_3=3+2=5.

Поправка формулы Бине для индексов от нуля до десяти меняет знак и уменьшается по модулю; при n равно 5 она примерно минус 0,040
Поправка формулы Бине для индексов от нуля до десяти меняет знак и уменьшается по модулю; при n равно 5 она примерно минус 0,040

На рисунке для n=0n=0 поправка приблизительно равна 0,4470{,}447, для n=1n=1 - −0,276-0{,}276, для n=5n=5 - −0,040-0{,}040. При чётном индексе она положительна, при нечётном отрицательна. Калькулятор использует те же определения, но показывает шесть знаков и находит точное целое отдельной рекурсией.

Ещё одна проверка: восьмой член

Возьмём n=8n=8. Рекурсия даёт цепочку F5=5F_5=5, F6=8F_6=8, F7=13F_7=13, F8=21F_8=21. Формула приводит к тому же результату: её главная часть приблизительно равна 21,00951921{,}009519, а поправка - 0,0095190{,}009519. Вычитая поправку, получаем 2121. На этот раз индекс чётный, поэтому поправка положительна, а главная часть расположена чуть выше целого. Сравнение с пятым членом показывает оба варианта знака и помогает проверить порядок вычитания.

Числовое совпадение служит проверкой вычисления, но не заменяет доказательства для всех индексов. Для строгого обоснования можно обозначить правую часть формулы через GnG_n и применить индукцию сразу к двум соседним членам. База - G0=0G_0=0 и G1=1G_1=1. Если Gk=FkG_k=F_k и Gk+1=Fk+1G_{k+1}=F_{k+1}, то по общей рекурсии Gk+2=Gk+1+Gk=Fk+1+Fk=Fk+2G_{k+2}=G_{k+1}+G_k=F_{k+1}+F_k=F_{k+2}. Пара совпадающих значений сдвигается на один индекс, поэтому рассуждение охватывает всю последовательность.

Почему работает округление

Так как ∣ψ∣<1|\psi|<1, для любого целого n≥0n\geq0 выполняется

∣ψn5∣≤15<12.\left|\frac{\psi^n}{\sqrt5}\right|\leq\frac1{\sqrt5}<\frac12.

Значит, расстояние между FnF_n и главной частью φn/5\varphi^n/\sqrt5 всегда строго меньше половины. Поскольку FnF_n - целое число, оно является единственным ближайшим целым к главной части:

Fn=round⁡ ⁣(φn5),n≥0.F_n=\operatorname{round}\!\left(\frac{\varphi^n}{\sqrt5}\right),\qquad n\geq0.

Это математическое равенство относится к точным действительным числам. Оно включает n=0n=0: 1/5≈0,4471/\sqrt5\approx0{,}447 округляется до нуля. При нечётном nn главная часть чуть меньше целого, при чётном - чуть больше. Именно знак поправки показывает, с какой стороны происходит приближение.

Отношение соседних чисел, начиная с ненулевого знаменателя, стремится к φ\varphi. Однако это свойство не следует путать с методом поиска минимума: в методе золотого сечения то же отношение применяется для деления интервала, а не для вычисления членов последовательности.

Формула в программе: скорость и точность

Для небольшого индекса рекурсию удобно реализовать двумя переменными. Начните с пары (a,b)=(0,1)(a,b)=(0,1) и повторите обновление (a,b)←(b,a+b)(a,b)\leftarrow(b,a+b) ровно nn раз. После этого a=Fna=F_n. Например, после пяти обновлений пара равна (5,8)(5,8). Нужно использовать старые значения обоих слагаемых, иначе последовательное присваивание может случайно прибавить уже обновлённое число.

Такой алгоритм выполняет nn сложений и хранит два целых значения. Если нужна вся последовательность, результаты можно записывать в массив. Наивная рекурсивная функция с двумя вызовами на каждом шаге многократно пересчитывает одинаковые индексы; динамическое программирование и мемоизация объясняют, как сохранять промежуточные ответы. Для одного очень большого индекса существует и быстрое удвоение с логарифмическим числом шагов, хотя работа с растущими целыми тоже имеет стоимость.

Прямая запись формулы выглядит короткой, но в обычной машинной арифметике 5\sqrt5 и степени представлены приближённо. Ошибка округления растёт вместе с масштабом главной части и при больших nn может превысить половину; тогда округление машинного результата вернёт неверное целое, хотя математическая формула верна. Кроме того, стандартный JavaScript number точно представляет не все целые больше 253−12^{53}-1. Для больших точных ответов применяют целочисленную рекурсию или быстрое удвоение с BigInt. Калькулятор ограничен диапазоном 0≤n≤200\leq n\leq20, где показанные целые малы, а дробные значения являются приближениями.

У прямой формулы есть и другие применения: она помогает исследовать рост последовательности и доказывать тождества. Другой путь к выражению для членов - метод производящих функций, который упаковывает последовательность в степенной ряд. А куча Фибоначчи использует числа этой последовательности в оценках структуры данных; сама она не является способом подставить индекс в формулу Бине.

Как проверить решение самостоятельно

При выводе полезно разделить три шага. Сначала проверьте корни характеристического уравнения: подстановка каждого из них должна давать r2=r+1r^2=r+1. Затем проверьте коэффициенты по обоим начальным условиям. Наконец, убедитесь, что полученное выражение удовлетворяет рекурсии. Проверки только одного значения, например F5=5F_5=5, недостаточно: множество других выражений тоже может дать пять при этом индексе.

Для численного примера составьте короткую таблицу индексов и не округляйте корни до подстановки. Если взять φ=1,62\varphi=1{,}62 и затем возвести его в высокую степень, ошибка исходного приближения тоже увеличится. Сравнивайте с целочисленным расчётом и указывайте знак поправки отдельно: при n=5n=5 это отрицательное число, а не просто расстояние до ближайшего целого.

Для оценки роста заметим, что отношение ∣ψ/φ∣|\psi/\varphi| меньше единицы. Поэтому вклад второго корня мал по сравнению с первым при больших индексах, а последовательность растёт примерно как φn/5\varphi^n/\sqrt5. Слово «примерно» существенно: относительная ошибка стремится к нулю, но точное выражение по-прежнему содержит оба слагаемых. Это различие помогает не смешивать асимптотическую оценку и алгоритм, который обязан вернуть все цифры ответа.

Ещё один способ осмыслить два корня - посмотреть на начальные условия по отдельности. При n=0n=0 обе степени равны единице, и их разность равна нулю. При n=1n=1 разность корней равна 5\sqrt5; деление на неё даёт единицу. Если удалить вторую степень, уже эти два условия одновременно выполняться не будут. Поправка не является произвольной настройкой для больших чисел: она необходима с самого начала.

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

Частые ошибки

  • Сдвигать индексы. При принятом соглашении F0=0F_0=0, а F5=5F_5=5; другая нумерация требует изменить запись формулы.
  • Терять знак второго корня. ψ\psi отрицателен, поэтому при нечётном nn его степень отрицательна и её вычитание увеличивает результат.
  • Считать главную часть точным равенством. Без поправки она только приближается к целому, хотя округление точного значения даёт FnF_n.
  • Считать машинное округление доказательством. Математическая оценка поправки не ограничивает погрешность вычисления иррациональных чисел на компьютере.

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

Почему в ответе целое число, если в формуле есть корни?

Иррациональные части двух слагаемых взаимно компенсируются. Строго это видно из совпадения начальных условий и рекурсии: правая часть равна FnF_n для каждого целого n≥0n\geq0.

Можно ли просто отбросить второе слагаемое?

Для приближённой оценки при большом nn - да. Для точного равенства нужно сохранить поправку или округлить точное значение главной части до ближайшего целого.

Подходит ли формула для любого вещественного индекса?

Обычная последовательность определена для целых индексов. Отрицательное основание ψ\psi при произвольной вещественной степени не всегда даёт вещественное число, поэтому изложенное правило относится к целым n≥0n\geq0.

Коротко

Формула Бине заменяет рекурсию выражением через два корня уравнения r2−r−1=0r^2-r-1=0. Растущая часть задаёт масштаб числа Фибоначчи, а затухающая поправка обеспечивает точное совпадение с целым. Для доказательств удобна формула с корнями; для больших точных вычислений надёжнее целочисленные алгоритмы.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Задача Иосифа Флавия: формула и решение

Задача Иосифа Флавия: формула и решение

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

8 ноября 20269 минут
Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77: сжатие с помощью ссылок назад

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

8 ноября 20268 минут
Числа Белла: разбиения множества и формула

Числа Белла: разбиения множества и формула

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

8 ноября 20269 минут
Числа трибоначчи: формула и примеры вычисления

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

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

8 ноября 20269 минут
Чётность подстановки: инверсии и знак

Чётность подстановки: инверсии и знак

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

8 ноября 20268 минут
Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: построение и операции

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

8 ноября 20268 минут