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

Чи́сла Фибона́ччи — элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS)

в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (известного как Фибоначчи)^[1]. Иногда число 0 не рассматривается как член последовательности.

Более формально, последовательность чисел Фибоначчи $\left\{F_n\right\}$ задается линейным рекуррентным соотношением:

$F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2.$

Иногда числа Фибоначчи рассматривают и для отрицательных номеров n как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. При этом члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: $F_n=F_{n+2}-F_{n+1}$:

n	−10	−9	−8	−7	−6	−5	−4	−3	−2	−1	0	1	2	3	4	5	6	7	8	9	10
$F_n$	−55	34	−21	13	−8	5	−3	2	−1	1	0	1	1	2	3	5	8	13	21	34	55

Легко заметить, что $\! F_{-n} = (-1)^{n+1}F_n$.

Происхождение

Страница Книги абака (лат. Liber abaci) Фибоначчи из Национальной центральной библиотеки Флоренции.
В правом блоке демонстрируется последовательность Фибоначчи.
Позиции от 0 до 12 обозначены тёмным цветом римскими цифрами, а значения красным цветом индо-арабскими цифрами.

Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении), намного раньше, чем она стала известна в Европе.

Образец длиной n может быть построен путём добавления S к образцу длиной n-1, либо L к образцу длиной n-2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что:

• В «нулевом» месяце имеется пара кроликов (1 новая пара).
• В первом месяце первая пара производит на свет другую пару (1 новая пара).
• Во втором месяце обе пары кроликов порождают другие пары и первая пара погибает (2 новые пары).
• В третьем месяце вторая пара и две новые пары порождают в общем три новые пары, а старая вторая пара погибает (3 новые пары).

Закономерным является тот факт, что каждая пара кроликов порождает ещё две пары на протяжении жизни, а затем погибает.

Пусть популяция за месяц $n$ будет равна $F_n$. В это время только те кролики, которые жили в месяце $n-2$, являются способными к размножению и производят потомков, тогда $F_{n-2}$ пар прибавится к текущей популяции $F_{n-1}$. Таким образом общее количество пар будет равно:

$F_n = F_{n-2} + F_{n-1}.$

Формула Бине

Формула Бине выражает в явном виде значение $F_n$ как функцию от n:

$F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} = \frac{\varphi^n - (-\varphi )^{-n}}{\varphi - (-\varphi )^{-1}} = \frac{\varphi^n - (-\varphi )^{-n}}{2\varphi - 1}$,

где $\varphi=\frac{1 + \sqrt{5}}{2}$ — золотое сечение. При этом $\varphi\,\!$ и $(-\varphi )^{-1}=1-\varphi\,\!$ являются корнями характеристического уравнения $x^2-x-1=0\,\!$.

Из формулы Бине следует, что для всех $n\geqslant 0$, $F_n$ есть ближайшее к $\frac{\varphi^n}{\sqrt{5}}\,$ целое число, то есть $F_n = \left\lfloor\frac{\varphi^n}{\sqrt{5}}\right\rceil$. В частности, при $n\to\infty$ справедлива асимптотика $F_n\sim \frac{\varphi^n}{\sqrt{5}}$.

Формула Бине может быть аналитически продолжена следующим образом:

$F_z = \frac{1}{\sqrt{5}} \left( \varphi^z - \frac{\cos{\pi z}}{\varphi^z} \right)$

При этом соотношение $F_{z+2} = F_{z+1} + F_z$ выполняется для любого комплексного числа z.

Тождества

Геометрическое доказательство формулы для суммы квадратов первых n чисел Фибоначчи^[2].

• $F_1+F_2+F_3+\dots+F_n=F_{n+2}-1$
• $F_1+F_3+F_5+\dots+F_{2n-1}=F_{2n}$
• $F_2+F_4+F_6+\dots+F_{2n}=F_{2n+1}-1$
• $F_{n+1}F_{n+2}^{}-F_nF_{n+3}=(-1)^{n}$
• $F_1^2+F_2^2+F_3^2+\dots+F_{n}^2=F_nF_{n+1}$
• $F_n^2+F_{n+1}^2=F_{2n+1}$
• $F_{2n}=F_{n+1}^2-F_{n-1}^2$
• $F_{3n}=F_{n+1}^3+F_n^3-F_{n-1}^3$
• $F_{5n}=25F_{n}^5+25(-1)^{n}F_n^3+5F_{n}$

И более общие формулы:

• $F_{n+m}^{}=F_{n-1}F_{m}+F_{n}F_{m+1}=F_{n+1}F_{m+1}-F_{n-1}F_{m-1}$
• $F_{(k+1)n}^{}=F_{n-1}F_{kn}+F_nF_{kn+1}$
• $F_n^{}=F_lF_{n-l+1}+F_{l-1}F_{n-l}$
• Числа Фибоначчи представляются значениями континуант на наборе единиц: $F_{n+1} = K_n(1,\dots,1)$, то есть

$F_{n+1} = \det \begin{pmatrix} 1 & 1 & 0 &\cdots & 0 \\ -1 & 1 & 1 & \ddots & \vdots\\ 0 & -1 & \ddots &\ddots & 0 \\ \vdots & \ddots & \ddots &\ddots & 1 \\ 0 & \cdots & 0 & -1 & 1 \end{pmatrix}$, а также $\ F_{n+1} = \det \begin{pmatrix} 1 & i & 0 &\cdots & 0 \\ i & 1 & i & \ddots & \vdots\\ 0 & i & \ddots &\ddots & 0 \\ \vdots & \ddots & \ddots &\ddots & i \\ 0 & \cdots & 0 & i & 1\end{pmatrix}$,

где матрицы имеют размер $n\times n$, i — мнимая единица.

• Числа Фибоначчи можно выразить через многочлены Чебышева:

$F_{n+1} = (-i)^n U_n\left(\frac{-i}{2}\right) = (-i)^n T_n(-i),$

$F_{2n+2} = U_n\left(\frac{3}{2}\right) = T_n(3).$

• Для любого n,

$\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n = \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}.$

• Следствие. Подсчёт определителей даёт

$(-1)^n = F_{n+1} F_{n-1} - F_n^2.$

Свойства

• Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. $(F_m,F_n) = F_{(m,n)}$. Следствия:
  • $F_m$ делится на $F_n$ тогда и только тогда, когда $m$ делится на $n$ (за исключением $n=2$). В частности, $F_m$ делится на $F_3=2$ (то есть является чётным) только для $m=3k$; $F_m$ делится на $F_4=3$ только для $m=4k$; $F_m$ делится на $F_5=5$ только для $m=5k$ и т. д.
  • $F_m$ может быть простым только для простых $m$ (с единственным исключением $m=4$). Например, число $F_{13}=233$ простое, и его индекс 13 также прост. Обратное не верно, наименьший контрпример — $F_{19}=4181=37\cdot 113$. Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.

• Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен $x^2-x-1$ имеет корни $~\varphi$ и $-\frac{1}{\varphi}$.
• Отношения $\frac{F_{n+1}}{F_n}$ являются подходящими дробями золотого сечения $\phi$ и, в частности, $\lim_{n\to\infty} \frac{F_{n+1}}{F_n} = \varphi.$
• Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы

  $F_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor} {n-k\choose k}$.

• В 1964 году Дж. Кон (J. H. E. Cohn) доказал,^[3] что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:

  $F_0=0^2=0$, $F_1=1^2=1$, $F_2=1^2=1$, $F_{12}=12^2=144$.

• Производящей функцией последовательности чисел Фибоначчи является:

  $1 + x + 2 x^2 + 3 x^3 + 5 x^4 + 8 x^5 + \dots = \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2}$

• Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена

  $z(x,y) = 2xy^4 + x^2 y^3 - 2 x^3 y^2 - y^5 - x^4 y + 2y,$

на множестве неотрицательных целых чисел x и y.^[4]

• Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
• Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность:

  1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)

  • В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.
• Натуральное число N является числом Фибоначчи тогда и только тогда, когда $5N^2 + 4$ или $5N^2 - 4$ является квадратом.^[5]
• Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.^[6]
• Число Фибоначчи $F_{n+2}$ равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних нулей. При этом $F_n$ равно количеству таких кортежей, начинающихся с нуля, а $F_{n+1}$ — начинающихся с единицы.

Вариации и обобщения

• Числа трибоначчи
• Числа Фибоначчи являются частным случаем последовательностей Люка $~F_n = U_n(1,-1)$, при этом их дополнением являются числа Люка $~L_n = V_n(1,-1)$.

В других областях

Следует отметить, что существует мнение, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространенный миф, который почти всегда оказывается неточной подгонкой под желаемый результат^[7][8].

В природе

• Филлотаксис (листорасположение) у растений описывается последовательностью Фибоначчи. Семена подсолнуха, сосновые шишки, лепестки цветков, ячейки ананаса также располагаются согласно последовательности Фибоначчи.^{[9][10][11][12]}
• Длины фаланг пальцев человека относятся примерно как числа Фибоначчи.^[9][13]

В культуре

• Американский писатель-фантаст Дэн Браун в книге «Код да Винчи» описал анаграмму на основе последовательности Фибоначчи.
• Светящиеся числа Фибоначчи от 1 до 55 прикреплены на дымовой трубе Turku Energia в Турку^[14] и главном вокзале Цюриха^[15].
• В фильме «Двадцать одно» (англ. 21) последовательность Фибоначчи представлена в виде надписи на торте.
• «Ряд Фибоначчи» — дополнительное название песни 2012 года «Новый сигнал из космоса» российской рок-группы «Сплин».
• В java-игре Doom RPG для мобильных телефонов в "Проходе" после прохождения 7 сектора есть секретная дверь, кодом которой являются числа Фибоначчи
• Числам Фибоначчи посвящён один их шуточных лимериков Джеймса Линдона^[16]:

     Плотная пища жён Фибоначчи
     Только на пользу им шла, не иначе.
     Весили жёны, согласно молве,
     Каждая — как предыдущие две.

См. также

• Дерево Фибоначчи
• Задача об упаковке в контейнеры
• Золотое сечение
• Метод Фибоначчи с запаздываниями
• Метод Фибоначчи поиска экстремума
• Непрерывная дробь
• Рекурсия
• Динамическое программирование
• Фибоначчи
• Фибоначчиева система счисления
• Числа Леонардо

Примечания

1. ↑ Числа Фибоначчи — статья из Большой советской энциклопедии
2. ↑ Фибоначчи числа // Энциклопедический словарь юного математика / Сост. Савин А. П.. — 2-е изд. — М.: Педагогика, 1989. — С. 312—314. — 352 с. — ISBN 5715502187
3. ↑ J H E Cohn. Square Fibonacci Numbers Etc, стр. 109–113.
4. ↑ P. Ribenboim. The New Book of Prime Number Records. — Springer, 1996. — С. 193.
5. ↑ Ira Gessel Problem H-187 // Fibonacci Quarterly. — 1972. — Т. 10. — С. 417–419.
6. ↑ В. Серпинский Задача 66 // 250 задач по элементарной теории чисел. — М.: Просвещение, 1968. — 168 с.
7. ↑ Fibonacci Flim-Flam (англ.)
8. ↑ The Myth That Will Not Go Away (англ.)
9. ↑ ^{1 2} Золотое сечение в природе
10. ↑ Числа Фибоначчи
11. ↑ Числа Фибоначчи
12. ↑ Глава из книги О. Е. Акимова «Конец науки»
13. ↑ Г. Манукян. ПОЭЗИЯ ЧИСЕЛ ФИБОНАЧЧИ
14. ↑ Марио Мерц Fibonacci Sequence 1-55 (фин.)
15. ↑ Based in Villigen: Fibonacci sequence at the Zürich Hauptbahnhof<
16. ↑ Матвеев, Михаил. Путешествие по ПаЛиндондромии с Джеймсом Линдоном // Знание-сила. - 2012. - № 3. - С. 110-116 . - ISSN 0130-1640.

Литература

• Н. Н. Воробьёв. Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).
• А. И. Маркушевич. Возвратные последовательности. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — (Популярные лекции по математике).
• А. Н. Рудаков Числа Фибоначчи и простота числа 2¹²⁷-1 // Математическое Просвещение, третья серия. — 2000. — Т. 4.
• Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
• Дональд Кнут, Роналд Грэхем, Орен Паташник Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7

Ссылки

• На Викискладе есть медиафайлы по теме Числа Фибоначчи
• Первые 300 чисел Фибоначчи (англ.)
• Расчет чисел Фибоначчи рекурсией (Mathcad Calculation Server)
• Компьютеры Фибоначчи
• Числа Фибоначчи в природе