bulgakov

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

Число двоичных слов длины nn без двух соседних нулей подчиняется соотношению xn=xn−1+xn−2x_n=x_{n-1}+x_{n-2}: слово начинается либо с единицы (дальше любое подходящее слово длины n−1n-1), либо с «01» (дальше любое подходящее слово длины n−2n-2). Получаются числа 2,3,5,8,13,…2,3,5,8,13,\dots — это числа Фибоначчи 1,1,2,3,5,8,13,…1,1,2,3,5,8,13,\dots, только с другой нумерацией, а характеристическое уравнение λ2−λ−1=0\lambda^2-\lambda-1=0 даёт для них явную формулу и отношение соседних чисел, стремящееся к 1+52\dfrac{1+\sqrt5}2.

Что пригодится из прошлого: два вещественных корня — формула (5) для xn=p xn−1+q xn−2x_n=p\,x_{n-1}+q\,x_{n-2}; двоичные коды — слова из нулей и единиц; правило суммы. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Задача

Задача. Найти число слов длины nn в алфавите {0,1}\{0,1\}, которые не содержат двух соседних нулей.

Обозначим это число xnx_n. Выпишем малые случаи:

  • n=1n=1: слова 00 и 11 — оба подходят, x1=2x_1=2;
  • n=2n=2: из четырёх слов 00,01,10,1100,01,10,11 не подходит только 0000: x2=3x_2=3;
  • n=3n=3: слова 010, 011, 101, 110, 111 — x3=5x_3=5 (из восьми слов не подходят три: 000000, 001001 и 100100).

Для n=4n=4 подходящих слов 88: 0101, 0110, 0111, 1010, 1011, 1101, 1110, 1111.

Рекуррентное соотношение

Пусть n≥3n\ge3. Разобьём все подходящие слова длины nn на два непересекающихся класса по первой букве.

  • а) Слова, начинающиеся с «1». После единицы идёт любое подходящее слово длины n−1n-1: единица в начале не может создать пару нулей. Таких слов xn−1x_{n-1}.
  • б) Слова, начинающиеся с «0». Вторая буква обязательно «1» (иначе получилось бы «00»). После «01» идёт любое подходящее слово длины n−2n-2: единица на второй позиции отделяет начальный нуль от остального слова, поэтому пара нулей не может возникнуть на границе, а хвост нужно проверять сам по себе. Таких слов xn−2x_{n-2}.

По правилу суммы

xn=xn−1+xn−2,x1=2, x2=3.\boxed{x_n=x_{n-1}+x_{n-2},\qquad x_1=2,\ x_2=3}.

Первые значения: 2,3,5,8,13,21,…2,3,5,8,13,21,\dots — каждое следующее равно сумме двух предыдущих.

Решение

Линейное соотношение второго порядка: p=q=1p=q=1. Характеристическое уравнение λ2−λ−1=0\lambda^2-\lambda-1=0, дискриминант D=1+4=5>0D=1+4=5>0. Корни

λ1=1−52,λ2=1+52.\lambda_1=\frac{1-\sqrt5}2,\qquad\lambda_2=\frac{1+\sqrt5}2.

Формула (5) из предыдущей главы ждёт значения x0x_0 и x1x_1. У нас заданы x1=2x_1=2, x2=3x_2=3; так как x2=x1+x0x_2=x_1+x_0, достаточно положить x0=1x_0=1 (3=2+13=2+1): слово длины 00 — «пустое», без символов, и оно одно. Тогда соотношение xn=xn−1+xn−2x_n=x_{n-1}+x_{n-2} верно при всех n≥2n\ge2, формула (5) применима, и a=1a=1, b=2b=2:

c1=λ2a−bλ2−λ1=λ2−25,c2=b−λ1aλ2−λ1=2−λ15.c_1=\frac{\lambda_2a-b}{\lambda_2-\lambda_1}=\frac{\lambda_2-2}{\sqrt5},\qquad c_2=\frac{b-\lambda_1a}{\lambda_2-\lambda_1}=\frac{2-\lambda_1}{\sqrt5}.

Цель — записать c1c_1 и c2c_2 как степени корней: тогда итоговая формула получится короче. Корни удовлетворяют λ2=λ+1\lambda^2=\lambda+1, поэтому λ22=λ2+1=3+52\lambda_2^2=\lambda_2+1=\dfrac{3+\sqrt5}2 и λ12=λ1+1=3−52\lambda_1^2=\lambda_1+1=\dfrac{3-\sqrt5}2. Тогда 2−λ1=2−1−52=3+52=λ222-\lambda_1=2-\dfrac{1-\sqrt5}2=\dfrac{3+\sqrt5}2=\lambda_2^2, а λ2−2=1+52−2=5−32=−3−52=−λ12\lambda_2-2=\dfrac{1+\sqrt5}2-2=\dfrac{\sqrt5-3}2=-\dfrac{3-\sqrt5}2=-\lambda_1^2. Значит, c2=λ225c_2=\dfrac{\lambda_2^2}{\sqrt5}, c1=−λ125c_1=-\dfrac{\lambda_1^2}{\sqrt5}, и

xn=c1λ1n+c2λ2n=15(λ2 n+2−λ1 n+2)=15((1+52)n+2−(1−52)n+2).\begin{aligned} x_n&=c_1\lambda_1^n+c_2\lambda_2^n=\frac1{\sqrt5}\Bigl(\lambda_2^{\,n+2}-\lambda_1^{\,n+2}\Bigr)\\ &=\boxed{\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}2\right)^{n+2}-\left(\frac{1-\sqrt5}2\right)^{n+2}\right)}. \end{aligned}

Проверка: при n=0n=0 формула даёт λ22−λ125=(λ2−λ1)(λ2+λ1)5=1=x0\dfrac{\lambda_2^2-\lambda_1^2}{\sqrt5}=\dfrac{(\lambda_2-\lambda_1)(\lambda_2+\lambda_1)}{\sqrt5}=1=x_0; при n=1n=1 — λ23−λ13λ2−λ1=λ22+λ1λ2+λ12=3−1=2=x1\dfrac{\lambda_2^3-\lambda_1^3}{\lambda_2-\lambda_1}=\lambda_2^2+\lambda_1\lambda_2+\lambda_1^2=3-1=2=x_1.

(Те же константы получаются и прямым решением системы 2=x1=c1λ1+c2λ22=x_1=c_1\lambda_1+c_2\lambda_2, 3=x2=c1λ12+c2λ223=x_2=c_1\lambda_1^2+c_2\lambda_2^2 — вычисления длиннее, ответ тот же.)

Последовательность Фибоначчи

Рассмотрим последовательность

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …,Fn=Fn−1+Fn−2,F0=F1=1.1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 13,\ 21,\ 34,\ 55,\ \dots,\qquad F_n=F_{n-1}+F_{n-2},\quad F_0=F_1=1.

Сравнив, видим Fn=xn−1F_n=x_{n-1} при n≥1n\ge1, поэтому (заменяем nn на n−1n-1 в формуле для xnx_n)

Fn=15((1+52)n+1−(1−52)n+1).\boxed{F_n=\frac1{\sqrt5}\left(\left(\frac{1+\sqrt5}2\right)^{n+1}-\left(\frac{1-\sqrt5}2\right)^{n+1}\right)}.

Эта последовательность называется последовательностью Фибоначчи, а формула — формулой Бине. В других книгах нумерацию часто сдвигают: F0=0F_0=0, F1=1F_1=1. Поэтому смотрите на начальные значения.

Проверка. n=0n=0: λ2−λ15=55=1\dfrac{\lambda_2-\lambda_1}{\sqrt5}=\dfrac{\sqrt5}{\sqrt5}=1 ✓. n=1n=1: λ22−λ125=(λ2−λ1)(λ2+λ1)5=1⋅1=1\dfrac{\lambda_2^2-\lambda_1^2}{\sqrt5}=\dfrac{(\lambda_2-\lambda_1)(\lambda_2+\lambda_1)}{\sqrt5}=1\cdot1=1 ✓ (так как λ1+λ2=1\lambda_1+\lambda_2=1).

Два свойства чисел Фибоначчи

1. Соседние числа взаимно просты: (Fn,Fn+1)=1(F_n,F_{n+1})=1 (наибольший общий делитель равен единице). Доказательство по алгоритму Евклида: любой общий делитель Fn+1F_{n+1} и FnF_n делит и Fn+1−Fn=Fn−1F_{n+1}-F_n=F_{n-1}, то есть является общим делителем FnF_n и Fn−1F_{n-1}. Обратно, общий делитель FnF_n и Fn−1F_{n-1} делит Fn+1=Fn+Fn−1F_{n+1}=F_n+F_{n-1}. Значит, наборы общих делителей совпадают и НОД(Fn+1,Fn)=НОД(Fn,Fn−1)\text{НОД}(F_{n+1},F_n)=\text{НОД}(F_n,F_{n-1}). Повторяя, дойдём до НОД(F1,F0)=НОД(1,1)=1\text{НОД}(F_1,F_0)=\text{НОД}(1,1)=1.

2. Отношение соседних чисел приближается к числу 1+52\dfrac{1+\sqrt5}2 — «золотому сечению»: чем больше nn, тем ближе оно к этому числу (это записывают через предел — число, к которому значения приближаются сколь угодно близко при больших nn):

lim⁡n→∞Fn+1Fn=1+52≈1,618.\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\frac{1+\sqrt5}2\approx1{,}618.

Объяснение по формуле Бине: Fn+1Fn=λ2n+2−λ1n+2λ2n+1−λ1n+1=λ2⋅1−(λ1/λ2)n+21−(λ1/λ2)n+1\dfrac{F_{n+1}}{F_n}=\dfrac{\lambda_2^{n+2}-\lambda_1^{n+2}}{\lambda_2^{n+1}-\lambda_1^{n+1}}=\lambda_2\cdot\dfrac{1-(\lambda_1/\lambda_2)^{n+2}}{1-(\lambda_1/\lambda_2)^{n+1}}. Так как ∣λ1λ2∣=5−15+1<1\left|\dfrac{\lambda_1}{\lambda_2}\right|=\dfrac{\sqrt5-1}{\sqrt5+1}<1, степени (λ1/λ2)n(\lambda_1/\lambda_2)^n приближаются к нулю (число, меньшее 11 по модулю, при возведении во всё большую степень становится всё меньше), дробь приближается к 11, и всё выражение — к λ2\lambda_2.

В последнем столбце — отличие дроби Fn+1Fn\dfrac{F_{n+1}}{F_n} от 1+52\dfrac{1+\sqrt5}{2}:

nn FnF_n Fn+1/FnF_{n+1}/F_n Отличие
1 1 2,0000 0,3820
2 2 1,5000 0,1180
3 3 1,6667 0,0486
4 5 1,6000 0,0180
5 8 1,6250 0,0070
6 13 1,6154 0,0026
7 21 1,6190 0,0010
8 34 1,6176 0,0004
9 55 1,6182 0,0001
10 89 1,6180 0,0001

Та же последовательность в другой задаче

Лесенка из nn ступенек; за один шаг поднимаются на одну или две ступеньки. Сколькими способами можно подняться? Обозначим cnc_n. Первый шаг — на одну ступеньку (дальше cn−1c_{n-1} способов) либо на две (cn−2c_{n-2}): cn=cn−1+cn−2c_n=c_{n-1}+c_{n-2}, c0=c1=1c_0=c_1=1 (подняться на 00 ступенек можно одним способом — ничего не делать; на одну ступеньку — тоже одним). Это в точности FnF_n.

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

  • Спутать нумерацию. В этой главе F0=F1=1F_0=F_1=1; при F0=0F_0=0 номера сдвинуты на единицу.
  • Решать соотношение, не проверив начальные условия. Формула (5) требует x0x_0 и x1x_1; при заданных x1,x2x_1,x_2 сначала восстановите x0x_0 (здесь x0=1x_0=1).
  • Считать число слов 2n2^n. Запрет «00» сильно сокращает: для n=10n=10 подходит всего F11=144F_{11}=144 слов из 10241024.
  • Ожидать, что формула Бине даёт дробные значения. Иррациональные слагаемые взаимно сокращаются — получаются целые числа.

Проверь себя

1. Сколько существует двоичных слов длины 66 без двух соседних нулей?

Решение

x6=x5+x4=13+8=21x_6=x_5+x_4=13+8=21 (последовательность 2,3,5,8,13,212,3,5,8,13,21). Это F7=21F_7=21.

2. Вычислите F10F_{10}.

Решение

1,1,2,3,5,8,13,21,34,55,891,1,2,3,5,8,13,21,34,55,89: F10=89F_{10}=89.

3. Вычислите F10F9\dfrac{F_{10}}{F_9} и сравните с 1+52\dfrac{1+\sqrt5}2.

Решение

8955=1,61818\dfrac{89}{55}=1,61818, а 1+52=1,61803…\dfrac{1+\sqrt5}2=1{,}61803\dots Различие уже в четвёртом знаке после запятой.

4. Сколькими способами можно подняться по лесенке из 77 ступенек шагами по 11 или 22 ступеньки?

Решение

c7=F7=21c_7=F_7=21.

Итог

  • Слова без «00»: xn=xn−1+xn−2x_n=x_{n-1}+x_{n-2}, x1=2x_1=2, x2=3x_2=3; начинаются либо с «1», либо с «01».
  • Характеристическое уравнение λ2−λ−1=0\lambda^2-\lambda-1=0, корни 1±52\dfrac{1\pm\sqrt5}2.
  • Числа Фибоначчи FnF_n (F0=F1=1F_0=F_1=1): формула Бине Fn=15(λ2n+1−λ1n+1)F_n=\dfrac1{\sqrt5}\left(\lambda_2^{n+1}-\lambda_1^{n+1}\right); соседние числа взаимно просты; Fn+1Fn→1+52\dfrac{F_{n+1}}{F_n}\to\dfrac{1+\sqrt5}2.
ПрактикаЗагружаем тест…