EssayAI
Блог
Блог
Математика и алгоритмы

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

8 ноября 2026Время чтения: 9 минут
#числа фибоначчи#рекуррентная формула#последовательности#рекурсия#золотое сечение
Числа Фибоначчи: рекуррентная формула и примеры

Числа Фибоначчи - последовательность, в которой каждый член, начиная с третьего, равен сумме двух предыдущих. Одного этого правила недостаточно: нужны ещё два начальных значения. Возьмём соглашение F0=0F_0=0 и F1=1F_1=1; тогда ряд начинается так: 0,1,1,2,3,5,8,13,21,…0, 1, 1, 2, 3, 5, 8, 13, 21, \ldots. Как получить число с нужным номером и почему иногда ответы отличаются на один индекс? Переместите ползунок и сравните выбранный член с двумя слагаемыми перед ним.

Рекуррентная формула и начальные значения

Определение состоит из двух начальных условий и правила перехода:

F0=0,F1=1,Fn=Fn−1+Fn−2(n≥2).F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}\quad(n\geq 2).

Индекс nn - номер члена, а не само значение. Чтобы найти FnF_n, необходимо знать именно два соседних предыдущих значения: Fn−1F_{n-1} и Fn−2F_{n-2}. Например, F2=F1+F0=1+0=1F_2=F_1+F_0=1+0=1, затем F3=F2+F1=1+1=2F_3=F_2+F_1=1+1=2. После задания двух первых членов правило однозначно определяет все следующие: на каждом шаге складывать уже известные числа можно только одним способом.

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

В других источниках нумерацию могут начинать с F1=1F_1=1, F2=1F_2=1. Это совместимо с принятой здесь записью, если просто не выписывать F0F_0. Но иногда первую единицу называют нулевым членом: тогда индексы сдвигаются. Перед сравнением ответов всегда проверяйте начальные условия, а не только само правило сложения.

Как вычислить член по шагам

Найдём F8F_8. В таблице под каждым номером записано его значение; строка не начинается с единицы, потому что нулевой индекс тоже занимает место.

nn012345678
FnF_n01123581321

Последний переход использует F6=8F_6=8 и F7=13F_7=13: получаем F8=8+13=21F_8=8+13=21. Ещё два шага дают F9=34F_9=34 и F10=55F_{10}=55. Если продолжить тот же процесс до двадцатого индекса, получится F20=6765F_{20}=6765. В калькуляторе можно проверить любой индекс от 2 до 20; высота столбца соответствует значению, а золотой столбец - выбранному члену.

Таблица первых девяти чисел Фибоначчи: F₈ равно сумме 8 и 13, то есть 21
Таблица первых девяти чисел Фибоначчи: F₈ равно сумме 8 и 13, то есть 21

Для вычисления вручную удобно держать рядом пару чисел. Начните с (0,1)(0,1), сложите их и сдвиньте пару: (1,1)(1,1), затем (1,2)(1,2), (2,3)(2,3) и так далее. Каждое продвижение на один шаг увеличивает оба индекса на единицу. Записывая индекс над числом, легче избежать ошибки: одинаковые значения F1F_1 и F2F_2 - разные члены последовательности.

Как восстановить предыдущие члены

Правило работает и в обратную сторону, если известны два соседних члена. Из равенства Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} получаем Fn−2=Fn−Fn−1F_{n-2}=F_n-F_{n-1}. Например, зная, что два соседних члена равны 13 и 21, вычитаем: предыдущий равен 8. Ещё один шаг даёт 13−8=513-8=5. Порядок важен: из более позднего члена вычитают непосредственно предшествующий, иначе знак результата изменится.

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

Задача о подъёме по ступенькам

Предположим, что за ход можно подняться на одну или две ступеньки. Пусть ana_n - количество способов оказаться на ступеньке nn, причём порядок ходов различается. На нулевой ступеньке есть один способ ничего не делать: a0=1a_0=1. На первую ведёт один ход, поэтому a1=1a_1=1.

Любой путь на ступеньку n≥2n\geq 2 заканчивается либо одиночным шагом со ступеньки n−1n-1, либо двойным со ступеньки n−2n-2. Эти случаи не пересекаются и исчерпывают все варианты. Значит,

an=an−1+an−2.a_n=a_{n-1}+a_{n-2}.

Правило совпадает с правилом Фибоначчи, но начало другое: a0=1a_0=1, а не ноль. Поэтому an=Fn+1a_n=F_{n+1}. Например, для трёх ступенек есть три пути: 1+1+11+1+1, 1+21+2 и 2+12+1; это a3=F4=3a_3=F_4=3. Для восьми ступенек получится a8=F9=34a_8=F_9=34. Сдвиг индекса возникает из начальных условий, а не из изменения рекуррентного правила.

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

Можно проверить разбиение на последнем ходе на небольшом примере. Для четырёх ступенек к каждому пути на третью добавим один шаг: получится три варианта. К каждому пути на вторую добавим двойной шаг: получится ещё два. В первой группе все пути заканчиваются единицей, во второй - двойкой, поэтому повторного подсчёта нет. Итого пять вариантов, как и предсказывает F5=5F_5=5. Если бы порядок ходов не различался или были разрешены другие размеры шага, модель и рекурсия изменились бы.

Вычисление и рекурсия в программе

Прямой перевод формулы в рекурсивную функцию вызывает два подвычисления для каждого n≥2n\geq 2. При этом одни и те же значения пересчитываются: например, при вычислении F6F_6 число F4F_4 понадобится и непосредственно, и внутри вычисления F5F_5. Дерево вызовов быстро разрастается; число операций растёт экспоненциально.

Итеративный способ идёт снизу вверх: хранит пару соседних членов и заменяет её парой (b,a+b)(b,a+b). Для FnF_n потребуется n−1n-1 сложений при n≥2n\geq 2 и лишь два текущих числа. Это оценка числа арифметических операций; при очень больших nn сами целые числа становятся длинными, и стоимость одного сложения уже нельзя считать постоянной. В статье про динамическое программирование разобрано, как сохранение промежуточных результатов устраняет повторную работу.

Ещё один способ ускорить повторные запросы - заранее построить таблицу до самого большого нужного индекса. Тогда каждое значение вычисляется один раз, а затем его можно взять по номеру. Таблица занимает больше памяти, чем пара переменных, зато позволяет быстро обращаться ко всем ранее найденным членам. Важно заранее определить границу таблицы и формат хранения больших целых чисел.

Формула Бине и золотое сечение

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

φ=1+52,ψ=1−52.\varphi=\frac{1+\sqrt5}{2},\qquad \psi=\frac{1-\sqrt5}{2}.

Оба числа удовлетворяют уравнению x2=x+1x^2=x+1. Поэтому последовательности φn\varphi^n и ψn\psi^n по отдельности удовлетворяют тому же правилу сложения, что и числа Фибоначчи. Их подходящая разность также удовлетворяет рекурсии:

Fn=φn−ψn5.F_n=\frac{\varphi^n-\psi^n}{\sqrt5}.

При n=0n=0 правая часть равна нулю, при n=1n=1 - единице. Значит, она совпадает с последовательностью, заданной нашими начальными условиями. Формула полезна для доказательств и оценки роста, хотя вычисление с обычными числами с плавающей точкой может давать ошибки округления при больших индексах. Итерация с целыми числами сохраняет точность при условии, что выбранный тип способен хранить результат.

Поскольку ∣ψ∣<1|\psi|<1, вклад ψn\psi^n уменьшается по модулю. Отсюда для больших nn следует приближение Fn≈φn/5F_n\approx\varphi^n/\sqrt5, а отношение соседних членов Fn+1/FnF_{n+1}/F_n при n→∞n\to\infty стремится к φ≈1,618\varphi\approx1{,}618. Делить можно только при Fn≠0F_n\ne0, поэтому отношение не определено для n=0n=0. Само золотое число также возникает в методе золотого сечения при поиске минимума функции; это отдельное применение того же числа.

Из предельного отношения не следует, что каждый объект с двумя размерами в отношении, близком к 1,6181{,}618, связан с последовательностью Фибоначчи. Для содержательной связи нужно показать правило построения или вычисления, а затем проверить, какие именно значения оно даёт. При малых индексах отличие от предела особенно заметно: например, отношение 2/12/1 равно двум. Члены ряда целые, тогда как предельное отношение иррационально; переход к пределу описывает тенденцию, а не точное значение отдельной дроби.

Сумма первых членов и доказательство

У первых членов есть удобное тождество:

F0+F1+⋯+Fn=Fn+2−1(n≥0).F_0+F_1+\cdots+F_n=F_{n+2}-1\quad(n\geq 0).

Проверим его математической индукцией. При n=0n=0 левая часть равна F0=0F_0=0, правая - F2−1=0F_2-1=0. Пусть равенство верно для некоторого nn. Прибавив Fn+1F_{n+1} к обеим частям, получим справа Fn+2+Fn+1−1=Fn+3−1F_{n+2}+F_{n+1}-1=F_{n+3}-1. Это и есть требуемая формула для следующего индекса. Значит, она верна для всех неотрицательных nn.

Например, сумма от F0F_0 до F6F_6 равна 0+1+1+2+3+5+8=200+1+1+2+3+5+8=20, что совпадает с F8−1=21−1F_8-1=21-1. Другой способ изучать такие равенства - метод производящих функций, который собирает члены последовательности в коэффициенты одного ряда.

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

  • Пропускать начальные условия. Одно правило сложения задаёт множество последовательностей; начальная пара определяет конкретную.
  • Путать номер и значение. При принятой нумерации F8=21F_8=21, а 34 - это F9F_9.
  • Считать две единицы одним членом. Значения F1F_1 и F2F_2 совпадают, но их индексы различны.
  • Забывать сдвиг в прикладной задаче. Для ступенек с a0=1a_0=1 результат равен Fn+1F_{n+1}, а не FnF_n.
  • Принимать предел отношения за точное равенство. Отношение соседних членов приближается к φ\varphi, но для конечного индекса не равно ему.

FAQ

Почему нужны именно два начальных значения?

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

Можно ли найти FnF_n без выписывания всех предыдущих членов?

Да, для этого есть формула Бине и алгоритмы быстрого удвоения. При точном программном вычислении важно учитывать размер целых чисел и погрешность приближённой арифметики.

Все ли отношения соседних чисел равны золотому сечению?

Нет. Например, F5/F4=5/3F_5/F_4=5/3, а F6/F5=8/5F_6/F_5=8/5. Они приближаются к φ\varphi при росте индекса, но в каждом таком случае являются рациональными числами, тогда как φ\varphi иррационально.

Коротко

При F0=0F_0=0 и F1=1F_1=1 рекуррентная формула Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} последовательно задаёт все числа Фибоначчи. Чтобы решить задачу, сначала зафиксируйте нумерацию и начальные значения, затем складывайте соседние члены или используйте подходящую формулу. В задачах подсчёта такое же правило может давать сдвинутый ряд из-за другой начальной пары.

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

Открыть EssayAI

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

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

Числа Люка: формула, примеры и связь с Фибоначчи

Числа Люка: формула, примеры и связь с Фибоначчи

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

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

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

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

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

Последовательность Падована: формула и примеры

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

8 ноября 20269 минут
Теорема Больцано-Вейерштрасса: доказательство и примеры

Теорема Больцано-Вейерштрасса: доказательство и примеры

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

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

Динамическое программирование: основы и идея мемоизации

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

7 июля 20267 минут
Числа Стирлинга первого рода: перестановки и циклы

Числа Стирлинга первого рода: перестановки и циклы

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

20 июня 20268 минут