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

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

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

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

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

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

Числа Фибоначчи можно определить с помощью рекуррентного соотношения ^[8] и для n > 1 .$${\displaystyle F_{0}=0,\quad F_{1}=1,}$$$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$

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

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

Ф 0	Ф 1	Ф 2	Ф 3	Ф 4	Ф 5	Ф 6	Ф 7	Ф 8	Ф 9	Ф 10	Ф 11	Ф 12	Ф 13	Ф 14	Ф 15	Ф 16	Ф 17	Ф 18	Ф 19
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

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

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

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

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

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

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

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

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

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

$${\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 }$$

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

$${\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}}.}$$

Чтобы увидеть связь между последовательностью и этими константами, ^[27] обратите внимание, что φ и ψ являются решениями уравнения , и, таким образом, степени φ и ψ удовлетворяют рекурсии Фибоначчи. Другими словами,${\textstyle х^{2}=х+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 , то результирующая последовательность U _n должна быть последовательностью Фибоначчи. Это то же самое, что требовать, чтобы a и b удовлетворяли системе уравнений:

$${\displaystyle \left\{{\begin{align}a+b&=0\\\varphi a+\psi b&=1\end{align}}\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{align}a&={\frac {U_{1}-U_{0}\psi }{\sqrt {5}}},\\[3mu]b&={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}.\end{align}}}$$

Так как для всех 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.}$$

Фактически, ошибка округления быстро становится очень маленькой по мере роста n , будучи менее 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 : где , , ^[28] и . ^[29]$${\displaystyle n_{\mathrm {самый большой} }(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}(F+1/2)\right\rfloor ,\ F\geq 0,}$$${\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 почти», и пришел к выводу, что эти отношения приближаются к золотому сечению ^{[30] [31]}${\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. Полученные рекуррентные соотношения дают числа Фибоначчи в качестве линейных коэффициентов : Это уравнение можно доказать индукцией по n ≥ 1 : Для также имеет место и также имеет место${\displaystyle \varphi ^{n}}$${\displaystyle \varphi }$$${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}.}$$$${\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 является числом Фибоначчи тогда и только тогда, когда хотя бы одно из или является полным квадратом . ^[32] Это происходит потому, что формула Бине, которая может быть записана как , может быть умножена на и решена как квадратное уравнение с помощью квадратной формулы :${\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 ={\tfrac {1}{2}}{\bigl (}1+{\sqrt {5}}~\!{\bigr )}}$${\displaystyle \psi =-\varphi ^{-1}={\tfrac {1}{2}}{\bigl (}1-{\sqrt {5}}~\!{\bigr )}}$$${\displaystyle {\vec {\mu }}={\varphi \choose 1},\quad {\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},\\[3mu]A^{n}&=S\Lambda ^{n}S^{-1},\end{aligned}}}$$

где

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

Таким образом, замкнутое выражение для n- го элемента ряда Фибоначчи имеет вид

$${\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 }}}}}}.}$$

Подходящие дроби непрерывной дроби для φ являются отношениями последовательных чисел Фибоначчи: φ _n = F _{n +1} / F _n является n -й подходящей дробью, а ( n  + 1) -ю подходящую дробь можно найти из рекуррентного соотношения φ _{n +1} = 1 + 1 / φ _n . ^[33] Матрица, образованная из последовательных подходящих дробей любой непрерывной дроби, имеет определитель +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}.}$$

Более того, поскольку A ⁿ A ^m = A ^{n + m} для любой квадратной матрицы A , можно вывести следующие тождества (они получаются из двух различных коэффициентов матричного произведения , и можно легко вывести второе из первого, заменив n на n + 1 ),$${\displaystyle {\begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1},\\[3mu]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}\\[6mu]F_{2n{\phantom {{}-1}}}&=(F_{n-1}+F_{n+1})F_{n}\\[3mu]&=(2F_{n-1}+F_{n})F_{n}\\[3mu]&=(2F_{n+1}-F_{n})F_{n}.\end{aligned}}}$$

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

Большинство тождеств, включающих числа Фибоначчи, можно доказать с помощью комбинаторных аргументов, используя тот факт, что можно интерпретировать как число (возможно, пустых) последовательностей единиц и двоек, сумма которых равна . Это можно принять за определение с соглашениями , что означает, что не существует такой последовательности, сумма которой равна −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)\}|}$

Таким образом, рекуррентное соотношение можно понять, разделив последовательности на два непересекающихся набора, где все последовательности начинаются либо с 1, либо с 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. ^[35] В символах:$${\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}$

Аналогичный аргумент, группирующий суммы по положению первой 1, а не первой 2, дает еще два тождества: и Иными словами, сумма первых чисел Фибоначчи с нечетным индексом до является (2 n ) -ым числом Фибоначчи, а сумма первых чисел Фибоначчи с четным индексом до является (2 n + 1) -ым числом Фибоначчи минус 1. ^[36]$${\displaystyle \sum _{i=0}^{n-1}F_{2i+1}=F_{2n}}$$$${\displaystyle \sum _{i=1}^{n}F_{2i}=F_{2n+1}-1.}$$${\displaystyle F_{2n-1}}$${\displaystyle F_{2n}}$

Другой трюк может быть использован для доказательства или на словах, сумма квадратов первых чисел Фибоначчи до является произведением n -го и ( n + 1) -го чисел Фибоначчи. Чтобы увидеть это, начните с прямоугольника Фибоначчи размера и разложите его на квадраты размера ; из этого следует тождество путем сравнения площадей :$${\displaystyle \sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}}$$${\displaystyle F_{n}}$${\displaystyle F_{n}\times F_{n+1}}$${\displaystyle F_{n},F_{n-1},...,F_{1}}$

Последовательность также рассматривается с использованием символического метода . ^[37] Точнее, эта последовательность соответствует определяемому комбинаторному классу . Спецификация этой последовательности такова . Действительно, как указано выше, -ое число Фибоначчи равно числу комбинаторных композиций (упорядоченных разбиений ) с использованием терминов 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}}}$

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

Идентификация Кассини утверждает, что идентичность Каталана является обобщением:$${\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}}$$где L _n — 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)}$$Их можно найти экспериментально с помощью редукции решетки , и они полезны при настройке специального числового поля сита для факторизации числа Фибоначчи.

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

$${\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}+5z^{5}+\dots .}$$

Этот ряд сходится для любого комплексного числа, удовлетворяющего , и его сумма имеет простую замкнутую форму: ^[39]${\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}}.}$$

Сумма всех четно-индексированных обратных чисел Фибоначчи равна ^[40] с рядом Ламберта , поскольку$${\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)\!.}$

Таким образом, обратная константа Фибоначчи равна ^[41]$${\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 }$$

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

Ряд Миллина дает тождество ^[43] , которое следует из замкнутой формы для его частичных сумм при стремлении N к бесконечности:$${\displaystyle \sum _{k=0}^{\infty }{\frac {1}{F_{2^{k}}}}={\frac {7-{\sqrt {5}}}{2}},}$$$${\displaystyle \sum _{k=0}^{N}{\frac {1}{F_{2^{k}}}}=3-{\frac {F_{2^{N}-1}}{F_{2^{N}}}}.}$$

Каждое третье число последовательности четно (кратно ) и, в более общем случае, каждое k -е число последовательности кратно F _k . Таким образом, последовательность Фибоначчи является примером последовательности делимости . Фактически, последовательность Фибоначчи удовлетворяет более сильному свойству делимости ^{[44] [45]} , где gcd — функция наибольшего общего делителя .${\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}}}$$

Эти случаи можно объединить в одну некусочную формулу , используя символ Лежандра : ^[46]$${\displaystyle p\mid F_{p\;-\,\left({\frac {5}{p}}\right)}.}$$

Вышеприведенная формула может быть использована в качестве теста на простоту в том смысле, что если где символ Лежандра был заменен символом Якоби , то это доказательство того, что n является простым числом, а если это не выполняется, то n определенно не является простым числом. Если n является составным и удовлетворяет формуле, то n является псевдопростым числом Фибоначчи . Когда m велико — скажем, 500- битное число — то мы можем эффективно вычислить F _m (mod n ) , используя матричную форму. Таким образом,$${\displaystyle n\mid F_{n\;-\,\left({\frac {5}{n}}\right)},}$$

$${\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}}.}$$Здесь мощность матрицы A ^m вычисляется с помощью модульного возведения в степень , которое можно адаптировать к матрицам . ^[47]

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

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

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

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

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

Единственное нетривиальное квадратное число Фибоначчи — 144. ^[51] В 2001 году Аттила Пете доказал, что существует лишь конечное число чисел Фибоначчи в полной степени . ^[52] В 2006 году И. Бюжо, М. Миньот и С. Сиксек доказали, что 8 и 144 являются единственными такими нетривиальными полными степенями. ^[53]

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

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

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

Делимость чисел Фибоначчи на простое число p связана с символом Лежандра , который вычисляется следующим образом:${\displaystyle {\bigl (}{\tfrac {p}{5}}{\bigr )}}$$${\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 — простое число, то ^{[60] [61]}$${\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}}.}$$

Например,$${\displaystyle {\begin{aligned}{\bigl (}{\tfrac {2}{5}}{\bigr )}&=-1,&F_{3}&=2,&F_{2}&=1,\\{\bigl (}{\tfrac {3}{5}}{\bigr )}&=-1,&F_{4}&=3,&F_{3}&=2,\\{\bigl (}{\tfrac {5}{5}}{\bigr )}&=0,&F_{5}&=5,\\{\bigl (}{\tfrac {7}{5}}{\bigr )}&=-1,&F_{8}&=21,&F_{7}&=13,\\{\bigl (}{\tfrac {11}{5}}{\bigr )}&=+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 — нечетное простое число, то: ^[62]$${\displaystyle 5{F_{\frac {p\pm 1}{2}}}^{2}\equiv {\begin{cases}{\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {p}{5}}{\bigr )}\pm 5\right){\pmod {p}}&{\text{if }}p\equiv 1{\pmod {4}}\\{\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {p}{5}}{\bigr )}\mp 3\right){\pmod {p}}&{\text{if }}p\equiv 3{\pmod {4}}.\end{cases}}}$$

Пример 1. p = 7 , в этом случае p ≡ 3 (mod 4) и мы имеем:$${\displaystyle {\bigl (}{\tfrac {7}{5}}{\bigr )}=-1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {7}{5}}{\bigr )}+3\right)=-1,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {7}{5}}{\bigr )}-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 {\bigl (}{\tfrac {11}{5}}{\bigr )}=+1:\qquad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {11}{5}}{\bigr )}+3\right)=4,\quad {\tfrac {1}{2}}\left(5{\bigl (}{\tfrac {11}{5}}{\bigr )}-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}}}$$