Число Фибоначчи - Википедия - Fibonacci number

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

В математике Числа Фибоначчи, обычно обозначаемый F_п, сформировать последовательность, называется Последовательность Фибоначчи, так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,^[1]

${ Displaystyle F_ {0} = 0, quad F_ {1} = 1,}$

и

${ Displaystyle F_ {n} = F_ {n-1} + F_ {n-2}}$

за п > 1.

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

${ Displaystyle 0, ; 1, ; 1, ; 2, ; 3, ; 5, ; 8, ; 13, ; 21, ; 34, ; 55, ; 89, ; 144, ; ldots}$^[2]

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

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

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

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

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

Они тоже появляются в биологических условиях, например, ветвление на деревьях, расположение листьев на стебле, ростки плодов ананас цветение Артишок, раскручивающийся папоротник, а расположение сосновая шишка прицветники.

Числа Фибоначчи также тесно связаны с Числа Лукаса ${ displaystyle L_ {n}}$, в том, что числа Фибоначчи и Люка образуют дополнительную пару Последовательности Лукаса: ${ Displaystyle U_ {n} (1, -1) = F_ {n}}$ и ${ displaystyle V_ {n} (1, -1) = L_ {n}}$.

История

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

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

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

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

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

Страница из Фибоначчи с Liber Abaci от Biblioteca Nazionale di Firenze показывая (в рамке справа) последовательность Фибоначчи с позицией в последовательности, обозначенной латинскими и римскими цифрами, а значение - индуистско-арабскими цифрами.

Количество пар кроликов образует последовательность Фибоначчи

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

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

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

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

Приложения

• Числа Фибоначчи важны для вычислительный анализ времени выполнения из Алгоритм Евклида определить наибольший общий делитель двух целых чисел: наихудший вход для этого алгоритма - это пара последовательных чисел Фибоначчи.^[21]
• Brasch et al. 2012 показывает, как обобщенная последовательность Фибоначчи также может быть связана с областью экономики.^[22] В частности, показано, как обобщенная последовательность Фибоначчи входит в управляющую функцию задач динамической оптимизации с конечным горизонтом с одним состоянием и одной управляющей переменной. Процедура проиллюстрирована на примере, который часто называют моделью экономического роста Брока – Мирмана.
• Юрий Матиясевич смог показать, что числа Фибоначчи могут быть определены Диофантово уравнение, что привело к его решение Десятая проблема Гильберта.^[23]
• Числа Фибоначчи также являются примером полная последовательность. Это означает, что каждое положительное целое число можно записать как сумму чисел Фибоначчи, где любое одно число используется не более одного раза.
• Более того, любое натуральное число можно уникальным образом записать как сумму один или больше различные числа Фибоначчи таким образом, что сумма не включает любые два последовательных числа Фибоначчи. Это известно как Теорема цекендорфа, а сумма чисел Фибоначчи, удовлетворяющая этим условиям, называется представлением Цекендорфа. Представление числа Цекендорфа можно использовать для получения его Кодирование Фибоначчи.
• Числа Фибоначчи используются некоторыми генераторы псевдослучайных чисел.
• Они также используются в планирование покера, что является этапом оценки в проектах разработки программного обеспечения, в которых используется Scrum методология.
• Числа Фибоначчи используются в многофазной версии Сортировка слиянием алгоритм, в котором несортированный список делится на два списка, длина которых соответствует последовательным числам Фибоначчи - путем деления списка таким образом, чтобы две части имели длину в приблизительной пропорции φ. Ленточная реализация многофазная сортировка слиянием был описан в Искусство программирования.
• Числа Фибоначчи возникают при анализе Куча Фибоначчи структура данных.
• В Куб Фибоначчи является неориентированный граф с числом узлов Фибоначчи, которое было предложено как топология сети за параллельные вычисления.
• Метод одномерной оптимизации, называемый Техника поиска Фибоначчи, использует числа Фибоначчи.^[24]
• Ряд чисел Фибоначчи используется для необязательного сжатие с потерями в МКФ 8SVX формат аудиофайла, используемый на Amiga компьютеры. Числовой ряд компанды исходная звуковая волна, аналогичная логарифмическим методам, таким как μ-закон.^[25][26]
• Поскольку преобразование Фактор 1,609344 для миль в километры близок к золотому сечению, разложение расстояния в милях на сумму чисел Фибоначчи становится почти суммой в километрах, когда числа Фибоначчи заменяются их преемниками. Этот метод составляет основание 2 номер регистр в база золотого сечения φ перемещается. Чтобы преобразовать километры в мили, вместо этого сдвиньте регистр вниз по последовательности Фибоначчи.^[27]
• В оптика, когда луч света проходит под углом через две сложенные друг на друга прозрачные пластины из разных материалов и показатели преломления, он может отражаться от трех поверхностей: верхней, средней и нижней поверхностей двух пластин. Количество различных путей луча, которые имеют k размышления, для k > 1, это ${ displaystyle k}$-е число Фибоначчи. (Однако когда k = 1, есть три пути отражения, а не два, по одному для каждой из трех поверхностей.)^[28]
• Марио Мерц включил последовательность Фибоначчи в некоторые из своих работ, начиная с 1970 года.^[29]
• Восстановление Фибоначчи уровни широко используются в технический анализ для торговли на финансовых рынках.
• Числа Фибоначчи появляются в кольцевая лемма, используется для доказательства связи между теорема об упаковке кругов и конформные карты.^[30]

Музыка

Джозеф Шиллингер (1895–1943) разработал система композиции который использует интервалы Фибоначчи в некоторых своих мелодиях; он рассматривал их как музыкальный аналог сложной гармонии, очевидной в природе.^[31]

Природа

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

Последовательности Фибоначчи появляются в биологических условиях,^[32] например, ветвление на деревьях, расположение листьев на стебле, плоды ананас,^[33] расцвет Артишок, распускающийся папоротник и расположение сосновая шишка,^[34] и генеалогическое древо медоносных пчел.^[35][36] Кеплер указал на присутствие последовательности Фибоначчи в природе, используя ее для объяснения (Золотое сечение родственные) пятиугольной формы некоторых цветов.^[37] Поле ромашки чаще всего имеют лепестки в счетах чисел Фибоначчи.^[38] В 1754 г. Шарль Бонне обнаружили, что спиральный филлотаксис растений часто выражается в числовых рядах Фибоначчи.^[39]

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

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

Модель по выкройке цветочки в голове подсолнечник был предложен Гельмут Фогель [де ] в 1979 г.^[41] Это имеет вид

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

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

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

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

Таким образом, у пчелы-самца всегда один родитель, а у самки - два. Если проследить родословную любого самца пчелы (1 пчела), у него будет 1 родитель (1 пчела), 2 бабушки и дедушки, 3 прабабушки и дедушки, 5 пра-прадедушек и т. Д. Эта последовательность чисел родителей и есть последовательность Фибоначчи. Количество предков на каждом уровне, F_п, - количество предков женского пола, которое F_п−1, плюс количество предков мужского пола, которое F_п−2.^[44] Это происходит при нереалистичном предположении, что предки на каждом уровне иначе не связаны.

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

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

Пути тубулины на внутриклеточном микротрубочки расположите по образцам 3, 5, 8 и 13.^[46]

Математика

Числа Фибоначчи - это суммы «мелких» диагоналей (показаны красным) Треугольник Паскаля.

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

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

Эти числа также дают решение некоторых задач перечисления,^[48] наиболее распространенным из них является подсчет количества способов записи данного числа п как упорядоченную сумму единиц и двоек (называемую композиции ); Существуют F_п+1 способы сделать это. Например, если п = 5, тогда F_п+1 = F₆ = 8 считает восемь композиций в сумме до 5:

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

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

• Количество двоичных строк длины п без последовательных 1s - число Фибоначчи F_п+2. Например, из 16 двоичных строк длиной 4 есть F₆ = 8 без последовательных 1s - это 0000, 0001, 0010, 0100, 0101, 1000, 1001 и 1010. Эквивалентно, F_п+2 это количество подмножеств S из {1, ..., п} без последовательных целых чисел, то есть те S для которого {я, я + 1} ⊈ S для каждого я.
• Количество двоичных строк длины п без нечетного количества последовательных 1s - число Фибоначчи F_{п + 1}. Например, из 16 двоичных строк длиной 4 есть F₅ = 5 без нечетного количества последовательных 1s - это 0000, 0011, 0110, 1100, 1111. Эквивалентно количество подмножеств S из {1, ..., п} без нечетного числа последовательных целых чисел F_п+1.
• Количество двоичных строк длины п без четного числа последовательных 0s или 1s это 2F_п. Например, из 16 двоичных строк длиной 4 есть 2F₄ = 6 без четного числа последовательных 0s или 1s - это 0001, 0111, 0101, 1000, 1010, 1110. Есть эквивалентное утверждение о подмножествах.

Свойства последовательности

Первые 21 число Фибоначчи F_п находятся:^[2]

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19	F20
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765

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

${ Displaystyle F_ {n-2} = F_ {n} -F_ {n-1},}$

что дает последовательность чисел "негафибоначчи"^[49] удовлетворение

${ displaystyle F _ {- n} = (- 1) ^ {n + 1} F_ {n}.}$

Таким образом, двунаправленная последовательность

F−8

F−7

F−6

F−5

F−4

F−3

F−2

F−1

F0

F1

F2

F3

F4

F5

F6

F7

F8

−21

13

−8

5

−3

2

−1

1

0

1

1

2

3

5

8

13

21

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

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

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

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

куда

${ displaystyle varphi = { frac {1 + { sqrt {5}}} {2}} приблизительно 1.61803 , 39887 ldots}$

это Золотое сечение (OEIS: A001622), и

${ displaystyle psi = { frac {1 - { sqrt {5}}} {2}} = 1- varphi = - {1 over varphi} приблизительно -0.61803 , 39887 ldots.}$^[51]

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

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

Чтобы увидеть это,^[52] Обратите внимание, что φ и ψ оба решения уравнений

${ displaystyle x ^ {2} = x + 1 quad { text {and}} quad x ^ {n} = x ^ {n-1} + x ^ {n-2},}$

так что полномочия φ и ψ удовлетворяют рекурсии Фибоначчи. Другими словами,

${ displaystyle varphi ^ {n} = varphi ^ {n-1} + varphi ^ {n-2}}$

и

${ Displaystyle psi ^ {n} = psi ^ {n-1} + psi ^ {n-2}.}$

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

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

удовлетворяет такое же повторение

${ Displaystyle U_ {n} = a varphi ^ {n-1} + b psi ^ {n-1} + a varphi ^ {n-2} + b psi ^ {n-2} = U_ { n-1} + U_ {n-2}.}$

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

${ displaystyle left {{ begin {array} {l} a + b = 0 varphi a + psi b = 1 end {array}} 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 a = { frac {U_ {1} -U_ {0} psi} { sqrt {5}}}}$

${ displaystyle b = { frac {U_ {0} varphi -U_ {1}} { sqrt {5}}}}$.

Вычисление округлением

С

${ displaystyle left | { frac { psi ^ {n}} { sqrt {5}}} right | <{ frac {1} {2}}}$

для всех п ≥ 0, номер F_п это ближайшее целое число к ${ displaystyle { frac { varphi ^ {n}} { sqrt {5}}}}$. Следовательно, его можно найти округление, используя ближайшую целочисленную функцию:

${ displaystyle F_ {n} = left [{ frac { varphi ^ {n}} { sqrt {5}}} right], n geq 0.}$

На самом деле ошибка округления очень мала и составляет менее 0,1 для п ≥ 4, и менее 0,01 для п ≥ 8.

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

${ displaystyle F_ {n} = left lfloor { frac { varphi ^ {n}} { sqrt {5}}} + { frac {1} {2}} right rfloor, n geq 0.}$

Поскольку функция пола монотонный, последняя формула может быть обращена для нахождения индекса п(F) наибольшего числа Фибоначчи, не превышающего настоящий номер F > 1:

${ displaystyle n (F) = left lfloor log _ { varphi} left (F cdot { sqrt {5}} + { frac {1} {2}} right) right rfloor ,}$

куда ${ displaystyle log _ { varphi} (x) = ln (x) / ln ( varphi) = log _ {10} (x) / log _ {10} ( varphi).}$

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

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

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

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

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

Разложение властей

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

${ Displaystyle varphi ^ {2} = varphi +1,}$

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

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

Это уравнение можно доказать с помощью индукция на п.

Это выражение верно и для п <1, если последовательность Фибоначчи F_п является расширен до отрицательных целых чисел используя правило Фибоначчи ${ displaystyle F_ {n} = F_ {n-1} + F_ {n-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},}$

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

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

и

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

Поскольку начальное значение равно

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

следует, что п-й член

${ displaystyle { begin {align} { 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} выбрать 1}, end {выровненный}}}$

Отсюда п-й элемент ряда Фибоначчи может быть прочитан непосредственно как выражение в закрытой форме:

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

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

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

куда ${ displaystyle Lambda = { begin {pmatrix} varphi & 0 0 & - varphi ^ {- 1} end {pmatrix}}}$ и ${ displaystyle S = { begin {pmatrix} varphi & - varphi ^ {- 1} 1 & 1 end {pmatrix}}.}$Выражение в закрытой форме для п-й элемент в ряду Фибоначчи, следовательно, задается

${ displaystyle { begin {align} {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 {align}}}$

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

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

Матрица А имеет детерминант −1, и, следовательно, это 2 × 2 унимодулярная матрица.

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

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

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

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

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

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

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

${ displaystyle { begin {align} {F_ {m}} {F_ {n}} + {F_ {m-1}} {F_ {n-1}} & = F_ {m + n-1}, F_ {m} F_ {n + 1} + F_ {m-1} F_ {n} & = F_ {m + n}. End {выравнивается}}}$

В частности, с м = п,

${ displaystyle { begin {align} F_ {2n-1} & = F_ {n} ^ {2} + F_ {n-1} ^ {2} F_ {2n} & = (F_ {n-1 } + F_ {n + 1}) F_ {n} & = (2F_ {n-1} + F_ {n}) F_ {n}. End {выровнено}}}$

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

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

Может возникнуть вопрос, может ли положительное целое число Икс это число Фибоначчи. Это верно тогда и только тогда, когда хотя бы один из ${ displaystyle 5x ^ {2} +4}$ или же ${ displaystyle 5x ^ {2} -4}$ это идеальный квадрат.^[56] Это потому, что формула Бине над можно переставить, чтобы дать

${ displaystyle n = log _ { varphi} left ({ frac {F_ {n} { sqrt {5}} + { sqrt {5F_ {n} ^ {2} pm 4}}} { 2}} right),}$

что позволяет найти позицию в последовательности данного числа Фибоначчи.

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

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

Большинство тождеств, включающих числа Фибоначчи, можно доказать с помощью комбинаторные аргументы используя тот факт, что F_п можно интерпретировать как количество последовательностей единиц и двоек, которые в сумме составляют п - 1. Это можно рассматривать как определение F_п, с условием, что F₀ = 0, что означает, что сумма не равна −1, и что F₁ = 1, что означает, что пустая сумма «складывается» в 0. Здесь порядок слагаемого имеет значение. Например, 1 + 2 и 2 + 1 считаются двумя разными суммами.

Например, рекуррентное соотношение

${ Displaystyle F_ {n} = F_ {n-1} + F_ {n-2},}$

или на словах п-ое число Фибоначчи представляет собой сумму двух предыдущих чисел Фибоначчи, может быть показано путем деления числа F_п суммы единиц и двоек, которые добавляют к п - 1 на две неперекрывающиеся группы. Одна группа содержит те суммы, у которых первый член равен 1, а другая - те суммы, у которых первый член равен 2. В первой группе оставшиеся члены добавляют к п - 2, так что F_п-1 сумм, а во второй группе оставшиеся члены прибавляют к п - 3, так что есть F_п−2 суммы. Итак, всего F_п−1 + F_п−2 сумм, показывая, что это равно F_п.

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

${ Displaystyle сумма _ {я = 1} ^ {п} F_ {я} = F_ {п + 2} -1}$

Это делается путем деления сумм на п + 1 другим способом, на этот раз по расположению первых 2. В частности, первая группа состоит из тех сумм, которые начинаются с 2, вторая группа - из тех, которые начинаются с 1 + 2, третья 1 + 1 + 2 и так далее, до последней группы, состоящей из единственной суммы, в которой используются только единицы. Количество сумм в первой группе составляет F(п), F(п - 1) во второй группе и т. Д. С 1 суммой в последней группе. Таким образом, общее количество сумм равно F(п) + F(п − 1) + ... + F(1) + 1, поэтому эта величина равна F(п + 2).

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

${ Displaystyle сумма _ {я = 0} ^ {п-1} F_ {2i + 1} = F_ {2n}}$

и

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

На словах сумма первых чисел Фибоначчи с нечетным индексом до F_2п−1 является (2п) -го числа Фибоначчи и суммы первых чисел Фибоначчи с четным индексом до F_2п является (2п + 1) -е число Фибоначчи минус 1.^[58]

Можно использовать другой прием, чтобы доказать

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

или, говоря словами, сумма квадратов первых чисел Фибоначчи до F_п продукт пth и (п + 1) числа Фибоначчи. В данном случае прямоугольник Фибоначчи размером F_п к F(п + 1) можно разложить на квадраты размером F_п, F_п−1и так далее до F₁ = 1, откуда тождество следует из сравнения площадей.

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

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

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

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

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

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

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

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

личность d'Ocagne

${ 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_п это п 'th Число Лукаса. Последний тож на удвоение п; другие идентичности этого типа

${ Displaystyle F_ {3n} = 2F_ {n} ^ {3} + 3F_ {n} F_ {n + 1} F_ {n-1} = 5F_ {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} + 3F_ {n + 1} ^ {2} F_ {n} + F_ {n} ^ {3}}$

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

Их можно найти экспериментально, используя редукция решетки, и полезны при настройке сито со специальным номером к факторизовать число Фибоначчи.

В более общем смысле,^[60]

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

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

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

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

Силовая серия

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

${ displaystyle s (x) = sum _ {k = 0} ^ { infty} F_ {k} x ^ {k}.}$

Этот ряд сходится при ${ displaystyle | x | <{ frac {1} { varphi}},}$ а его сумма имеет простую замкнутую форму:^[61]

${ displaystyle s (x) = { frac {x} {1-x-x ^ {2}}}}$

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

${ displaystyle { begin {align} s (x) & = sum _ {k = 0} ^ { infty} F_ {k} x ^ {k} & = F_ {0} + F_ {1} x + sum _ {k = 2} ^ { infty} left (F_ {k-1} + F_ {k-2} right) x ^ {k} & = x + sum _ {k = 2 } ^ { infty} F_ {k-1} x ^ {k} + sum _ {k = 2} ^ { infty} F_ {k-2} x ^ {k} & = x + x sum _ {k = 0} ^ { infty} F_ {k} x ^ {k} + x ^ {2} sum _ {k = 0} ^ { infty} F_ {k} x ^ {k} & = x + xs (x) + x ^ {2} s (x). end {align}}}$

Решение уравнения

${ Displaystyle s (x) = x + xs (x) + x ^ {2} s (x)}$

за s(Икс) приводит к приведенной выше закрытой форме.

Параметр Икс = 1/k, замкнутая форма ряда принимает вид

${ displaystyle sum _ {n = 0} ^ { infty} { frac {F_ {n}} {k ^ {n}}} = { frac {k} {k ^ {2} -k-1 }}.}$

В частности, если k является целым числом больше 1, то этот ряд сходится. Дальнейшая настройка k = 10^м дает

${ displaystyle sum _ {n = 1} ^ { infty} { frac {F_ {n}} {10 ^ {m (n + 1)}}} = { frac {1} {10 ^ {2m } -10 ^ {m} -1}}}$

для всех положительных целых чисел м.

Некоторые сборники-головоломки по математике представляют как любопытную особую ценность, исходящую от м = 1, который ${ displaystyle { frac {s (1/10)} {10}} = { frac {1} {89}} =. 011235 ldots}$^[62] По аналогии, м = 2 дает

${ displaystyle { frac {s (1/100)} {100}} = { frac {1} {9899}} =. 0001010203050813213455 ldots}$

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

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

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

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

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

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

${ displaystyle sum _ {k = 0} ^ { 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}}.}$

Нет закрытой формулы для обратная константа Фибоначчи

${ displaystyle psi = sum _ {k = 1} ^ { infty} { frac {1} {F_ {k}}} = 3.359885666243 dots}$

известно, но число доказано иррациональный к Ричард Андре-Жаннин.^[63]

В Серия Миллина дает личность^[64]

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

что следует из замкнутой формы его частичных сумм при N стремится к бесконечности:

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

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

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

Каждое третье число последовательности является четным и, в более общем смысле, каждое k-й номер последовательности кратен F_k. Таким образом, последовательность Фибоначчи является примером последовательность делимости. Фактически, последовательность Фибоначчи удовлетворяет более сильному свойству делимости^[65][66]

${ displaystyle gcd (F_ {m}, F_ {n}) = F _ { gcd (m, n)}.}$

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

gcd (F_п, F_п+1) = gcd (F_п, F_п+2) = gcd (F_п+1, F_п+2) = 1.

Каждое простое число п делит число Фибоначчи, которое может быть определено значением п по модулю 5. Если п конгруэнтно 1 или 4 (mod 5), то п разделяет F_п − 1, и если п конгруэнтно 2 или 3 (mod 5), то п разделяет F_п + 1. Остающийся случай таков: п = 5, и в этом случае п разделяет F_п.

${ displaystyle { begin {case} 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 {case}}}$

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

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

Проверка на первичность

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

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

где символ Лежандра был заменен на Символ Якоби, то это свидетельствует о том, что п простое число, и если оно не выполняется, то п определенно не прайм. Если п составно и удовлетворяет формуле, то п это Псевдопросто Фибоначчи. Когда м большое - скажем, 500-битное число - тогда мы можем вычислить F_м (мод п) эффективно используя матричную форму. Таким образом

${ displaystyle { begin {pmatrix} F_ {m + 1} & F_ {m} F_ {m} & F_ {m-1} end {pmatrix}} Equiv { begin {pmatrix} 1 & 1 1 & 0 конец {pmatrix}} ^ {m} { pmod {n}}.}$

Здесь мощность матрицы А^м рассчитывается с использованием модульное возведение в степень, который может быть адаптирован к матрицам.^[68]

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

А Простое число Фибоначчи число Фибоначчи, которое основной. Первые несколько:

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, ... OEIS: A005478.

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

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

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

Единственный нетривиальный квадрат Число Фибоначчи 144.^[71] Аттила Пету доказал в 2001 году, что существует только конечное число чисел Фибоначчи совершенной степени.^[72] В 2006 г. Ю. Бюжо, М. Миньотт и С. Сиксек доказали, что 8 и 144 - единственные такие нетривиальные совершенные степени.^[73]

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

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

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

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

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

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

Если п простое число, тогда

${ 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}}.}$^[79][80]

Например,

${ displaystyle { begin {align} ({ 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 {align}}}$

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

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

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

Кроме того, если п ≠ 5 - нечетное простое число, тогда:^[81]

${ displaystyle 5F _ { 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 {case}}}$

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

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

${ displaystyle F_ {3} = 2 { text {и}} F_ {4} = 3.}$

${ Displaystyle 5F_ {3} ^ {2} = 20 Equiv -1 { pmod {7}} ; ; { text {and}} ; ; 5F_ {4} ^ {2} = 45 экв -4 { pmod {7}}}$

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

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

${ displaystyle F_ {5} = 5 { text {и}} F_ {6} = 8.}$

${ Displaystyle 5F_ {5} ^ {2} = 125 эквив 4 { pmod {11}} ; ; { текст {и}} ; ; 5F_ {6} ^ {2} = 320 эквив 1 { pmod {11}}}$

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

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

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

${ displaystyle 5F_ {6} ^ {2} = 320 Equiv -5 { pmod {13}} ; ; { text {and}} ; ; 5F_ {7} ^ {2} = 845 эквивалент 0 { pmod {13}}}$

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

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

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

${ Displaystyle 5F_ {14} ^ {2} = 710645 Equiv 0 { pmod {29}} ; ; { text {and}} ; ; 5F_ {15} ^ {2} = 1860500 эквив. 5 { pmod {29}}}$

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

Например,

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

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

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

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

Правые треугольники

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

Первый треугольник в этой серии имеет стороны длиной 5, 4 и 3. Если пропустить 8, следующий треугольник имеет стороны длиной 13, 12 (5 + 4 + 3) и 5 ​​(8 - 3). Пропуская 21, следующий треугольник имеет стороны длиной 34, 30 (13 + 12 + 5) и 16 (21-5). Эта серия продолжается бесконечно. Стороны треугольника а, б, c можно рассчитать напрямую:

${ displaystyle { begin {align} a_ {n} & = F_ {2n-1} = F_ {n} ^ {2} + F_ {n-1} ^ {2} [4pt] b_ {n} & = 2F_ {n} F_ {n-1} [4pt] c_ {n} & = F_ {n} ^ {2} -F_ {n-1} ^ {2} = F_ {n + 1} F_ {п-2}. end {выравнивается}}}$

Эти формулы удовлетворяют ${ displaystyle a_ {n} ^ {2} = b_ {n} ^ {2} + c_ {n} ^ {2}}$ для всех п, но они представляют стороны треугольника только тогда, когдап > 2.

Любые четыре последовательных числа Фибоначчи F_п, F_п+1, F_п+2 и F_п+3 может также использоваться для генерации тройки Пифагора другим способом:^[86]

${ Displaystyle { begin {align} a_ {n} & = F_ {n + 1} ^ {2} + F_ {n + 2} ^ {2} b_ {n} & = 2F_ {n + 1} F_ {n + 2} c_ {n} & = F_ {n} F_ {n + 3}. End {выровнено}}}$

Эти формулы удовлетворяют ${ displaystyle a_ {n} ^ {2} = b_ {n} ^ {2} + c_ {n} ^ {2}}$ для всех п, но они представляют стороны треугольника только тогда, когдап > 0.

Величина

С F_п является асимптотический к ${ displaystyle varphi ^ {n} / { sqrt {5}}}$, количество цифр в F_п асимптотичен ${ Displaystyle п журнал _ {10} varphi приблизительно 0,2090 , п}$. Как следствие, для каждого целого числа d > 1 есть 4 или 5 чисел Фибоначчи с d десятичные цифры.

В общем, в базе б представление, количество цифр в F_п асимптотичен ${ displaystyle n log _ {b} varphi.}$

Обобщения

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

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

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

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

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

Сноски

Цитаты