Число Фибоначчи - Fibonacci number

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

В математике числа Фибоначчи , обычно обозначаемые F n , образуют последовательность , называемую последовательностью Фибоначчи , так что каждое число является суммой двух предыдущих, начиная с 0 и 1. То есть,

а также
для n > 1 .

Последовательность начинается:

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

Согласно некоторым более старым определениям, значение опускается, так что последовательность начинается с, а повторение допустимо для n > 2 . В своем первоначальном определении Фибоначчи начал последовательность с

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

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

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

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

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

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

История

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

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

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

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

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

Страница из Фибоначчи «s Liber Abaci от Biblioteca Nazionale ди Фиренце показывает (в поле справа) последовательность Фибоначчи с положением в последовательности меченого на латинском и римские цифры и значение в индо-арабскими цифрами.
Количество пар кроликов образует последовательность Фибоначчи

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

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

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

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

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

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

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

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

что дает последовательность чисел «негафибоначчи», удовлетворяющих

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

F −8 F −7 F −6 F −5 F −4 F −3 F −2 F −1 F 0 F 1 F 2 П 3 П 4 П 5 П 6 П 7 П 8
−21 13 −8 5 −3 2 −1 1 0 1 1 2 3 5 8 13 21 год

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

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

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

куда
это золотое сечение ( OEISA001622 ), и

Поскольку эту формулу также можно записать как

Чтобы убедиться в этом, заметим, что оба φ и ψ являются решениями уравнений
поэтому степени φ и ψ удовлетворяют рекурсии Фибоначчи. Другими словами,
а также

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

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

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

который имеет решение
производство требуемой формулы.

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

куда

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

С

для всех n ≥ 0 число F n является ближайшим к . Следовательно, его можно найти округлением с использованием ближайшей целочисленной функции:

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

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

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

куда

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

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

Эта сходимость сохраняется независимо от начальных значений, исключая 0 и 0, или любой пары в сопряженном золотом сечении. Это можно проверить с помощью формулы Бине . Например, начальные значения 3 и 2 генерируют последовательность 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ... Соотношение последовательных членов в этой последовательности показывает такое же сближение с золотым сечением.

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

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

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

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

Это уравнение можно доказать индукцией по n .

Это выражение справедливо и для п <1 , если последовательность Фибоначчи F п будет продлен до отрицательных целых чисел , используя правило Фибоначчи

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

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

альтернативно обозначается

который дает . В собственных значениях матрицы А имеют и соответствующие соответствующие собственные векторы

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

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

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

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

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

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

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

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

Более того, поскольку

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

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

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

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

Может возникнуть вопрос, является ли целое положительное число x числом Фибоначчи. Это верно тогда и только тогда, когда хотя бы один из или является

точным квадратом . Это потому, что формулу Бине, приведенную выше, можно перестроить, чтобы получить

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

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

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

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

Большинство тождеств, включающих числа Фибоначчи, можно доказать с помощью комбинаторных аргументов, используя тот факт, что можно интерпретировать как количество [возможно пустых] последовательностей единиц и двоек, сумма которых равна . Это можно принять как определение с соглашениями , означающее, что не существует такой последовательности, сумма которой равна −1, и , что означает, что пустая последовательность «складывается» до 0. Далее приводится

мощность набора:

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

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


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

Это можно увидеть, разделив все последовательности, суммируя до, на основе местоположения первых 2. В частности, каждый набор состоит из тех последовательностей, которые начинаются до последних двух наборов, каждая с мощностью 1.


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

... где последние два члена имеют значение . Из этого следует, что .

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

а также
Проще говоря, сумма первых чисел Фибоначчи с нечетным индексом до является (2
n ) -м числом Фибоначчи, а сумма первых чисел Фибоначчи с четным индексом до является (2 n  + 1) -м числом Фибоначчи минус 1.


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

или, говоря словами, сумма квадратов первых чисел Фибоначчи до является произведением
n- го и ( n  + 1) -го чисел Фибоначчи. Чтобы увидеть это, начните с прямоугольника Фибоначчи и разложите его на квадраты размера ; из этого тождество следует из сравнения областей:
34 * 21-FibonacciBlocks.png

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

Последовательность также рассматривается с использованием

символьного метода . Точнее, эта последовательность соответствует определяемому комбинаторному классу . Спецификация этой последовательности . В самом деле, как указано выше, -е число Фибоначчи равно количеству комбинаторных композиций (упорядоченных разбиений ) с использованием членов 1 и 2.

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

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

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

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

Добавление к обеим сторонам дает

и поэтому у нас есть формула для

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

дать

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

Формула Бине:

Это можно использовать для доказательства тождеств Фибоначчи.

Например, чтобы доказать это, обратите внимание, что левая часть, умноженная на, становится

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

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

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

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

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

Каталонская идентичность - это обобщение:

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

где L n - n- е число Лукаса . Последний - это тождество для удвоения n ; другие идентичности этого типа
личность Кассини.

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

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

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

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

Производящая функция

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

Этот ряд сходится при, а его сумма имеет простой замкнутый вид:

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

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

для s ( x ) приводит к закрытому виду.

дает производящую функцию для чисел Негафибоначчи и удовлетворяет

функциональному уравнению

Разложение частичной фракции задается

где - золотое сечение, а - его сопряжение.

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

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

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

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

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

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

с рядом Ламберта,     так как  

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

Кроме того, это число было доказано иррациональным путем Ричард Андре-Jeannin .

Серия Millin придает индивидуальность

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

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

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

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

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

НОД ( F n , F n +1 ) = НОД ( F n , F n +2 ) = НОД ( F n +1 , F n +2 ) = 1.

Каждое простое число p делит число Фибоначчи, которое может быть определено значением p по модулю 5. Если p сравнимо с 1 или 4 (по модулю 5), то p делит F p  - 1 , и если p сравнимо с 2 или 3 (mod 5), тогда p делит F p  + 1 . В оставшемся случае p  = 5, и в этом случае p делит F p .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Делимость чисел Фибоначчи на простое число p связана с символом Лежандра, который оценивается следующим образом:

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

Например,

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

Такие простые числа (если таковые имеются) назовем простыми числами Стены – Солнца – Солнца .

Кроме того, если p ≠ 5 - нечетное простое число, то:

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

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

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

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

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

Например,

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

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

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

Величина

Так как Р п является асимптотической , чтобы число цифр в F п является асимптотической . Как следствие, для каждого целого числа d > 1 существует 4 или 5 чисел Фибоначчи с d десятичными знаками.

В более общем смысле, в представлении с основанием b количество цифр в F n асимптотически равно

Обобщения

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

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

  • Обобщение индекса до отрицательных целых чисел для получения чисел Негафибоначчи .
  • Обобщение индекса на действительные числа с использованием модификации формулы Бине.
  • Начиная с других целых чисел. Числа Люка имеют L 1 = 1, L 2 = 3 и L n = L n −1 + L n −2 . Последовательности без простых чисел используют рекурсию Фибоначчи с другими начальными точками для генерации последовательностей, в которых все числа являются составными .
  • Допустим, что число является линейной функцией (кроме суммы) двух предыдущих чисел. В числе Pell есть P п = 2 Р п - 1 + Р п - 2 . Если коэффициенту предыдущего значения присваивается значение переменной x , результатом является последовательность полиномов Фибоначчи .
  • Не складывать непосредственно предшествующие числа. Последовательность Падована и числа Перрина имеют P ( n ) = P ( n - 2) + P ( n - 3).
  • Создание следующего числа путем добавления 3 чисел (числа трибоначчи), 4 чисел (числа тетраначчи) или более. Результирующие последовательности известны как 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

то есть , где мы выбираем позиции k двоек из nk-1 членов.

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

Эти числа также дают решение некоторых задач перечисления, наиболее распространенной из которых является подсчет количества способов записать данное число n в виде упорядоченной суммы единиц и двоек (называемых композициями ); есть F n +1 способов сделать это (эквивалентно, это также количество мозаик домино в прямоугольнике). Например, есть F 5 + 1 = F 6 = 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 без последовательных 1 с - это число Фибоначчи F n +2 . Например, из 16 двоичных строк длиной 4 F 6 = 8 без последовательных 1 с - это 0000, 0001, 0010, 0100, 0101, 1000, 1001 и 1010. Эквивалентно F n +2 равно количество подмножеств Sиз {1, ..., n } без последовательных целых чисел, то есть тех S, для которых { i , i + 1} ⊈ S для каждого i . Биекция с суммами до п + 1 , чтобы заменить 1 с 0 и 2 с 10 , а падение последний ноль.
  • Количество двоичных строк длины n без нечетного количества последовательных 1 s - это число Фибоначчи F n + 1 . Например, из 16 двоичных строк длиной 4 F 5 = 5 без нечетного количества последовательных 1 с - это 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 4 = 6 без четного числа последовательных 0 или 1 с - это 0001, 0111, 0101, 1000, 1010, 1110. Существует эквивалент заявление о подмножествах.
  • Юрий Матиясевич смог показать, что числа Фибоначчи могут быть определены диофантовым уравнением , что привело к его решению десятой проблемы Гильберта .
  • Числа Фибоначчи также являются примером полной последовательности . Это означает, что каждое положительное целое число можно записать как сумму чисел Фибоначчи, где любое одно число используется не более одного раза.
  • Более того, каждое положительное целое число может быть записано уникальным образом как сумма одного или нескольких различных чисел Фибоначчи таким образом, чтобы сумма не включала любые два последовательных числа Фибоначчи. Это известно как теорема Цекендорфа , а сумма чисел Фибоначчи, удовлетворяющая этим условиям, называется представлением Цекендорфа. Представление числа Цекендорфа можно использовать для получения его кодировки Фибоначчи .
  • Начиная с 5, каждое второе число Фибоначчи - это длина гипотенузы прямоугольного треугольника с целыми сторонами, или, другими словами, наибольшее число в тройке Пифагора , полученное по формуле
    Последовательность треугольников Пифагора, полученная по этой формуле, имеет стороны длин (3,4,5), (5,12,13), (16,30,34), (39,80,89), ... Сторона каждого из этих треугольников равна сумме трех сторон предыдущего треугольника.
  • Куба Фибоначчи представляет собой неориентированный граф с числом Фибоначчи узлов , который был предложен в качестве сетевой топологии для параллельных вычислений .
  • Числа Фибоначчи появляются в лемме о кольце , используемой для доказательства связи между теоремой об упаковке кругов и конформными отображениями .

Информатика

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

Природа

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

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

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

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

Модель рисунка цветочков на головке подсолнечника была предложена Гельмутом Фогелем в 1979 году. Она имеет вид

где 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-хромосома , которую он получил от своего отца. Самец считается «источником» его собственной Х-хромосомы ( ), а в поколении его родителей его Х-хромосома произошла от одного родителя ( ). Мать мужчины получила одну Х-хромосому от своей матери (бабушка по материнской линии сына) и одну от своего отца (деда по материнской линии), поэтому двое бабушек и дедушек внесли свой вклад в Х-хромосому потомка мужского пола ( ). Дед по материнской линии получил свою Х-хромосому от своей матери, а бабушка по материнской линии получила Х-хромосомы от обоих своих родителей, поэтому три прабабушки и дедушки внесли свой вклад в Х-хромосому мужского потомка ( ). Пять прапрапрадедов внесли свой вклад в Х-хромосому мужского потомка ( ) и т. Д. (Это предполагает, что все предки данного потомка независимы, но если какая-либо генеалогия прослеживается достаточно далеко во времени, предки начинают появляться в нескольких строках. генеалогии, пока в конце концов основатель населения не появится на всех линиях генеалогии.)

Пути тубулинов на внутриклеточных микротрубочках расположены в виде паттернов 3, 5, 8 и 13.

Другой

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

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

использованная литература

Сноски

Цитаты

Процитированные работы

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