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

Числа, полученные сложением двух предыдущих

Плитка из квадратов , длины сторон которых представляют собой последовательные числа Фибоначчи: 1, 1, 2, 3, 5, 8, 13 и 21.

В математике последовательность Фибоначчи — это последовательность , в которой каждое число представляет собой сумму двух предыдущих. Числа, являющиеся частью последовательности Фибоначчи, известны как числа Фибоначчи , обычно обозначаемые F _n  . Последовательность обычно начинается с 0 и 1, хотя некоторые авторы начинают последовательность с 1 и 1 или иногда (как это делал Фибоначчи) с 1 и 2. Начиная с 0 и 1, последовательность начинается

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, .... ^[1]

Числа Фибоначчи были впервые описаны в индийской математике еще в 200 г. до н.э. в работе Пингалы по перечислению возможных моделей санскритской поэзии, образованных из слогов двух длин. ^{[2] [3] [4]} Они названы в честь итальянского математика Леонардо Пизанского, также известного как Фибоначчи , который представил последовательность в западноевропейской математике в своей книге 1202 года Liber Abaci . ^[5]

Числа Фибоначчи неожиданно часто встречаются в математике, настолько, что их изучению посвящен целый журнал — Fibonacci Quarterly . Приложения чисел Фибоначчи включают компьютерные алгоритмы, такие как метод поиска Фибоначчи и структура данных кучи Фибоначчи , а также графы , называемые кубами Фибоначчи , используемые для соединения параллельных и распределенных систем. Они также появляются в биологических условиях , таких как ветвление деревьев, расположение листьев на стебле , ростки плодов ананаса , цветение артишока и расположение прицветников сосновой шишки, хотя они не встречаются. у всех видов.

Числа Фибоначчи также тесно связаны с золотым сечением : формула Бине выражает n -е число Фибоначчи через n и золотое сечение и подразумевает, что отношение двух последовательных чисел Фибоначчи стремится к золотому сечению по мере увеличения n . Числа Фибоначчи также тесно связаны с числами Люка , которые подчиняются тому же рекуррентному соотношению и образуют с числами Фибоначчи дополнительную пару последовательностей Люка .

Определение

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

Числа Фибоначчи могут быть определены рекуррентным соотношением ^[6]

$${\displaystyle F_{0}=0,\quad F_{1}=1,}$$

$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$

n > 1

В некоторых старых определениях значение опускается, поэтому последовательность начинается с и повторение допустимо для n > 2 . ^{[7] [8]} ${\displaystyle F_{0}=0}$ ${\displaystyle F_{1}=F_{2}=1,}$ ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$

Первые 20 чисел Фибоначчи F _n : ^[1]

История

Индия

Тринадцать ( F ₇ ) способов расположения длинных и кратких слогов в каденции длиной шесть. Восемь ( F ₆ ) заканчиваются кратким слогом, а пять ( F ₅ ) – долгим слогом.

Последовательность Фибоначчи появляется в индийской математике в связи с санскритской просодией . ^{[3] [9] [10]} В санскритской поэтической традиции существовал интерес к перечислению всех моделей длинных (L) слогов длительностью 2 единицы, сопоставленных с короткими (S) слогами продолжительностью 1 единица. Подсчет различных паттернов последовательных L и S с заданной общей продолжительностью приводит к числам Фибоначчи: количество паттернов длительностью m единиц равно F _{m +1} . ^[4]

Знания о последовательности Фибоначчи были выражены еще в Пингале ( ок.  450–200 до н.э.). Сингх цитирует загадочную формулу Пингалы « мисрау ча» («два смешаны») и учёных, которые интерпретируют ее в контексте как говорящие, что количество паттернов для m долей ( F _{m +1} ) получается добавлением одного [S] к F _m . случаях и один [L] для случаев F _{m −1} . ^[11] Бхарата Муни также выражает знание последовательности в Натья Шастре (ок. 100 г. до н.э. – ок. 350 г. н. э.). ^{[12] [2]} Однако наиболее ясное изложение этой последовательности можно найти в работе Вираханки (ок. 700 г. н. э.), чья собственная работа утеряна, но доступна в цитате Гопалы (ок. 1135 г.): ^[10]

Вариации двух прежних метров [это вариация]... Например, для [метра длины] четыре, вариации метров двух [и] трёх при смешивании получается пять. [прорабатывает примеры 8, 13, 21]... Таким образом, процессу следует следовать во всех матра-вриттах [просодических сочетаниях]. ^[а]

Хемачандре (ок. 1150 г.) также приписывают знание этой последовательности, ^[2] написав, что «сумма последнего и предпоследнего есть число… следующей матра-вритты». ^{[14] [15]}

Европа

Страница Liber Abaci Фибоначчи из Национальной библиотеки Флоренции, показывающая (в рамке справа) 13 записей последовательности Фибоначчи: индексы от настоящего до XII (месяцев) в виде латинских порядковых номеров и римских цифр, а также номера (пар кроликов). ) как индийско-арабские цифры, начинающиеся с 1, 2, 3, 5 и заканчивающиеся на 377.

Последовательность Фибоначчи впервые появляется в книге Фибоначчи « Liber Abaci» ( «Книга вычислений» , 1202 г.) ^{[16] [17]} , где она используется для расчета роста популяции кроликов. ^{[18] [19]} Фибоначчи рассматривает рост идеализированной ( биологически нереальной) популяции кроликов , предполагая, что: новорожденную племенную пару кроликов помещают в поле; каждая племенная пара спаривается в месячном возрасте, а в конце второго месяца всегда дает еще одну пару кроликов; кролики никогда не умирают, а продолжают размножаться вечно. Фибоначчи задал загадку: сколько пар будет через год?

• В конце первого месяца они спариваются, но остается еще только 1 пара.
• В конце второго месяца они производят новую пару, так что на поле осталось 2 пары.
• В конце третьего месяца исходная пара производит вторую пару, но вторая пара спаривается только для того, чтобы вынашивать ребенка в течение месяца, поэтому всего есть 3 пары.
• В конце четвертого месяца исходная пара произвела еще одну новую пару, а пара, родившаяся два месяца назад, также произвела свою первую пару, составив 5 пар.

В конце n -го месяца количество пар кроликов равно числу половозрелых пар (т. е. количеству пар в месяце n – 2 ) плюс числу пар, живых в прошлом месяце (месяц n – 1 ). Число в n -м месяце является n -м числом Фибоначчи. ^[20]

Название «последовательность Фибоначчи» впервые использовал теоретик чисел XIX века Эдуард Лукас . ^[21]

В растущей идеализированной популяции количество пар кроликов образует последовательность Фибоначчи. В конце n- го месяца количество пар равно F _n.

Связь с золотым сечением

Выражение в закрытой форме

Как и любая последовательность , определяемая линейной рекуррентностью с постоянными коэффициентами , числа Фибоначчи имеют выражение в замкнутой форме . Она стала известна как формула Бине , названная в честь французского математика Жака Филиппа Мари Бине , хотя она уже была известна Абрахаму де Муару и Даниэлю Бернулли : ^[22]

$${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}},}$$

где

$${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\,39887\ldots }$$

– золотое сечение , а ψ – его сопряженное число : ^[23]

$${\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\ldots .}$$

Поскольку , эту формулу можно записать и в виде ${\displaystyle \psi =-\varphi ^{-1}}$

$${\displaystyle F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}}.}$$

Чтобы увидеть связь между последовательностью и этими константами, отметим ^{[24] , что} φ и ψ оба являются решениями уравнения , и, таким образом , степени φ и ψ удовлетворяют рекурсии Фибоначчи. Другими словами, ${\textstyle x^{2}=x+1}$ ${\displaystyle x^{n}=x^{n-1}+x^{n-2},}$

$${\displaystyle {\begin{aligned}\varphi ^{n}&=\varphi ^{n-1}+\varphi ^{n-2},\\[3mu]\psi ^{n}&=\psi ^{n-1}+\psi ^{n-2}.\end{aligned}}}$$

Отсюда следует, что для любых значений a и b последовательность, определяемая формулами

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

удовлетворяет той же повторяемости,

$${\displaystyle {\begin{aligned}U_{n}&=a\varphi ^{n}+b\psi ^{n}\\[3mu]&=a(\varphi ^{n-1}+\varphi ^{n-2})+b(\psi ^{n-1}+\psi ^{n-2})\\[3mu]&=a\varphi ^{n-1}+b\psi ^{n-1}+a\varphi ^{n-2}+b\psi ^{n-2}\\[3mu]&=U_{n-1}+U_{n-2}.\end{aligned}}}$$

Если a и b выбраны так, что U ₀ = 0 и U ₁ = 1 , то результирующая последовательность Un должна _быть последовательностью Фибоначчи. Это то же самое, что требовать, чтобы a и b удовлетворяли системе уравнений:

$${\displaystyle \left\{{\begin{aligned}a+b&=0\\\varphi a+\psi b&=1\end{aligned}}\right.}$$

который имеет решение

$${\displaystyle a={\frac {1}{\varphi -\psi }}={\frac {1}{\sqrt {5}}},\quad b=-a,}$$

получение необходимой формулы.

Приняв начальные значения U ₀ и U ₁ за произвольные константы, можно найти более общее решение:

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

где

$${\displaystyle {\begin{aligned}a&={\frac {U_{1}-U_{0}\psi }{\sqrt {5}}},\\[3mu]b&={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}.\end{aligned}}}$$

Расчет путем округления

Поскольку для всех n ≥ 0 , число F _n является ближайшим к . Следовательно, его можно найти округлением , используя ближайшую целочисленную функцию: ${\textstyle \left|{\frac {\psi ^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}$ ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$

$${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil ,\ n\geq 0.}$$

На самом деле ошибка округления очень мала: менее 0,1 для n ≥ 4 и менее 0,01 для n ≥ 8 . Эту формулу легко инвертировать, чтобы найти индекс числа Фибоначчи F :

$${\displaystyle n(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}F\right\rceil ,\ F\geq 1.}$$

Вместо этого использование функции пола дает наибольший индекс числа Фибоначчи, который не превышает F :

$${\displaystyle n_{\mathrm {largest} }(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}(F+1/2)\right\rfloor ,\ F\geq 0,}$$

^[25][26] ${\displaystyle \log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )}$ ${\displaystyle \ln(\varphi )=0.481211\ldots }$ ${\displaystyle \log _{10}(\varphi )=0.208987\ldots }$

Величина

Поскольку F _n асимптотичен для , количество цифр в F _n асимптотично для . Как следствие, для каждого целого числа d > 1 существует либо 4, либо 5 чисел Фибоначчи с d десятичными цифрами. ${\displaystyle \varphi ^{n}/{\sqrt {5}}}$ ${\displaystyle n\log _{10}\varphi \approx 0.2090\,n}$

В более общем смысле, в представлении по основанию b количество цифр в F _n асимптотически равно ${\displaystyle n\log _{b}\varphi ={\frac {n\log \varphi }{\log b}}.}$

Предел последовательных частных

Иоганн Кеплер заметил, что отношения последовательных чисел Фибоначчи сходятся . Он написал, что «как 5 к 8, так и 8 к 13 практически, и как 8 к 13, так почти и 13 к 21», и пришел к выводу, что эти отношения приближаются к золотому сечению ^{[27] [28]} ${\displaystyle \varphi \colon }$

$${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .}$$

Эта сходимость сохраняется независимо от начальных значений и , если только . В этом можно убедиться, используя формулу Бине. Например, начальные значения 3 и 2 генерируют последовательность 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555,... . Соотношение последовательных членов в этой последовательности показывает ту же тенденцию к золотому сечению. ${\displaystyle U_{0}}$ ${\displaystyle U_{1}}$ ${\displaystyle U_{1}=-U_{0}/\varphi }$

В общем, потому что отношения между последовательными числами Фибоначчи приближаются к . ${\displaystyle \lim _{n\to \infty }{\frac {F_{n+m}}{F_{n}}}=\varphi ^{m}}$ ${\displaystyle \varphi }$

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

Разложение полномочий

Поскольку золотое сечение удовлетворяет уравнению

$${\displaystyle \varphi ^{2}=\varphi +1,}$$

это выражение можно использовать для разложения более высоких степеней как линейную функцию от более низких степеней, которую, в свою очередь, можно разложить до линейной комбинации и 1. Полученные рекуррентные соотношения дают числа Фибоначчи в виде линейных коэффициентов : ${\displaystyle \varphi ^{n}}$ ${\displaystyle \varphi }$

$${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}.}$$

доказатьпо n1

$${\displaystyle \varphi ^{n+1}=(F_{n}\varphi +F_{n-1})\varphi =F_{n}\varphi ^{2}+F_{n-1}\varphi =F_{n}(\varphi +1)+F_{n-1}\varphi =(F_{n}+F_{n-1})\varphi +F_{n}=F_{n+1}\varphi +F_{n}.}$$

${\displaystyle \psi =-1/\varphi }$ ${\displaystyle \psi ^{2}=\psi +1}$

$${\displaystyle \psi ^{n}=F_{n}\psi +F_{n-1}.}$$

Эти выражения также верны для n < 1 , если последовательность Фибоначчи F _n расширяется до отрицательных целых чисел с помощью правила Фибоначчи. ${\displaystyle F_{n}=F_{n+2}-F_{n+1}.}$

Идентификация

Формула Бине доказывает, что положительное целое число x является числом Фибоначчи тогда и только тогда, когда хотя бы одно из или является полным квадратом . ^[29] Это связано с тем, что формулу Бине, которую можно записать как , можно умножить и решить как квадратное уравнение с помощью квадратной формулы : ${\displaystyle 5x^{2}+4}$ ${\displaystyle 5x^{2}-4}$ ${\displaystyle F_{n}=(\varphi ^{n}-(-1)^{n}\varphi ^{-n})/{\sqrt {5}}}$ ${\displaystyle {\sqrt {5}}\varphi ^{n}}$ ${\displaystyle \varphi ^{n}}$

$${\displaystyle \varphi ^{n}={\frac {F_{n}{\sqrt {5}}\pm {\sqrt {5{F_{n}}^{2}+4(-1)^{n}}}}{2}}.}$$

Сравнивая это с , следует, что ${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}=(F_{n}{\sqrt {5}}+F_{n}+2F_{n-1})/2}$

$${\displaystyle 5{F_{n}}^{2}+4(-1)^{n}=(F_{n}+2F_{n-1})^{2}\,.}$$

В частности, левая часть представляет собой правильный квадрат.

Матричная форма

Двумерная система линейных разностных уравнений , описывающая последовательность Фибоначчи, имеет вид

$${\displaystyle {F_{k+2} \choose F_{k+1}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{F_{k+1} \choose F_{k}}}$$

$${\displaystyle {\vec {F}}_{k+1}=\mathbf {A} {\vec {F}}_{k},}$$

который дает . Собственные значения матрицы A равны и соответствуют соответствующим собственным векторам ${\displaystyle {\vec {F}}_{n}=\mathbf {A} ^{n}{\vec {F}}_{0}}$ ${\displaystyle \varphi ={\frac {1}{2}}(1+{\sqrt {5}})}$ ${\displaystyle \psi =-\varphi ^{-1}={\frac {1}{2}}(1-{\sqrt {5}})}$

$${\displaystyle {\vec {\mu }}={\varphi \choose 1}}$$

$${\displaystyle {\vec {\nu }}={-\varphi ^{-1} \choose 1}.}$$

$${\displaystyle {\vec {F}}_{0}={1 \choose 0}={\frac {1}{\sqrt {5}}}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}{\vec {\nu }},}$$

n-й

$${\displaystyle {\begin{aligned}{\vec {F}}_{n}&={\frac {1}{\sqrt {5}}}A^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}A^{n}{\vec {\nu }}\\&={\frac {1}{\sqrt {5}}}\varphi ^{n}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}(-\varphi )^{-n}{\vec {\nu }}~\\&={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{n}{\varphi \choose 1}-{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{n}{-\varphi ^{-1} \choose 1},\end{aligned}}}$$

n-выражение в замкнутой форме

$${\displaystyle F_{n}={\cfrac {1}{\sqrt {5}}}\left({\cfrac {1+{\sqrt {5}}}{2}}\right)^{n}-{\cfrac {1}{\sqrt {5}}}\left({\cfrac {1-{\sqrt {5}}}{2}}\right)^{n}.}$$

Эквивалентно, то же самое вычисление может быть выполнено путем диагонализации A посредством использования его собственного разложения :

$${\displaystyle {\begin{aligned}A&=S\Lambda S^{-1},\\A^{n}&=S\Lambda ^{n}S^{-1},\end{aligned}}}$$

n- ${\displaystyle \Lambda ={\begin{pmatrix}\varphi &0\\0&-\varphi ^{-1}\end{pmatrix}}}$ ${\displaystyle S={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}.}$

$${\displaystyle {\begin{aligned}{F_{n+1} \choose F_{n}}&=A^{n}{F_{1} \choose F_{0}}\\&=S\Lambda ^{n}S^{-1}{F_{1} \choose F_{0}}\\&=S{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}S^{-1}{F_{1} \choose F_{0}}\\&={\begin{pmatrix}\varphi &-\varphi ^{-1}\\1&1\end{pmatrix}}{\begin{pmatrix}\varphi ^{n}&0\\0&(-\varphi )^{-n}\end{pmatrix}}{\frac {1}{\sqrt {5}}}{\begin{pmatrix}1&\varphi ^{-1}\\-1&\varphi \end{pmatrix}}{1 \choose 0},\end{aligned}}}$$

что снова дает

$${\displaystyle F_{n}={\cfrac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}.}$$

Матрица A имеет определитель −1 и, следовательно, является унимодулярной матрицей размера 2 × 2 .

Это свойство можно понять с точки зрения представления цепной дроби золотого сечения:

$${\displaystyle \varphi =1+{\cfrac {1}{1+{\cfrac {1}{1+{\cfrac {1}{1+\ddots }}}}}}.}$$

Числа Фибоначчи представляют собой отношение последовательных дробей непрерывной дроби для φ , а матрица, сформированная из последовательных дробей любой цепной дроби, имеет определитель +1 или -1. Матричное представление дает следующее выражение в замкнутой форме для чисел Фибоначчи:

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

Для данного n эта матрица может быть вычислена за O (log n ) арифметических операций, используя возведение в степень методом возведения в квадрат .

Взяв определитель обеих частей этого уравнения, получим тождество Кассини :

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

Более того, поскольку An ^A m = An ^{+ m} для любой квадратной матрицы ^A , можно вывести следующие тождества (они получаются из двух разных коэффициентов произведения матрицы , и второй можно легко вывести из первого по ^{формуле} заменив n на n + 1 ),

$${\displaystyle {\begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1},\\F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}.\end{aligned}}}$$

В частности, при m = n ,

$${\displaystyle {\begin{aligned}F_{2n-1}&={F_{n}}^{2}+{F_{n-1}}^{2}\\[5pt]F_{2n{\phantom {{}-1}}}&=(F_{n-1}+F_{n+1})F_{n}\\[5pt]&=(2F_{n-1}+F_{n})F_{n}\\[5pt]&=(2F_{n+1}-F_{n})F_{n}.\end{aligned}}}$$

Эти последние два тождества позволяют рекурсивно вычислять числа Фибоначчи за O (log n ) арифметических операций. Это соответствует времени вычисления n -го числа Фибоначчи из матричной формулы замкнутой формы, но с меньшим количеством избыточных шагов, если избегать повторного вычисления уже вычисленного числа Фибоначчи (рекурсия с мемоизацией ). ^[30]

Комбинаторные тождества

Комбинаторные доказательства

Большинство тождеств, включающих числа Фибоначчи, можно доказать с помощью комбинаторных аргументов, используя тот факт, который можно интерпретировать как количество (возможно, пустых) последовательностей единиц и двоек, сумма которых равна . Это можно принять за определение с соглашениями , что означает, что не существует такой последовательности, сумма которой равна -1, и , что означает, что пустая последовательность «в сумме» равна 0. Ниже указывается мощность набора : ${\displaystyle F_{n}}$ ${\displaystyle n-1}$ ${\displaystyle F_{n}}$ ${\displaystyle F_{0}=0}$ ${\displaystyle F_{1}=1}$ ${\displaystyle |{...}|}$

${\displaystyle F_{0}=0=|\{\}|}$

${\displaystyle F_{1}=1=|\{()\}|}$

${\displaystyle F_{2}=1=|\{(1)\}|}$

${\displaystyle F_{3}=2=|\{(1,1),(2)\}|}$

${\displaystyle F_{4}=3=|\{(1,1,1),(1,2),(2,1)\}|}$

${\displaystyle F_{5}=5=|\{(1,1,1,1),(1,1,2),(1,2,1),(2,1,1),(2,2)\}|}$

Таким образом, рекуррентное соотношение

$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$

${\displaystyle F_{n}}$

$${\displaystyle F_{n}=|\{(1,...),(1,...),...\}|+|\{(2,...),(2,...),...\}|}$$

${\displaystyle n-2}$ ${\displaystyle n-3}$ ${\displaystyle F_{n-1}}$ ${\displaystyle F_{n-2}}$ ${\displaystyle F_{n-1}+F_{n-2}}$ ${\displaystyle F_{n}}$

Аналогичным образом можно показать, что сумма первых чисел Фибоначчи до n -го равна ( n + 2) -му числу Фибоначчи минус 1. ^[31] В символах:

$${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$$

Это можно увидеть, разделив все последовательности, суммируя их, в зависимости от местоположения первых 2. В частности, каждый набор состоит из тех последовательностей, которые начинаются до двух последних наборов, каждый из которых имеет мощность 1. ${\displaystyle n+1}$ ${\displaystyle (2,...),(1,2,...),...,}$ ${\displaystyle \{(1,1,...,1,2)\},\{(1,1,...,1)\}}$

Следуя той же логике, что и раньше, суммируя мощность каждого набора, мы видим, что

${\displaystyle F_{n+2}=F_{n}+F_{n-1}+...+|\{(1,1,...,1,2)\}|+|\{(1,1,...,1)\}|}$

... где последние два члена имеют значение . Отсюда следует, что . ${\displaystyle F_{1}=1}$ ${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$

Аналогичный аргумент, группирующий суммы по положению первой единицы, а не первых двух, дает еще два тождества:

$${\displaystyle \sum _{i=0}^{n-1}F_{2i+1}=F_{2n}}$$

$${\displaystyle \sum _{i=1}^{n}F_{2i}=F_{2n+1}-1.}$$

нечетным(2 n )четным(2 n + 1)^[32] ${\displaystyle F_{2n-1}}$ ${\displaystyle F_{2n}}$

Чтобы доказать это, можно использовать другой трюк.

$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$

n( n +1)площадей ${\displaystyle F_{n}}$ ${\displaystyle F_{n}\times F_{n+1}}$ ${\displaystyle F_{n},F_{n-1},...,F_{1}}$

Символический метод

Последовательность также рассматривается с использованием символьного метода . ^[33] Точнее, эта последовательность соответствует определяемому комбинаторному классу . Спецификация этой последовательности . Действительно, как указано выше, -е число Фибоначчи равно количеству комбинаторных композиций (упорядоченных разбиений ) с использованием терминов 1 и 2. ${\displaystyle (F_{n})_{n\in \mathbb {N} }}$ ${\displaystyle \operatorname {Seq} ({\mathcal {Z+Z^{2}}})}$ ${\displaystyle n}$ ${\displaystyle n-1}$

Отсюда следует, что обычная производящая функция последовательности Фибоначчи , является рациональной функцией ${\displaystyle \sum _{i=0}^{\infty }F_{i}z^{i}}$ ${\displaystyle {\frac {z}{1-z-z^{2}}}.}$

Индукционные доказательства

Тождества Фибоначчи часто можно легко доказать с помощью математической индукции .

Например, пересмотреть

$${\displaystyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1.}$$

${\displaystyle F_{n+1}}$

${\displaystyle \sum _{i=1}^{n}F_{i}+F_{n+1}=F_{n+1}+F_{n+2}-1}$

и так у нас есть формула для ${\displaystyle n+1}$

$${\displaystyle \sum _{i=1}^{n+1}F_{i}=F_{n+3}-1}$$

Аналогично добавьте к обеим сторонам ${\displaystyle {F_{n+1}}^{2}}$

$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$

$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}+{F_{n+1}}^{2}=F_{n+1}\left(F_{n}+F_{n+1}\right)}$$

$${\displaystyle \sum _{i=1}^{n+1}F_{i}^{2}=F_{n+1}F_{n+2}}$$

Доказательства формулы Бине

Формула Бине

$${\displaystyle {\sqrt {5}}F_{n}=\varphi ^{n}-\psi ^{n}.}$$

Например, чтобы доказать это, обратите внимание, что левая часть, умноженная на, становится ${\textstyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$ ${\displaystyle {\sqrt {5}}}$

$${\displaystyle {\begin{aligned}1+&\varphi +\varphi ^{2}+\dots +\varphi ^{n}-\left(1+\psi +\psi ^{2}+\dots +\psi ^{n}\right)\\&={\frac {\varphi ^{n+1}-1}{\varphi -1}}-{\frac {\psi ^{n+1}-1}{\psi -1}}\\&={\frac {\varphi ^{n+1}-1}{-\psi }}-{\frac {\psi ^{n+1}-1}{-\varphi }}\\&={\frac {-\varphi ^{n+2}+\varphi +\psi ^{n+2}-\psi }{\varphi \psi }}\\&=\varphi ^{n+2}-\psi ^{n+2}-(\varphi -\psi )\\&={\sqrt {5}}(F_{n+2}-1)\\\end{aligned}}}$$

${\textstyle \varphi \psi =-1}$ ${\textstyle \varphi -\psi ={\sqrt {5}}}$

Другие личности

Множество других тождеств можно получить с помощью различных методов. Вот некоторые из них: ^[34]

Личности Кассини и Каталонии

Личность Кассини утверждает, что

$${\displaystyle {F_{n}}^{2}-F_{n+1}F_{n-1}=(-1)^{n-1}}$$

$${\displaystyle {F_{n}}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}{F_{r}}^{2}}$$

личность д'Оканя

$${\displaystyle F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{m-n}}$$

$${\displaystyle F_{2n}={F_{n+1}}^{2}-{F_{n-1}}^{2}=F_{n}\left(F_{n+1}+F_{n-1}\right)=F_{n}L_{n}}$$

Ln — n _-Люкаn

$${\displaystyle F_{3n}=2{F_{n}}^{3}+3F_{n}F_{n+1}F_{n-1}=5{F_{n}}^{3}+3(-1)^{n}F_{n}}$$

$${\displaystyle F_{3n+1}={F_{n+1}}^{3}+3F_{n+1}{F_{n}}^{2}-{F_{n}}^{3}}$$

$${\displaystyle F_{3n+2}={F_{n+1}}^{3}+3{F_{n+1}}^{2}F_{n}+{F_{n}}^{3}}$$

$${\displaystyle F_{4n}=4F_{n}F_{n+1}\left({F_{n+1}}^{2}+2{F_{n}}^{2}\right)-3{F_{n}}^{2}\left({F_{n}}^{2}+2{F_{n+1}}^{2}\right)}$$

сокращения решеткиспециального сита числового поляфакторизации

В более общем плане ^[34]

$${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c-i}{F_{n}}^{i}{F_{n+1}}^{k-i}.}$$

или альтернативно

$${\displaystyle F_{kn+c}=\sum _{i=0}^{k}{k \choose i}F_{c+i}{F_{n}}^{i}{F_{n-1}}^{k-i}.}$$

Поставив в эту формулу k = 2 , снова получим формулы из конца раздела «Матричная форма».

Генерирующая функция

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

$${\displaystyle s(z)=\sum _{k=0}^{\infty }F_{k}z^{k}=0+z+z^{2}+2z^{3}+3z^{4}+\dots .}$$

Этот ряд сходится для любого комплексного числа, удовлетворяющего условиям , и его сумма имеет простой замкнутый вид: ^[35] ${\displaystyle z}$ ${\displaystyle |z|<1/\varphi ,}$

$${\displaystyle s(z)={\frac {z}{1-z-z^{2}}}.}$$

Это можно доказать, умножив на : ${\textstyle (1-z-z^{2})}$

$${\displaystyle {\begin{aligned}(1-z-z^{2})s(z)&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=0}^{\infty }F_{k}z^{k+1}-\sum _{k=0}^{\infty }F_{k}z^{k+2}\\&=\sum _{k=0}^{\infty }F_{k}z^{k}-\sum _{k=1}^{\infty }F_{k-1}z^{k}-\sum _{k=2}^{\infty }F_{k-2}z^{k}\\&=0z^{0}+1z^{1}-0z^{1}+\sum _{k=2}^{\infty }(F_{k}-F_{k-1}-F_{k-2})z^{k}\\&=z,\end{aligned}}}$$

где все члены, включающие for, сокращаются из-за определяющего рекуррентного соотношения Фибоначчи. ${\displaystyle z^{k}}$ ${\displaystyle k\geq 2}$

Разложение на частичные дроби определяется выражением

$${\displaystyle s(z)={\frac {1}{\sqrt {5}}}\left({\frac {1}{1-\varphi z}}-{\frac {1}{1-\psi z}}\right)}$$

сопряженное ${\textstyle \varphi ={\tfrac {1}{2}}\left(1+{\sqrt {5}}\right)}$ ${\displaystyle \psi ={\tfrac {1}{2}}\left(1-{\sqrt {5}}\right)}$

Соответствующая функция является производящей функцией чисел негафибоначчи и удовлетворяет функциональному уравнению ${\textstyle z\mapsto -s\left(-1/z\right)}$ ${\displaystyle s(z)}$

$${\displaystyle s(z)=s\!\left(-{\frac {1}{z}}\right).}$$

При использовании любого из значений 0,01, 0,001, 0,0001 и т. д. первые числа Фибоначчи размещаются в десятичном разложении . Например, ${\displaystyle z}$ ${\displaystyle s(z)}$ ${\displaystyle s(0.001)={\frac {0.001}{0.998999}}={\frac {1000}{998999}}=0.001001002003005008013021\ldots .}$

Взаимные суммы

Бесконечные суммы по обратным числам Фибоначчи иногда можно оценить с помощью тэта-функций . Например, сумму каждого обратного числа Фибоначчи с нечетным индексом можно записать как

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}={\frac {\sqrt {5}}{4}}\;\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{2},}$$

и сумма квадратов обратных чисел Фибоначчи как

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{{F_{k}}^{2}}}={\frac {5}{24}}\!\left(\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}-\vartheta _{4}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{4}+1\right).}$$

Если мы добавим 1 к каждому числу Фибоначчи в первой сумме, получится также замкнутая форма

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{1+F_{2k-1}}}={\frac {\sqrt {5}}{2}},}$$

и существует вложенная сумма квадратов чисел Фибоначчи, дающая обратную величину золотого сечения :

$${\displaystyle \sum _{k=1}^{\infty }{\frac {(-1)^{k+1}}{\sum _{j=1}^{k}{F_{j}}^{2}}}={\frac {{\sqrt {5}}-1}{2}}.}$$

Сумма всех четных обратных чисел Фибоначчи равна ^[36]

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}={\sqrt {5}}\left(L(\psi ^{2})-L(\psi ^{4})\right)}$$

серией Ламберта ${\displaystyle \textstyle L(q):=\sum _{k=1}^{\infty }{\frac {q^{k}}{1-q^{k}}},}$ ${\displaystyle \textstyle {\frac {1}{F_{2k}}}={\sqrt {5}}\left({\frac {\psi ^{2k}}{1-\psi ^{2k}}}-{\frac {\psi ^{4k}}{1-\psi ^{4k}}}\right)\!.}$

Таким образом, обратная константа Фибоначчи равна ^[37]

$${\displaystyle \sum _{k=1}^{\infty }{\frac {1}{F_{k}}}=\sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}+\sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}=3.359885666243\dots }$$

Более того, Ришар Андре-Жаннен доказал иррациональность этого числа. ^[38]

Ряд Миллина дает тождество ^[39]

$${\displaystyle \sum _{k=0}^{\infty }{\frac {1}{F_{2^{k}}}}={\frac {7-{\sqrt {5}}}{2}},}$$

N

$${\displaystyle \sum _{k=0}^{N}{\frac {1}{F_{2^{k}}}}=3-{\frac {F_{2^{N}-1}}{F_{2^{N}}}}.}$$

Простые числа и делимость

Свойства делимости

Каждое третье число последовательности четно (кратно ) и, в более общем смысле, каждое k -е число последовательности кратно F _k . Таким образом, последовательность Фибоначчи является примером последовательности делимости . Фактически, последовательность Фибоначчи удовлетворяет более сильному свойству делимости ^{[40] [41]} ${\displaystyle F_{3}=2}$

$${\displaystyle \gcd(F_{a},F_{b},F_{c},\ldots )=F_{\gcd(a,b,c,\ldots )}\,}$$

НОДнаибольшего общего делителя

В частности, любые три последовательных числа Фибоначчи попарно взаимно просты, поскольку оба и . То есть, ${\displaystyle F_{1}=1}$ ${\displaystyle F_{2}=1}$

${\displaystyle \gcd(F_{n},F_{n+1})=\gcd(F_{n},F_{n+2})=\gcd(F_{n+1},F_{n+2})=1}$

для каждого n .

Каждое простое число p делит число Фибоначчи, которое можно определить по значению p по модулю  5. Если p конгруэнтно 1 или 4 по модулю 5, то p делит F _{p −1} , а если p конгруэнтно 2 или 3 по модулю 5 , то p делит F _{p +1} . Оставшийся случай состоит в том, что p = 5 , и в этом случае p делит F _p .

$${\displaystyle {\begin{cases}p=5&\Rightarrow p\mid F_{p},\\p\equiv \pm 1{\pmod {5}}&\Rightarrow p\mid F_{p-1},\\p\equiv \pm 2{\pmod {5}}&\Rightarrow p\mid F_{p+1}.\end{cases}}}$$

Эти случаи можно объединить в одну некусочную формулу , используя символ Лежандра : ^[42]

$${\displaystyle p\mid F_{p\;-\,\left({\frac {5}{p}}\right)}.}$$

Тестирование на примитивность

Приведенную выше формулу можно использовать в качестве теста на простоту в том смысле, что если

$${\displaystyle n\mid F_{n\;-\,\left({\frac {5}{n}}\right)},}$$

символом Якобиnnnn —число ФибоначчиmбитноеF _m (mod n )

$${\displaystyle {\begin{pmatrix}F_{m+1}&F_{m}\\F_{m}&F_{m-1}\end{pmatrix}}\equiv {\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{m}{\pmod {n}}.}$$

Amмодульного возведения в степень , ^{которое}адаптировать к матрицам^[43]

Простые числа Фибоначчи

Простое число Фибоначчи — это число Фибоначчи, которое является простым . Первые несколько: ^[44]

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ...

Были найдены простые числа Фибоначчи с тысячами цифр, но неизвестно, бесконечно ли их количество. ^[45]

F _kn делится на F _n , поэтому, кроме F ₄ = 3 , любое простое число Фибоначчи должно иметь простой индекс. Поскольку существуют произвольно длинные серии составных чисел , следовательно, существуют также сколь угодно длинные серии составных чисел Фибоначчи.

Никакое число Фибоначчи, большее F ₆ = 8, не может быть на единицу больше или на единицу меньше простого числа. ^[46]

Единственное нетривиальное квадратное число Фибоначчи — 144. ^[47] Аттила Петё доказал в 2001 году, что существует только конечное число совершенных степенных чисел Фибоначчи. ^[48] ​​В 2006 году Ю. Бюжо, М. Миньотт и С. Сиксек доказали, что 8 и 144 являются единственными такими нетривиальными совершенными степенями. ^[49]

1, 3, 21 и 55 — единственные треугольные числа Фибоначчи, гипотеза которых была высказана Верном Хоггаттом и доказана Ло Мином. ^[50]

Ни одно число Фибоначчи не может быть идеальным числом . ^[51] В более общем смысле, никакое число Фибоначчи, кроме 1, не может быть кратно совершенным , ^[52] и никакое соотношение двух чисел Фибоначчи не может быть идеальным. ^[53]

Простые делители

За исключением 1, 8 и 144 ( F ₁ = F ₂ , F ₆ и F ₁₂ ), каждое число Фибоначчи имеет простой делитель, который не является делителем какого-либо меньшего числа Фибоначчи ( теорема Кармайкла ). ^[54] В результате 8 и 144 ( F ₆ и F ₁₂ ) являются единственными числами Фибоначчи, которые являются произведением других чисел Фибоначчи. ^[55]

Делимость чисел Фибоначчи на простое число p связана с символом Лежандра , который оценивается следующим образом: ${\displaystyle \left({\tfrac {p}{5}}\right)}$

$${\displaystyle \left({\frac {p}{5}}\right)={\begin{cases}0&{\text{if }}p=5\\1&{\text{if }}p\equiv \pm 1{\pmod {5}}\\-1&{\text{if }}p\equiv \pm 2{\pmod {5}}.\end{cases}}}$$

Если p — простое число, то

$${\displaystyle F_{p}\equiv \left({\frac {p}{5}}\right){\pmod {p}}\quad {\text{and}}\quad F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p}}.}$$

^{[56] [57]}

Например,

$${\displaystyle {\begin{aligned}({\tfrac {2}{5}})&=-1,&F_{3}&=2,&F_{2}&=1,\\({\tfrac {3}{5}})&=-1,&F_{4}&=3,&F_{3}&=2,\\({\tfrac {5}{5}})&=0,&F_{5}&=5,\\({\tfrac {7}{5}})&=-1,&F_{8}&=21,&F_{7}&=13,\\({\tfrac {11}{5}})&=+1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}}$$

Неизвестно, существует ли простое число p такое, что

$${\displaystyle F_{p-\left({\frac {p}{5}}\right)}\equiv 0{\pmod {p^{2}}}.}$$

Такие простые числа (если они есть) будут называться простыми числами Стены-Солнца-Солнца .

Кроме того, если p ≠ 5 — нечетное простое число, то: ^[58]

$${\displaystyle 5{F_{\frac {p\pm 1}{2}}}^{2}\equiv {\begin{cases}{\tfrac {1}{2}}\left(5\left({\frac {p}{5}}\right)\pm 5\right){\pmod {p}}&{\text{if }}p\equiv 1{\pmod {4}}\\{\tfrac {1}{2}}\left(5\left({\frac {p}{5}}\right)\mp 3\right){\pmod {p}}&{\text{if }}p\equiv 3{\pmod {4}}.\end{cases}}}$$

Пример 1. p = 7 , в этом случае p ≡ 3 (mod 4) и имеем:

$${\displaystyle ({\tfrac {7}{5}})=-1:\qquad {\tfrac {1}{2}}\left(5({\tfrac {7}{5}})+3\right)=-1,\quad {\tfrac {1}{2}}\left(5({\tfrac {7}{5}})-3\right)=-4.}$$

$${\displaystyle F_{3}=2{\text{ and }}F_{4}=3.}$$

$${\displaystyle 5{F_{3}}^{2}=20\equiv -1{\pmod {7}}\;\;{\text{ and }}\;\;5{F_{4}}^{2}=45\equiv -4{\pmod {7}}}$$

Пример 2. p = 11 , в этом случае p ≡ 3 (mod 4) и имеем:

$${\displaystyle ({\tfrac {11}{5}})=+1:\qquad {\tfrac {1}{2}}\left(5({\tfrac {11}{5}})+3\right)=4,\quad {\tfrac {1}{2}}\left(5({\tfrac {11}{5}})-3\right)=1.}$$

$${\displaystyle F_{5}=5{\text{ and }}F_{6}=8.}$$

$${\displaystyle 5{F_{5}}^{2}=125\equiv 4{\pmod {11}}\;\;{\text{ and }}\;\;5{F_{6}}^{2}=320\equiv 1{\pmod {11}}}$$

Пример 3. p = 13 , в этом случае p ≡ 1 (mod 4) и имеем:

$${\displaystyle ({\tfrac {13}{5}})=-1:\qquad {\tfrac {1}{2}}\left(5({\tfrac {13}{5}})-5\right)=-5,\quad {\tfrac {1}{2}}\left(5({\tfrac {13}{5}})+5\right)=0.}$$

$${\displaystyle F_{6}=8{\text{ and }}F_{7}=13.}$$

$${\displaystyle 5{F_{6}}^{2}=320\equiv -5{\pmod {13}}\;\;{\text{ and }}\;\;5{F_{7}}^{2}=845\equiv 0{\pmod {13}}}$$

Пример 4. p = 29 , в этом случае p ≡ 1 (mod 4) и имеем:

$${\displaystyle ({\tfrac {29}{5}})=+1:\qquad {\tfrac {1}{2}}\left(5({\tfrac {29}{5}})-5\right)=0,\quad {\tfrac {1}{2}}\left(5({\tfrac {29}{5}})+5\right)=5.}$$

$${\displaystyle F_{14}=377{\text{ and }}F_{15}=610.}$$

$${\displaystyle 5{F_{14}}^{2}=710645\equiv 0{\pmod {29}}\;\;{\text{ and }}\;\;5{F_{15}}^{2}=1860500\equiv 5{\pmod {29}}}$$

Для нечетного n все нечетные простые делители F _n конгруэнтны 1 по модулю 4, а это означает, что все нечетные делители F _n (как произведения нечетных простых делителей) конгруэнтны 1 по модулю 4. ^[59]

Например,

$${\displaystyle F_{1}=1,\ F_{3}=2,\ F_{5}=5,\ F_{7}=13,\ F_{9}=34=2\cdot 17,\ F_{11}=89,\ F_{13}=233,\ F_{15}=610=2\cdot 5\cdot 61.}$$

Все известные коэффициенты чисел Фибоначчи F ( i ) для всех i < 50000 собраны в соответствующих репозиториях. ^{[60] [61]}

Периодичность по модулю n

Если члены последовательности Фибоначчи взяты по модулю  n , результирующая последовательность будет периодической с периодом не более  6 n . ^[62] Длины периодов для различных n образуют так называемые периоды Пизано . ^[63] Определение общей формулы для периодов Пизано является открытой проблемой , которая включает в себя в качестве подзадачи частный случай проблемы нахождения мультипликативного порядка модулярного целого числа или элемента в конечном поле . Однако для любого конкретного n период Пизано может быть найден как пример обнаружения цикла .

Обобщения

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

Некоторые конкретные примеры, которые в некотором смысле близки к последовательности Фибоначчи, включают:

• Обобщение индекса на отрицательные целые числа для получения чисел негафибоначчи.
• Обобщение индекса на действительные числа с использованием модификации формулы Бине. ^[34]
• Начиная с других целых чисел. Числа Люка имеют L ₁ = 1 , L ₂ = 3 и L _n = L _{n −1} + L _{n −2} . Последовательности Primefree используют рекурсию Фибоначчи с другими отправными точками для создания последовательностей, в которых все числа являются составными.
• Пусть число является линейной функцией (кроме суммы) двух предыдущих чисел. Числа Пелля имеют P n ₌ 2 P _{n −1} + P _{n −2} . Если коэффициенту предыдущего значения присвоено переменное значение x , результатом будет последовательность полиномов Фибоначчи .
• Не добавляя непосредственно предыдущие числа. Последовательность Падована и числа Перрена имеют P ( n ) = P ( n - 2) + P ( n - 3) .
• Генерация следующего числа путем сложения 3 чисел (числа трибоначчи), 4 чисел (числа тетраначчи) или более. Полученные последовательности известны как n-ступенчатые числа Фибоначчи . ^[64]

Приложения

Математика

Числа Фибоначчи представляют собой суммы диагоналей (показаны красным) выровненного слева треугольника Паскаля .

Числа Фибоначчи представляют собой суммы биномиальных коэффициентов на «мелких» диагоналях треугольника Паскаля : ^[65]

$${\displaystyle F_{n}=\sum _{k=0}^{\left\lfloor {\frac {n-1}{2}}\right\rfloor }{\binom {n-k-1}{k}}.}$$

$${\displaystyle {\frac {x}{1-x-x^{2}}}=x+x^{2}(1+x)+x^{3}(1+x)^{2}+\dots +x^{k+1}(1+x)^{k}+\dots =\sum \limits _{n=0}^{\infty }F_{n}x^{n}}$$

${\displaystyle x^{n}}$

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

то есть мы выбираем позиции k двоек из n - k -1 членов. ${\displaystyle {\binom {5}{0}}+{\binom {4}{1}}+{\binom {3}{2}}}$

Использование последовательности Фибоначчи для подсчета составов с ограничением {1, 2}

Эти числа также дают решение некоторых перечислительных задач, ^[66] наиболее распространенной из которых является задача о подсчете количества способов записи данного числа n в виде упорядоченной суммы единиц и двоек (называемых композициями ); существует F _{n +1} способов сделать это (эквивалентно, это также количество разбиений прямоугольника на домино ). Например, существует F ₅₊₁ = F ₆ = 8 способов подняться по лестнице из 5 ступенек, делая по одной или две ступеньки за раз: ${\displaystyle 2\times n}$

На рисунке видно, что 8 можно разложить на 5 (количество способов подняться на 4 ступеньки с последующей одноступенчатой) плюс 3 (количество способов подняться на 3 ступеньки с последующей двойной ступенькой). Те же рассуждения применяются рекурсивно до тех пор, пока не будет достигнута единственная ступень, на которую есть только один способ подняться.

Числа Фибоначчи можно найти разными способами среди множества двоичных строк или, что то же самое, среди подмножеств данного набора.

• Количество двоичных строк длины n без последовательных единиц — это число Фибоначчи F _{n +2} . Например, из 16 двоичных строк длины 4 есть _F6 = 8 без последовательных единиц — это 0000, 0001, 0010, 0100, 0101, 1000, 1001 и 1010. Такие строки являются двоичными представлениями Фиббинарные числа . Эквивалентно, F _{n +2} — это количество подмножеств S из {1, ..., n } без последовательных целых чисел, то есть тех S , для которых { i , i + 1} ⊈ S для каждого i . Биекция с суммами до n +1 заключается в замене 1 на 0 и 2 на 10 и отбрасывании последнего нуля.
• Количество двоичных строк длины n без нечетного количества последовательных единиц — это число Фибоначчи F _{n +1} . Например, из 16 двоичных строк длиной 4 есть F ₅ = 5 без нечетного числа последовательных единиц — это 0000, 0011, 0110, 1100, 1111. Эквивалентно, количество подмножеств S из {1 , ..., n } без нечётного числа последовательных целых чисел — это F _{n +1} . Биекция с суммами до n заключается в замене 1 на 0 и 2 на 11.
• Количество двоичных строк длины n без четного количества последовательных 0 или 1 равно 2 F _n . Например, из 16 двоичных строк длиной 4 есть 2 F ₄ = 6 без четного числа последовательных 0 или 1 — это 0001, 0111, 0101, 1000, 1010, 1110. Существует эквивалент утверждение о подмножествах.
• Юрию Матиясевичу удалось показать, что числа Фибоначчи можно определить с помощью диофантова уравнения , что привело к решению десятой проблемы Гильберта . ^[67]
• Числа Фибоначчи также являются примером полной последовательности . Это означает, что каждое положительное целое число можно записать как сумму чисел Фибоначчи, где любое число используется не более одного раза.
• Более того, каждое положительное целое число можно записать уникальным образом как сумму одного или нескольких различных чисел Фибоначчи таким образом, чтобы эта сумма не включала в себя два последовательных числа Фибоначчи. Это известно как теорема Цекендорфа , а сумма чисел Фибоначчи, удовлетворяющая этим условиям, называется представлением Цекендорфа. Представление числа Цекендорфа можно использовать для получения его кодирования Фибоначчи .
• Начиная с 5, каждое второе число Фибоначчи — это длина гипотенузы прямоугольного треугольника с целыми сторонами, или другими словами, наибольшее число в пифагоровой тройке , полученное по формуле
  $${\displaystyle (F_{n}F_{n+3})^{2}+(2F_{n+1}F_{n+2})^{2}={F_{2n+3}}^{2}.}$$
  Последовательность треугольников Пифагора, полученная по этой формуле, имеет стороны длин (3,4,5), (5,12,13), (16,30,34), (39,80,89), ... . Средняя сторона каждого из этих треугольников представляет собой сумму трёх сторон предыдущего треугольника. ^[68]
• Куб Фибоначчи — это неориентированный граф с числом узлов Фибоначчи, который был предложен в качестве топологии сети для параллельных вычислений .
• Числа Фибоначчи появляются в лемме о кольцах , используемой для доказательства связи между теоремой об упаковке кругов и конформными отображениями . ^[69]

Информатика

Дерево Фибоначчи высотой 6. Коэффициенты баланса зеленые; высоты красные.
Ключами в левом позвоночнике являются числа Фибоначчи.

• Числа Фибоначчи важны при вычислительном анализе алгоритма Евклида во время выполнения для определения наибольшего общего делителя двух целых чисел: в худшем случае входными данными для этого алгоритма является пара последовательных чисел Фибоначчи. ^[70]
• Числа Фибоначчи используются в многофазной версии алгоритма сортировки слиянием , в которой несортированный список делится на два списка, длина которых соответствует последовательным числам Фибоначчи, — путем деления списка так, чтобы две части имели длину в приблизительной пропорции φ . Реализация многофазной сортировки слиянием на ленточном накопителе была описана в книге «Искусство компьютерного программирования» .
• Дерево Фибоначчи — это двоичное дерево , дочерние деревья которого (рекурсивно) отличаются по высоте ровно на 1. Таким образом, это дерево AVL , причем дерево с наименьшим количеством узлов для заданной высоты — самое «тонкое» дерево AVL. Эти деревья имеют количество вершин, равное числу Фибоначчи минус один, что является важным фактом при анализе деревьев AVL. ^[71]
• Числа Фибоначчи используются некоторыми генераторами псевдослучайных чисел .
• Числа Фибоначчи возникают при анализе структуры данных кучи Фибоначчи .
• Метод одномерной оптимизации, называемый методом поиска Фибоначчи , использует числа Фибоначчи. ^[72]
• Ряд чисел Фибоначчи используется для дополнительного сжатия с потерями в формате аудиофайлов IFF 8SVX , используемом на компьютерах Amiga . Числовой ряд компонует исходную звуковую волну аналогично логарифмическим методам, таким как μ-law . ^{[73] [74]}
• Некоторые команды Agile используют модифицированную серию под названием «Модифицированная серия Фибоначчи» при планировании покера в качестве инструмента оценки. Planning Poker — формальная часть Scaled Agile Framework . ^[75]
• Кодирование Фибоначчи
• Кодирование Негафибоначчи

Природа

Головка желтой ромашки демонстрирует расположение из 21 (синей) и 13 (голубых) спиралей. Такие схемы, включающие последовательные числа Фибоначчи, встречаются на самых разных предприятиях.

Последовательности Фибоначчи появляются в биологических условиях, ^[76] таких как ветвление деревьев, расположение листьев на стебле , плоды ананаса , [ ^77] цветение артишока , расположение сосновой шишки , ^[78] и семейство дерево пчел . ^{[79] [80]} Кеплер указал на присутствие последовательности Фибоначчи в природе, используя ее для объяснения ( связанной с золотым сечением ) пятиугольной формы некоторых цветов. ^[81] У полевых ромашек чаще всего лепестки соответствуют числам Фибоначчи. ^[82] В 1830 г. К. Ф. Шимпер и А. Браун обнаружили, что парастихи (спиральный филлотаксис ) растений часто выражаются в виде фракций, включающих числа Фибоначчи. ^[83]

Пшемыслав Прусинкевич выдвинул идею о том, что реальные примеры можно частично понимать как выражение определенных алгебраических ограничений на свободные группы , в частности, как определенные грамматики Линденмайера . ^[84]

Иллюстрация модели Фогеля для n = 1...500

Модель рисунка цветков на головке подсолнуха была предложена Хельмутом Фогелем  [ де ] в 1979 году. ^[85] Она имеет вид

$${\displaystyle \theta ={\frac {2\pi }{\varphi ^{2}}}n,\ r=c{\sqrt {n}}}$$

где n — порядковый номер цветка, а c — постоянный масштабный коэффициент; таким образом, цветки лежат на спирали Ферма . Угол расхождения , примерно 137,51°, представляет собой золотой угол , делящий круг в золотом сечении. Поскольку это соотношение иррационально, ни один цветочек не имеет соседа, находящегося точно под таким же углом от центра, поэтому соцветия группируются эффективно. Поскольку рациональные приближения к золотому сечению имеют форму F (  j ): F (  j + 1) , ближайшие соседи цветка с номером n — это соседи с номером n ± F (  j ) для некоторого индекса j , который зависит от r , расстояние от центра. Подсолнухи и подобные цветы чаще всего имеют спирали цветков, направленные по часовой стрелке и против часовой стрелки, в количестве соседних чисел Фибоначчи, ^[86] обычно отсчитываемых по самому дальнему диапазону радиусов. ^[87]

Числа Фибоначчи также появляются в родословных идеализированных медоносных пчел согласно следующим правилам:

• Если яйцо откладывает неспаренная самка, из него вылупляется самец или трутень .
• Однако если яйцо было оплодотворено самцом, из него вылупляется самка.

Таким образом, у пчелы-самца всегда один родитель, а у пчелы-самки – два. Если проследить родословную любой пчелы-самца (1 пчелы), у него будет 1 родитель (1 пчела), 2 бабушки и дедушки, 3 прадеда и прадеда, 5 прапрадедов и т. д. Эта последовательность чисел родителей является последовательностью Фибоначчи. Число предков на каждом уровне, F _n , равно количеству предков женского пола, равному F _{n -1} , плюс числу предков мужского пола, равному F _{n -2} . ^[88] Это основано на нереалистичном предположении, что предки на каждом уровне в остальном не связаны друг с другом.

Число возможных предков по линии наследования Х-хромосомы в данном наследственном поколении соответствует последовательности Фибоначчи. (По Хатчисону, Л. «Выращивание генеалогического древа: сила ДНК в реконструкции семейных отношений». ^[89] ).

Было замечено, что число возможных предков в линии наследования Х-хромосомы человека в данном наследственном поколении также соответствует последовательности Фибоначчи. ^[89] Особь мужского пола имеет Х-хромосому, которую он получил от матери, и Y-хромосому , которую он получил от отца. Самец считается «происхождением» его собственной Х-хромосомы ( ), а в поколении его родителей его Х-хромосома произошла от единственного родителя ( ) . Мать мужчины получила одну Х-хромосому от своей матери (бабушки сына по материнской линии) и одну от отца (дедушки сына по материнской линии), поэтому два дедушки и бабушки внесли свой вклад в Х-хромосому потомка мужского пола ( ) . Дедушка по материнской линии получил Х-хромосому от своей матери, а бабушка по материнской линии получила Х-хромосомы от обоих своих родителей, поэтому три прадеда и прадеда внесли свой вклад в Х-хромосому потомка мужского пола ( ) . Пять прапрадедов и прадедов внесли свой вклад в Х-хромосому потомка мужского пола ( ) и т. д. (Это предполагает, что все предки данного потомка независимы, но если какая-либо генеалогия прослеживается достаточно далеко назад во времени, предки начинают появляться в нескольких линиях). генеалогии, пока в конце концов во всех линиях генеалогии не появится основатель популяции .) ${\displaystyle F_{1}=1}$ ${\displaystyle F_{2}=1}$ ${\displaystyle F_{3}=2}$ ${\displaystyle F_{4}=3}$ ${\displaystyle F_{5}=5}$

Другой

• В оптике , когда луч света падает под углом через две сложенные друг на друга прозрачные пластины из разных материалов с разными показателями преломления , он может отражаться от трех поверхностей: верхней, средней и нижней поверхностей двух пластин. Количество различных траекторий луча, которые имеют k отражений, для k > 1 , является k -м числом Фибоначчи. (Однако, когда k = 1 , существует три пути отражения, а не два, по одному на каждую из трех поверхностей.) ^[90]
• Уровни коррекции Фибоначчи широко используются в техническом анализе для торговли на финансовых рынках.
• Поскольку коэффициент перевода миль в километры 1,609344 близок к золотому сечению, разложение расстояния в милях на сумму чисел Фибоначчи становится почти суммой километров, когда числа Фибоначчи заменяются их преемниками. Этот метод заключается в сдвиге регистра числа по основанию 2 в базе золотого сечения φ . Чтобы преобразовать километры в мили, вместо этого сдвиньте регистр вниз по последовательности Фибоначчи. ^[91]
• Измеренные значения напряжений и токов в цепи бесконечной цепи резисторов (также называемой резисторной лестницей или бесконечной последовательно-параллельной цепью) следуют последовательности Фибоначчи. Промежуточные результаты сложения чередующихся рядов и параллельных сопротивлений дают дроби, состоящие из последовательных чисел Фибоначчи. Эквивалентное сопротивление всей цепи равно золотому сечению. ^[92]
• Браш и др. 2012 год показывает, как обобщенная последовательность Фибоначчи также может быть связана с областью экономики . ^[93] В частности, показано, как обобщенная последовательность Фибоначчи входит в функцию управления задач динамической оптимизации на конечном интервале времени с одним состоянием и одной управляющей переменной. Процедура проиллюстрирована на примере, который часто называют моделью экономического роста Брока – Мирмана.
• Марио Мерц включил последовательность Фибоначчи в некоторые из своих работ, начиная с 1970 года. ^[94]
• Джозеф Шиллингер (1895–1943) разработал систему композиции , в которой в некоторых мелодиях используются интервалы Фибоначчи; он рассматривал их как музыкальный аналог сложной гармонии, очевидной в природе. ^[95] См. также Золотое сечение § Музыка .

Смотрите также

• Ассоциация Фибоначчи  - Организация по исследованию чисел Фибоначчи.
• Числа Фибоначчи в популярной культуре
• Слово Фибоначчи  - двоичная последовательность из повторения Фибоначчи.
• Случайная последовательность Фибоначчи  – рандомизированная математическая последовательность, основанная на последовательности Фибоначчи.
• Массив Витхоффа  - бесконечная матрица целых чисел, полученная из последовательности Фибоначчи.

Рекомендации

Пояснительные сноски

1. «Для четырех вариаций метров двух [и] трех при смешивании получается пять. Для пяти вариаций двух ранее - трех [и] четырех при смешивании получается восемь. Таким образом, для шести [вариаций] ] из четырех [и] из пяти при смешивании получается тринадцать. И таким образом, при смешивании двух предыдущих метров семь мораэ [это] двадцать один. Таким образом, этому процессу следует следовать во всех матра-вриттах ". ^[13]

Цитаты

1. Слоан, Нью-Джерси (редактор), «Последовательность A000045 (числа Фибоначчи: F (n) = F (n-1) + F (n-2) с F (0) = 0 и F (1) = 1) ", Электронная энциклопедия целочисленных последовательностей , Фонд OEIS.
2. Goonatilake, Сусанта (1998), На пути к глобальной науке, Indiana University Press, стр. 126, ISBN 978-0-253-33388-9
3. Сингх, Пармананд (1985), «Так называемые числа Фибоначчи в древней и средневековой Индии», Historia Mathematica , 12 (3): 229–44, doi : 10.1016/0315-0860(85)90021-7
4. Кнут, Дональд (2006), Искусство компьютерного программирования, том. 4. Генерация всех деревьев – История комбинаторной генерации, Аддисон-Уэсли, с. 50, ISBN 978-0-321-33570-8, было естественно рассмотреть множество всех последовательностей [L] и [S], имеющих ровно m долей. ...их ровно Fm+1. Например, 21 последовательность при m = 7 : [выдает список]. Таким образом, индийские просодисты открыли последовательность Фибоначчи, как мы наблюдали в разделе 1.2.8 (из версии 1).
5. Сиглер 2002, стр. 404–05.
6. Лукас 1891, с. 3.
7. Бек и Геохеган 2010.
8. Бона 2011, с. 180.
9. Кнут, Дональд (1968), Искусство компьютерного программирования, том. 1, Аддисон Уэсли, с. 100, ISBN 978-81-7758-754-8, До того, как Фибоначчи написал свою работу, последовательность Fn уже обсуждалась индийскими учеными, которые давно интересовались ритмическими узорами... и Гопала (до 1135 г. н. э.), и Хемачандра (ок. 1150 г.) упоминали числа 1, 2, 3,5,8,13,21 явно [см. P. Singh Historia Math 12 (1985) 229–44]», стр. 100 (3-е изд.) ...
10. Ливио 2003, с. 197.
11. Агравала, В.С. (1969),Паниникалина Бхаратаварша (Ген.). Варанаси-I: Чоукхамба Видьябхаван , Садгуруши Шья пишет, что Пингала был младшим братом Панини [Агравала 1969, lb]. Существует альтернативное мнение, что он приходился Панини дядей по материнской линии [Винаясагар 1965, Предисловие, 121]. ... Агравала [1969, 463–76] после тщательного расследования, в котором он рассмотрел взгляды более ранних ученых, пришел к выводу, что Панини жил между 480 и 410 годами до нашей эры.
12. Сингх, Пармананд (1985), «Так называемые числа Фибоначчи в древней и средневековой Индии», Historia Mathematica , Academic Press , 12 (3): 232, doi : 10.1016/0315-0860(85)90021-7
13. Веланкар, HD (1962),«Vrttajātisamuccaya» Кави Вираханки , Джодхпур: Институт восточных исследований Раджастана, стр. 101
14. Ливио 2003, с. 197–198.
15. Шах, Джаянт (1991), «История комбинаторики Пингалы» (PDF) , Северо-Восточный университет : 41 , получено 4 января 2019 г.
16. Сиглер 2002, стр. 404–405.
17. «Liber Abaci Фибоначчи (Книга вычислений)», Университет Юты , 13 декабря 2009 г. , получено 28 ноября 2018 г.
18. Хеменуэй, Прия (2005), Божественная пропорция: Фи в искусстве, природе и науке , Нью-Йорк: Стерлинг, стр. 20–21, ISBN 1-4027-3522-7
19. Нотт, Рон (25 сентября 2016 г.), «Числа Фибоначчи и золотое сечение в природе - 1», Университет Суррея , получено 27 ноября 2018 г.
20. Нотт, Рон, Кролики Фибоначчи, Факультет инженерных и физических наук Университета Суррея
21. Гарднер, Мартин (1996), Математический цирк , Математическая ассоциация Америки, стр. 153, ISBN 978-0-88385-506-5По иронии судьбы , Леонардо, внесшего ценный вклад в математику, помнят сегодня главным образом потому, что французский теоретик чисел XIX века Эдуард Люка... присвоил имя Фибоначчи числовой последовательности, которая появляется в тривиальной задаче в Liber abaci.
22. Бойтельспехер, Альбрехт; Петри, Бернхард (1996), «Фибоначчи-Цален», Der Goldene Schnitt , Vieweg+Teubner Verlag, стр. 87–98, doi : 10.1007/978-3-322-85165-9_6
23. Болл 2003, с. 156.
24. Болл 2003, стр. 155–156.
25. Слоан, Нью-Джерси (редактор), «Последовательность A002390 (десятичное разложение натурального логарифма золотого сечения)», Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS
26. Слоан, Нью-Джерси (редактор), «Последовательность A097348 (десятичное расширение arccsch (2) / log (10))», Онлайн -энциклопедия целочисленных последовательностей , Фонд OEIS
27. Кеплер, Йоханнес (1966), Новогодний подарок: на шестиугольном снегу , Oxford University Press, стр. 92, ISBN 978-0-19-858120-8
28. Strena seu de Nive Sexangula , 1611 г.
29. Гессель, Ира (октябрь 1972 г.), «Фибоначчи - это квадрат» (PDF) , The Fibonacci Quarterly , 10 (4): 417–19 , получено 11 апреля 2012 г.
30. Дейкстра, Эдсгер В. (1978), В честь Фибоначчи (PDF)
31. Лукас 1891, с. 4.
32. Воробьев, Николай Николаевич; Мартин, Мирча (2002), «Глава 1», Числа Фибоначчи , Birkhäuser, стр. 5–6, ISBN 978-3-7643-6135-8
33. Флажоле, Филипп; Седжвик, Роберт (2009), Аналитическая комбинаторика , Издательство Кембриджского университета, стр. 42, ISBN 978-0521898065
34. Weisstein, Эрик В. , «Число Фибоначчи», MathWorld
35. Глейстер, П. (1995), «Степенной ряд Фибоначчи», The Mathematical Gazette , 79 (486): 521–25, doi : 10.2307/3618079, JSTOR  3618079, S2CID  116536130
36. Ландау (1899), цитируется по Борвейну, стр. 95, упражнение 3b.
37. Слоан, Нью-Джерси (редактор), «Последовательность A079586 (десятичное разложение Sum_{k>=1} 1/F(k), где F(k) — k-е число Фибоначчи)», Электронная энциклопедия Целочисленные последовательности , Фонд OEIS
38. Андре-Жаннен, Ришар (1989), «Иррациональность некоторых инверсий некоторых повторяющихся сюит», Comptes Rendus de l'Académie des Sciences, Série I , 308 (19): 539–41, MR  0999451
39. Хонсбергер, Росс (1985), «Серия Миллина», Mathematical Gems III , Dolciani Mathematical Expositions, vol. 9, Американское математическое общество, стр. 135–136, ISBN. 9781470457181
40. Рибенбойм, Пауло (2000), Мои числа, мои друзья , Springer-Verlag
41. Су, Фрэнсис Э (2000), «НОД Фибоначчи, пожалуйста», Mudd Math Fun Facts и др., HMC, заархивировано из оригинала 14 декабря 2009 г. , получено 23 февраля 2007 г.
42. Уильямс, ХК (1982), «Заметки о факторе Фибоначчи », Canadian Mathematical Bulletin , 25 (3): 366–70, doi : 10.4153/CMB-1982-053-0 , hdl : 10338.dmlcz/137492 , МР  0668957 ${\displaystyle F_{p-\varepsilon }/p}$. Уильямс называет это свойство «хорошо известным».
43. Простые числа , Ричард Крэндалл, Карл Померанс, Спрингер, второе издание, 2005, стр. 142.
44. Слоан, Нью-Джерси (редактор), «Последовательность A005478 (простые числа Фибоначчи)», Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS
45. Диаконис, Перси (2018), «Вероятность чисел Фибоначчи» (PDF) , Батлер, Стив ; Купер, Джошуа; Херлберт, Гленн (ред.), Связи в дискретной математике: прославление работы Рона Грэма , Cambridge University Press, стр. 1–12, ISBN 978-1-107-15398-1, МР  3821829
46. Хонсбергер, Росс (1985), «Математические жемчужины III», Математические экспозиции AMS Dolciani (9): 133, ISBN 978-0-88385-318-4
47. Кон, JHE (1964), «О квадратных числах Фибоначчи», Журнал Лондонского математического общества , 39 : 537–540, doi : 10.1112/jlms/s1-39.1.537, MR  0163867
48. Петё, Аттила (2001), «Диофантовые свойства линейных рекурсивных последовательностей II», Acta Mathematica Academiae Paedagogicae Nyíregyháziensis , 17 : 81–96
49. Бюжо, Ю; Миньотт, М; Сиксек, С. (2006), «Классические и модульные подходы к экспоненциальным диофантовым уравнениям. И. Фибоначчи и совершенные степени Лукаса», Ann. Математика. , 2 (163): 969–1018, arXiv : math/0403046 , Bibcode : 2004math......3046B, doi : 10.4007/annals.2006.163.969, S2CID  10266596
50. Луо, Мин (1989), «О треугольных числах Фибоначчи» (PDF) , Кварта Фибоначчи. , 27 (2): 98–108
51. Лука, Флориан (2000), «Совершенные числа Фибоначчи и Люка», Rendiconti del Circolo Matematico di Palermo , 49 (2): 313–18, doi : 10.1007/BF02904236, ISSN  1973-4409, MR  1765401, S2CID  121789033
52. Броган, Кевин А.; Гонсалес, Маркос Х.; Льюис, Райан Х.; Лука, Флориан; Мехия Уге, В. Яницио; Тогбе, Ален (2011), «Не существует кратно совершенных чисел Фибоначчи», Целые числа , 11a : A7, MR  2988067
53. Лука, Флориан; Мехия Уге, В. Яницио (2010), «О совершенных числах, которые представляют собой отношения двух чисел Фибоначчи», Annales Mathematicae в Informaticae , 37 : 107–24, ISSN  1787-6117, MR  2753031
54. Нотт, Рон, Числа Фибоначчи, Великобритания: Суррей
55. Слоан, Нью-Джерси (редактор), «Последовательность A235383 (числа Фибоначчи, которые являются произведением других чисел Фибоначчи)», Онлайн -энциклопедия целочисленных последовательностей , Фонд OEIS
56. Рибенбойм, Пауло (1996), Новая книга рекордов простых чисел , Нью-Йорк: Springer, стр. 64, ISBN 978-0-387-94457-9
57. Леммермейер 2000, стр. 73–74, упр. 2.25–28.
58. Леммермейер 2000, стр. 73–74, упр. 2.28.
59. Леммермейер 2000, стр. 73, упр. 2.27.
60. Факторизации Фибоначчи и Лукаса, Мерсеннуссобирает все известные факторы F ( i ) с i <10000 .
61. Факторы чисел Фибоначчи и Люка, Red golpeсобирает все известные факторы F ( i ) с 10000 < i <50000 .
62. Фрейд, Питер; Браун, Кевин С. (1993), «Проблемы и решения: решения: E3410», The American Mathematical Monthly , 99 (3): 278–79, doi : 10.2307/2325076, JSTOR  2325076
63. Слоан, Нью-Джерси (ред.), «Последовательность A001175 (периоды Пизано (или числа Пизано): период чисел Фибоначчи по модулю n)», Интернет -энциклопедия целочисленных последовательностей , Фонд OEIS
64. Лю, Кебо; Ван, Джун (2006), «k-шаговая последовательность Фибоначчи по модулю m», Utilitas Mathematica , 71 : 169–177, MR  2278830
65. Лукас 1891, с. 7.
66. Стэнли, Ричард (2011), Перечислительная комбинаторика I (2-е изд.) , Cambridge Univ. Пресс, с. 121, Пример 1.35, ISBN 978-1-107-60262-5
67. Харизанов, Валентина (1995), «Обзор Юрия В. Матиясевича, десятая проблема Хиберта», Modern Logic , 5 (3): 345–55
68. Паньи, Дэвид (сентябрь 2001 г.), «Фибоначчи встречает Пифагора», Математика в школе , 30 (4): 39–40, JSTOR  30215477
69. Стивенсон, Кеннет (2005), Введение в упаковку кругов: теория дискретных аналитических функций , Cambridge University Press, ISBN 978-0-521-82356-2, МР  2131318; особенно см. лемму 8.2 (Лемма о кольце), стр. 73–74, и Приложение B, Лемма о кольце, стр. 318–321.
70. Кнут, Дональд Э (1997), Искусство компьютерного программирования , том. 1: Фундаментальные алгоритмы (3-е изд.), Аддисон – Уэсли, с. 343, ISBN 978-0-201-89683-1
71. Адельсон-Вельский, Георгий; Ландис, Евгений (1962), «Алгоритм организации информации», Известия Академии наук СССР (на русском языке), 146 : 263–266.Английский перевод Майрона Дж. Риччи в «Советской математике» - Доклады , 3:1259–1263, 1962.
72. Авриэль, М; Уайльд, ди-джей (1966), «Оптимальность метода симметричного поиска Фибоначчи», Fibonacci Quarterly (3): 265–69
73. Справочное руководство по ядру Amiga ROM , Аддисон-Уэсли, 1991 г.
74. "МКФ", Мультимедиа Wiki
75. Дин Леффингвелл (01 июля 2021 г.), Story, Scaled Agile Framework , получено 15 августа 2022 г.
76. Дуади, С; Кудер, Ю. (1996), «Филлотаксис как динамический процесс самоорганизации» (PDF) , Journal of Theoretical Biology , 178 (3): 255–74, doi : 10.1006/jtbi.1996.0026, заархивировано из оригинала (PDF) на сайте 26 мая 2006 г.
77. Джонс, Джуди; Уилсон, Уильям (2006), «Наука», Неполное образование , Ballantine Books, стр. 544, ISBN 978-0-7394-7582-9
78. Бруссо, А. (1969), «Статистика Фибоначчи в хвойных деревьях», Fibonacci Quarterly (7): 525–32
79. «Оценки за код да Винчи: B–», Математика , Информатика для развлечения: CS4FN
80. Скотт, TC; Маркетос, П. (март 2014 г.), О происхождении последовательности Фибоначчи (PDF) , Архив истории математики MacTutor , Университет Сент-Эндрюс
81. Ливио 2003, с. 110.
82. Ливио 2003, стр. 112–13.
83. Варенн, Франк (2010), Formaliser le vivant - Lois, Théories, Modeles (на французском языке), Hermann, p. 28, ISBN 9782705678128, получено 30 октября 2022 г. , En 1830, К. Ф. Шимпер и А. Браун [...]. Ils montraient que si l'on представляет этот угол расхождения по одной дроби, отражающей число туров по фейлю ([...]), на томбе, регулируемом по номерам сюиты Фибоначчи для нумератора [...] .
84. Прусинкевич, Пшемыслав; Ханан, Джеймс (1989), Системы Линденмайера, фракталы и растения (конспекты лекций по биоматематике) , Springer-Verlag , ISBN 978-0-387-97092-9
85. Фогель, Хельмут (1979), «Лучший способ построить головку подсолнечника», Mathematical Biosciences , 44 (3–4): 179–89, doi : 10.1016/0025-5564(79)90080-4
86. Ливио 2003, с. 112.
87. Прусинкевич, Пшемыслав ; Линденмайер, Аристид (1990), «4», Алгоритмическая красота растений, Springer-Verlag, стр. 101–107, ISBN 978-0-387-97297-8
88. «Последовательность Фибоначчи, как она проявляется в природе» (PDF) , The Fibonacci Quarterly , 1 (1): 53–56, 1963
89. Хатчисон, Люк (сентябрь 2004 г.), «Выращивание генеалогического древа: сила ДНК в реконструкции семейных отношений» (PDF) , Труды Первого симпозиума по биоинформатике и биотехнологии (BIOT-04) , получено 3 сентября 2016 г.
90. Ливио 2003, стр. 98–99.
91. "Представление Цекендорфа", Энциклопедия математики
92. Патранабис, Д.; Дана, С.К. (декабрь 1985 г.), «Диагностика неисправностей с одним шунтом посредством измерения затухания на клеммах и использования чисел Фибоначчи», IEEE Transactions on Instrumentation and Measurement , IM-34 (4): 650–653, Bibcode : 1985ITIM...34. .650P, doi : 10.1109/tim.1985.4315428, S2CID  35413237
93. Браш, Т. фон; Бистрем, Дж.; Листад, Л. П. (2012), «Оптимальное управление и последовательность Фибоначчи», Журнал теории оптимизации и приложений , 154 (3): 857–78, doi : 10.1007/s10957-012-0061-2, hdl : 11250/180781 , S2CID  8550726
94. Ливио 2003, с. 176.
95. Ливио 2003, с. 193.

Цитируемые работы

• Болл, Кейт М. (2003), «8: новый взгляд на кроликов Фибоначчи», « Странные кривые, подсчет кроликов и другие математические исследования» , Принстон, Нью-Джерси: Princeton University Press , ISBN 978-0-691-11321-0.
• Бек, Матиас; Геогеган, Росс (2010), Искусство доказательства: базовая подготовка для более глубокой математики , Нью-Йорк: Springer, ISBN 978-1-4419-7022-0.
• Бона, Миклош (2011), Прогулка по комбинаторике (3-е изд.), Нью-Джерси: World Scientific, ISBN 978-981-4335-23-2.
• Борвейн, Джонатан М .; Борвейн, Питер Б. (июль 1998 г.), Пи и годовое собрание: исследование аналитической теории чисел и сложности вычислений, Wiley, стр. 91–101, ISBN 978-0-471-31515-5
• Леммермейер, Франц (2000), Законы взаимности: от Эйлера до Эйзенштейна , Монографии Springer по математике, Нью-Йорк: Springer, ISBN 978-3-540-66957-9.
• Ливио, Марио (2003) [2002], Золотое сечение: История Фи, самого удивительного числа в мире (первое издание в мягкой обложке), Нью-Йорк: Broadway Books , ISBN 0-7679-0816-3
• Лукас, Эдуард (1891), Théorie des nombres (на французском языке), vol. 1, Париж: Готье-Виллар.
• Сиглер, Л.Е. (2002), Liber Abaci Фибоначчи: перевод на современный английский книги Леонардо Пизано по расчетам , источникам и исследованиям по истории математики и физических наук, Springer, ISBN 978-0-387-95419-6

Внешние ссылки

• Подсолнухи и Фибоначчи - Numberphile на YouTube
• Периоды последовательностей Фибоначчи Mod m на MathPages
• Ученые нашли ключ к образованию спиралей Фибоначчи в природе
• Последовательность Фибоначчи в программе «В наше время» на BBC
• «Числа Фибоначчи», Математическая энциклопедия , EMS Press , 2001 [1994]
• Последовательность OEIS A000045 (числа Фибоначчи)