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

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

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

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

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

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

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

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

Определение

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

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

Согласно некоторым старым определениям, значение $F_{0}=0$ опускается, так что последовательность начинается с $F_{1}=F_{2}=1,$ и повторение $F_{n}=F_{n-1}+F_{n-2}$ справедливо для n > 2 .

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

FF0	FQ1	FФ2	F 3	FF4	Ф 5	Ф 6	Ф 7	Ф 8	FF9	F 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

История

Индия

Смотрите также: Золотое сечение § История

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

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

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

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

Хемачандре (ок. 1150 г.) также приписывают знание этой последовательности: написав, что «сумма последнего и предпоследнего есть число… следующей матра-вритты».

Европа

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

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

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

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

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

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

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

Основная статья: Золотое сечение

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

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

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

где

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

где

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

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

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

На самом деле ошибка округления очень мала: менее 0,1 для n ≥ 4 и менее 0,01 для n ≥ 8 . Эту формулу легко инвертировать, чтобы найти индекс числа Фибоначчи F : $$n(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}F\right\rceil ,\ F\geq 1.$$

Вместо этого использование функции пола дает наибольший индекс числа Фибоначчи, который не превышает F : $$n_{\mathrm {largest} }(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}(F+1/2)\right\rfloor ,\ F\geq 0,$$где $\log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )$, $\ln(\varphi )=0.481211\ldots$, и $\log _{10}(\varphi )=0.208987\ldots$.

Величина

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

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

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

Иоганн Кеплер заметил, что отношения последовательных чисел Фибоначчи сходятся . Он написал, что «как 5 к 8, так практически и 8 к 13, и как 8 к 13, так почти и 13 к 21», и пришел к выводу, что эти отношения приближаются к золотому сечению. $\varphi \colon$ $$\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi .$$

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

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

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

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

Поскольку золотое сечение удовлетворяет уравнению $$\varphi ^{2}=\varphi +1,$$

это выражение можно использовать для разложения высших степеней $\varphi ^{n}$ как линейную функцию младших степеней, которую, в свою очередь, можно разложить до линейной комбинации $\varphi$ и 1. Полученные рекуррентные соотношения дают числа Фибоначчи в виде линейных коэффициентов : $$\varphi ^{n}=F_{n}\varphi +F_{n-1}.$$Это уравнение можно доказать индукцией 1 по n ≥ : $$\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}.$$Для $\psi =-1/\varphi$, также бывает, что $\psi ^{2}=\psi +1$ и это также тот случай, когда $$\psi ^{n}=F_{n}\psi +F_{n-1}.$$

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

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

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

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

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

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

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

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

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

$${F_{k+2} \choose F_{k+1}}={\begin{pmatrix}1&1\\1&0\end{pmatrix}}{F_{k+1} \choose F_{k}}$$альтернативно обозначается $${\vec {F}}_{k+1}=\mathbf {A} {\vec {F}}_{k},$$

что дает ${\vec {F}}_{n}=\mathbf {A} ^{n}{\vec {F}}_{0}$. Собственные значения матрицы ​ A равны $\varphi ={\tfrac {1}{2}}{\bigl (}1+{\sqrt {5}}~\!{\bigr )}$ и $\psi =-\varphi ^{-1}={\tfrac {1}{2}}{\bigl (}1-{\sqrt {5}}~\!{\bigr )}$ соответствующие соответствующим собственным векторам $${\vec {\mu }}={\varphi \choose 1},\quad {\vec {\nu }}={-\varphi ^{-1} \choose 1}.$$

Поскольку начальное значение $${\vec {F}}_{0}={1 \choose 0}={\frac {1}{\sqrt {5}}}{\vec {\mu }}-{\frac {1}{\sqrt {5}}}{\vec {\nu }},$$

отсюда следует, что n- й член равен $${\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- й элемент ряда Фибоначчи можно считать непосредственно как выражение в замкнутой форме : $$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 Эквивалентно , посредством использования его собственного разложения :

$${\begin{aligned}A&=S\Lambda S^{-1},\\[3mu]A^{n}&=S\Lambda ^{n}S^{-1},\end{aligned}}$$

где

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

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

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

что снова дает $$F_{n}={\cfrac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}.$$

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

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

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

цепной Подходящие дроби дроби для φ представляют собой отношения последовательных чисел Фибоначчи: φ _n = F _{n +1} / F _n — n -я подходящая дробь, а ( n + 1) -я подходящая дробь находится из рекуррентного соотношения φ _{п +1} знак равно 1 + 1 / φ _п . Матрица, образованная из последовательных дробей любой цепной дроби, имеет определитель +1 или -1. Матричное представление дает следующее выражение в замкнутой форме для чисел Фибоначчи:

$${\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 ) арифметических операций, используя возведение в степень методом возведения в квадрат .

Взяв определитель обеих частей этого уравнения, получим тождество Кассини : $$(-1)^{n}=F_{n+1}F_{n-1}-{F_{n}}^{2}.$$

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

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

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

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

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

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

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

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

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

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

Таким образом, рекуррентное соотношение $$F_{n}=F_{n-1}+F_{n-2}$$можно понять, разделив $F_{n}$ последовательности на два непересекающихся набора, где все последовательности начинаются либо с 1, либо с 2: $$F_{n}=|\{(1,...),(1,...),...\}|+|\{(2,...),(2,...),...\}|$$За исключением первого элемента, сумма остальных членов каждой последовательности равна $n-2$ или $n-3$ и мощность каждого набора равна $F_{n-1}$ или $F_{n-2}$ давая в общей сложности $F_{n-1}+F_{n-2}$ последовательности, показывающие, что это равно $F_{n}$.

Аналогичным образом можно показать, что сумма первых чисел Фибоначчи до n -го равна ( n + 2) -му числу Фибоначчи минус 1. В символах: $$\sum _{i=1}^{n}F_{i}=F_{n+2}-1$$

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

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

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

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

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

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

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

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

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

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

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

Например, пересмотреть $$\sum _{i=1}^{n}F_{i}=F_{n+2}-1.$$Добавление $F_{n+1}$ обеим сторонам дает

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

и так у нас есть формула для $n+1$$$\sum _{i=1}^{n+1}F_{i}=F_{n+3}-1$$

Аналогично добавьте ${F_{n+1}}^{2}$ в обе стороны $$\sum _{i=1}^{n}F_{i}^{2}=F_{n}F_{n+1}$$дать $$\sum _{i=1}^{n}F_{i}^{2}+{F_{n+1}}^{2}=F_{n+1}\left(F_{n}+F_{n+1}\right)$$$$\sum _{i=1}^{n+1}F_{i}^{2}=F_{n+1}F_{n+2}$$

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

Формула Бине $${\sqrt {5}}F_{n}=\varphi ^{n}-\psi ^{n}.$$Это можно использовать для доказательства тождеств Фибоначчи.

Например, чтобы доказать, что ${\textstyle \sum _{i=1}^{n}F_{i}=F_{n+2}-1}$Обратите внимание, что левая часть, умноженная на ${\sqrt {5}}$ становится $${\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}}}$ упростить уравнения.

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

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

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

Основная статья: Кассини и каталонская идентичность

Личность Кассини утверждает, что $${F_{n}}^{2}-F_{n+1}F_{n-1}=(-1)^{n-1}$$Каталонская идентичность — это обобщение: $${F_{n}}^{2}-F_{n+r}F_{n-r}=(-1)^{n-r}{F_{r}}^{2}$$

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

$$F_{m}F_{n+1}-F_{m+1}F_{n}=(-1)^{n}F_{m-n}$$$$F_{2n}={F_{n+1}}^{2}-{F_{n-1}}^{2}=F_{n}\left(F_{n+1}+F_{n-1}\right)=F_{n}L_{n}$$где Ln _— е n - число Люка . Последнее — тождество удвоения n ; другие личности этого типа $$F_{3n}=2{F_{n}}^{3}+3F_{n}F_{n+1}F_{n-1}=5{F_{n}}^{3}+3(-1)^{n}F_{n}$$по личности Кассини.

$$F_{3n+1}={F_{n+1}}^{3}+3F_{n+1}{F_{n}}^{2}-{F_{n}}^{3}$$$$F_{3n+2}={F_{n+1}}^{3}+3{F_{n+1}}^{2}F_{n}+{F_{n}}^{3}$$$$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)$$Их можно найти экспериментально с помощью сокращения решетки , и они полезны при настройке специального сита числового поля для факторизации числа Фибоначчи.

В более общем смысле,

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

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

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

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

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

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

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

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

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

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

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

Разложение на частичные дроби определяется выражением $$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)}$ это золотое сечение и $\psi ={\tfrac {1}{2}}\left(1-{\sqrt {5}}\right)$ является его сопряжением .

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

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

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

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

Бесконечные суммы по обратным числам Фибоначчи иногда можно оценить с помощью тэта-функций . Например, сумму каждого обратного числа Фибоначчи с нечетным индексом можно записать как $$\sum _{k=1}^{\infty }{\frac {1}{F_{2k-1}}}={\frac {\sqrt {5}}{4}}\;\vartheta _{2}\!\left(0,{\frac {3-{\sqrt {5}}}{2}}\right)^{2},$$

и сумма квадратов обратных чисел Фибоначчи как $$\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 к каждому числу Фибоначчи в первой сумме, получится также замкнутая форма $$\sum _{k=1}^{\infty }{\frac {1}{1+F_{2k-1}}}={\frac {\sqrt {5}}{2}},$$

и существует вложенная сумма квадратов чисел Фибоначчи, дающая обратную величину золотого сечения : $$\sum _{k=1}^{\infty }{\frac {(-1)^{k+1}}{\sum _{j=1}^{k}{F_{j}}^{2}}}={\frac {{\sqrt {5}}-1}{2}}.$$

Сумма всех четных обратных чисел Фибоначчи равна $$\sum _{k=1}^{\infty }{\frac {1}{F_{2k}}}={\sqrt {5}}\left(L(\psi ^{2})-L(\psi ^{4})\right)$$с серией Ламберта $\textstyle L(q):=\sum _{k=1}^{\infty }{\frac {q^{k}}{1-q^{k}}},$ с $\textstyle {\frac {1}{F_{2k}}}={\sqrt {5}}\left({\frac {\psi ^{2k}}{1-\psi ^{2k}}}-{\frac {\psi ^{4k}}{1-\psi ^{4k}}}\right)\!.$

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

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

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

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

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

Каждое третье число последовательности четное (кратное $F_{3}=2$) и, в более общем смысле, каждое k -е число последовательности кратно F _k . Таким образом, последовательность Фибоначчи является примером последовательности делимости . Фактически, последовательность Фибоначчи удовлетворяет более сильному свойству делимости. $$\gcd(F_{a},F_{b},F_{c},\ldots )=F_{\gcd(a,b,c,\ldots )}\,$$где НОД — функция наибольшего общего делителя .

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

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

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

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

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

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

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

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

Основная статья: простое число Фибоначчи

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

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

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

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

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

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

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

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

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

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

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

Например, $${\begin{aligned}({\tfrac {2}{5}})&=-1,&F_{3}&=2,&F_{2}&=1,\\({\tfrac {3}{5}})&=-1,&F_{4}&=3,&F_{3}&=2,\\({\tfrac {5}{5}})&=0,&F_{5}&=5,\\({\tfrac {7}{5}})&=-1,&F_{8}&=21,&F_{7}&=13,\\({\tfrac {11}{5}})&=+1,&F_{10}&=55,&F_{11}&=89.\end{aligned}}$$

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

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

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

Кроме того, если p ≠ 5 — нечетное простое число, то: $$5{F_{\frac {p\pm 1}{2}}}^{2}\equiv {\begin{cases}{\tfrac {1}{2}}\left(5\left({\frac {p}{5}}\right)\pm 5\right){\pmod {p}}&{\text{if }}p\equiv 1{\pmod {4}}\\{\tfrac {1}{2}}\left(5\left({\frac {p}{5}}\right)\mp 3\right){\pmod {p}}&{\text{if }}p\equiv 3{\pmod {4}}.\end{cases}}$$

Пример 1. p = 7 , в этом случае p ≡ 3 (mod 4) и имеем: $$({\tfrac {7}{5}})=-1:\qquad {\tfrac {1}{2}}\left(5({\tfrac {7}{5}})+3\right)=-1,\quad {\tfrac {1}{2}}\left(5({\tfrac {7}{5}})-3\right)=-4.$$$$F_{3}=2{\text{ and }}F_{4}=3.$$$$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) и имеем: $$({\tfrac {11}{5}})=+1:\qquad {\tfrac {1}{2}}\left(5({\tfrac {11}{5}})+3\right)=4,\quad {\tfrac {1}{2}}\left(5({\tfrac {11}{5}})-3\right)=1.$$$$F_{5}=5{\text{ and }}F_{6}=8.$$$$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) и имеем: $$({\tfrac {13}{5}})=-1:\qquad {\tfrac {1}{2}}\left(5({\tfrac {13}{5}})-5\right)=-5,\quad {\tfrac {1}{2}}\left(5({\tfrac {13}{5}})+5\right)=0.$$$$F_{6}=8{\text{ and }}F_{7}=13.$$$$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) и имеем: $$({\tfrac {29}{5}})=+1:\qquad {\tfrac {1}{2}}\left(5({\tfrac {29}{5}})-5\right)=0,\quad {\tfrac {1}{2}}\left(5({\tfrac {29}{5}})+5\right)=5.$$$$F_{14}=377{\text{ and }}F_{15}=610.$$$$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.

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

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

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

Основная статья: период Пизано

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

Обобщения

Основная статья: Обобщения чисел Фибоначчи

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

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

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

Приложения

Математика

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

Числа Фибоначчи представляют собой суммы биномиальных коэффициентов на «мелких» диагоналях треугольника Паскаля : $$F_{n}=\sum _{k=0}^{\left\lfloor {\frac {n-1}{2}}\right\rfloor }{\binom {n-k-1}{k}}.$$Это можно доказать, разложив производящую функцию $${\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}$$и собирая подобные термины $x^{n}$.

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

5	= 1+1+1+1+1
	= 2+1+1+1	= 1+2+1+1	= 1+1+2+1	= 1+1+1+2
	= 2+2+1	= 2+1+2	= 1+2+2

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

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

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

5	= 1+1+1+1+1	= 2+1+1+1	= 1+2+1+1	= 1+1+2+1	= 2+2+1
	= 1+1+1+2	= 2+1+2	= 1+2+2

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

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

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

Информатика

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

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

Природа

Дополнительная информация: Закономерности в природе.

Смотрите также: Золотое сечение § Природа

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

Последовательности Фибоначчи появляются в биологических условиях, например, ветвление деревьев, расположение листьев на стебле , плоды ананаса , цветение артишока , расположение сосновой шишки , и генеалогическое древо медоносных пчел . Кеплер указал на присутствие последовательности Фибоначчи в природе, используя ее для объяснения ( связанной с золотым сечением ) пятиугольной формы некоторых цветов. У полевых ромашек чаще всего лепестки имеют количество чисел Фибоначчи. В 1830 году Карл Фридрих Шимпер и Александр Браун обнаружили, что паразитизмы (спиральный филлотаксис ) растений часто выражаются в виде дробей, включающих числа Фибоначчи.

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

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

Модель рисунка цветков на головке подсолнуха была предложена Хельмутом Фогелем в 1979 году. Это имеет форму

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

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

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

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

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

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

Другой

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

См. также

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

Ссылки

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

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

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

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