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

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

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

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

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

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

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

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

Определение

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

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

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

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

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

Европа

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

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

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

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

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

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

Отношение к золотому сечению

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

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

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

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

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

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

Фактически, ошибка округления быстро становится очень маленькой по мере роста 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 : где , , ^[26] и . ^[27] $${\displaystyle n_{\mathrm {largest} }(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 почти», и пришел к выводу, что эти отношения приближаются к золотому сечению ^{[28] [29]} ${\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 является числом Фибоначчи тогда и только тогда, когда хотя бы одно из или является полным квадратом . ^[30] Это происходит потому, что формула Бине, которая может быть записана как , может быть умножена на и решена как квадратное уравнение с помощью квадратной формулы : ${\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 . ^[31] Матрица, образованная из последовательных подходящих дробей любой непрерывной дроби, имеет определитель +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 -го числа Фибоначчи из формулы матрицы замкнутой формы, но с меньшим количеством избыточных шагов, если избегать повторного вычисления уже вычисленного числа Фибоначчи (рекурсия с запоминанием ). ^[32]

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

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

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

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

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

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

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

Идентификации Кассини и Каталана

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

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

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

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

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

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

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

Ряд Миллина дает тождество ^[41] , которое следует из замкнутой формы для его частичных сумм при стремлении 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 . Таким образом, последовательность Фибоначчи является примером последовательности делимости . Фактически, последовательность Фибоначчи удовлетворяет более сильному свойству делимости ^{[42] [43]} , где 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}}}$$

Эти случаи можно объединить в одну некусочную формулу , используя символ Лежандра : ^[44] $${\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 вычисляется с помощью модульного возведения в степень , которое можно адаптировать к матрицам . ^[45]

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

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

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

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

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

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

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

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

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

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

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

Делимость чисел Фибоначчи на простое число 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 — простое число, то ^{[58] [59]} $${\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 — нечетное простое число, то: ^[60] $${\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}}}$$

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

Например, $${\displaystyle F_{1}=1,\ F_{3}=2,\ F_{5}=5,\ F_{7}=13,\ F_{9}={\color {Red}34}=2\cdot 17,\ F_{11}=89,\ F_{13}=233,\ F_{15}={\color {Red}610}=2\cdot 5\cdot 61.}$$

Все известные множители чисел Фибоначчи F ( i ) для всех i < 50000 собраны в соответствующих репозиториях. ^{[62] [63]}

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

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

Обобщения

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

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

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

Приложения

Математика

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

Числа Фибоначчи возникают как суммы биномиальных коэффициентов в «неглубоких» диагоналях треугольника Паскаля : ^[67] Это можно доказать, расширив производящую функцию и собрав подобные члены . $${\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 \textstyle {\binom {5}{0}}+{\binom {4}{1}}+{\binom {3}{2}}}$

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

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

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

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

• Число двоичных строк длины n без последовательных единиц — это число Фибоначчи F _{n +2} . Например, из 16 двоичных строк длины 4 есть F ₆ = 8 без последовательных единиц — это 0000, 0001, 0010, 0100, 0101, 1000, 1001 и 1010. Такие строки являются двоичными представлениями чисел F bbinary . Эквивалентно, 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 без четного числа последовательных нулей или единиц равно 2 F _n . Например, из 16 двоичных строк длины 4 имеется 2 F ₄ = 6 без четного числа последовательных нулей или единиц — это 0001, 0111, 0101, 1000, 1010, 1110. Существует эквивалентное утверждение о подмножествах.
• Юрий Матиясевич смог показать, что числа Фибоначчи можно определить с помощью диофантового уравнения , что привело его к решению десятой проблемы Гильберта . ^[69]
• Числа Фибоначчи также являются примером полной последовательности . Это означает, что каждое положительное целое число может быть записано как сумма чисел Фибоначчи, где любое число используется максимум один раз.
• Более того, каждое положительное целое число может быть записано уникальным способом как сумма одного или нескольких различных чисел Фибоначчи таким образом, что сумма не включает никакие два последовательных числа Фибоначчи. Это известно как теорема Цекендорфа , а сумма чисел Фибоначчи, которая удовлетворяет этим условиям, называется представлением Цекендорфа. Представление Цекендорфа числа может быть использовано для вывода его кодировки Фибоначчи .
• Начиная с 5, каждое второе число Фибоначчи является длиной гипотенузы прямоугольного треугольника с целыми сторонами, или, другими словами, наибольшим числом в пифагоровой тройке , полученной из формулы Последовательность пифагоровых треугольников, полученная из этой формулы, имеет стороны длиной (3,4,5), (5,12,13), (16,30,34), (39,80,89), ... . Средняя сторона каждого из этих треугольников является суммой трех сторон предыдущего треугольника. ^[70] $${\displaystyle (F_{n}F_{n+3})^{2}+(2F_{n+1}F_{n+2})^{2}={F_{2n+3}}^{2}.}$$
• Куб Фибоначчи — это неориентированный граф с числом Фибоначчи в числе узлов, который был предложен в качестве сетевой топологии для параллельных вычислений .
• Числа Фибоначчи появляются в кольцевой лемме , используемой для доказательства связи между теоремой об упаковке кругов и конформными отображениями . ^[71]

Информатика

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

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

Природа

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

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

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

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

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

$${\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 , расстояния от центра. Подсолнухи и подобные цветы чаще всего имеют спирали цветков в направлениях по часовой стрелке и против часовой стрелки в количестве смежных чисел Фибоначчи, ^[88] как правило, подсчитываемых по самому внешнему диапазону радиусов. ^[89]

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

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

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

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

Аналогичным образом было замечено, что число возможных предков в линии наследования человеческой Х-хромосомы в данном предковом поколении также следует последовательности Фибоначчи. ^[92] У мужчины есть Х-хромосома, которую он получил от своей матери, и Y-хромосома , которую он получил от своего отца. Мужчина считается «источником» своей собственной Х-хромосомы ( ), а в поколении его родителей его Х-хромосома произошла от одного родителя ( ) . Мать мужчины получила одну Х-хромосому от своей матери (бабушки сына по материнской линии) и одну от своего отца (дедушки сына по материнской линии), поэтому двое бабушек и дедушек внесли свой вклад в Х-хромосому потомка мужского пола ( ) . Дедушка по материнской линии получил свою Х-хромосому от своей матери, а бабушка по материнской линии получила Х-хромосому от обоих своих родителей, поэтому три прабабушки и прадедушки внесли свой вклад в Х-хромосому потомка мужского пола ( ) . Пять прапрапрадедушки и прабабушки внесли свой вклад в X-хромосому потомка мужского пола ( ) и т. д. (Это предполагает, что все предки данного потомка независимы, но если проследить генеалогию достаточно далеко назад во времени, предки начнут появляться в нескольких линиях генеалогии, пока в конечном итоге основатель популяции не появится во всех линиях генеалогии.) ${\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 , есть три пути отражения, а не два, по одному для каждой из трех поверхностей.) ^[93]
• Уровни коррекции Фибоначчи широко используются в техническом анализе для торговли на финансовом рынке.
• Поскольку коэффициент преобразования 1,609344 для миль в километры близок к золотому сечению, разложение расстояния в милях на сумму чисел Фибоначчи становится почти суммой километров, когда числа Фибоначчи заменяются их последовательными значениями. Этот метод сводится к сдвигу регистра чисел с основанием 2 в золотом сечении по основанию φ . Чтобы преобразовать километры в мили, вместо этого сдвиньте регистр вниз по последовательности Фибоначчи. ^[94]
• Измеренные значения напряжений и токов в бесконечной цепи резисторов (также называемой лестницей резисторов или бесконечной последовательно-параллельной цепью) следуют последовательности Фибоначчи. Промежуточные результаты сложения чередующихся последовательных и параллельных сопротивлений дают дроби, состоящие из последовательных чисел Фибоначчи. Эквивалентное сопротивление всей цепи равно золотому сечению. ^[95]
• Brasch et al. 2012 показывают, как обобщенная последовательность Фибоначчи также может быть связана с областью экономики . ^[96] В частности, показано, как обобщенная последовательность Фибоначчи входит в функцию управления задач динамической оптимизации с конечным горизонтом с одним состоянием и одной управляющей переменной. Процедура проиллюстрирована на примере, часто называемом моделью экономического роста Брока–Мирмана.
• Марио Мерц включал последовательность Фибоначчи в некоторые из своих произведений искусства, начиная с 1970 года. ^[97]
• Йозеф Шиллингер (1895–1943) разработал систему композиции , которая использует интервалы Фибоначчи в некоторых своих мелодиях; он рассматривал их как музыкальный аналог сложной гармонии, очевидной в природе. ^[98] См. также Золотое сечение § Музыка .

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

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

Ссылки

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

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

Цитаты

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

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

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