Чи́сла Фибона́ччи — элементы числовой последовательности

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS)

в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (известного как Фибоначчи)^[1]. Иногда число 0 не рассматривается как член последовательности.

Более формально, последовательность чисел Фибоначчи задается линейным рекуррентным соотношением:

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

Легко заметить, что .

Происхождение

Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении), намного раньше, чем она стала известна в Европе.

Образец длиной n может быть построен путём добавления S к образцу длиной n-1, либо L к образцу длиной n-2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнут рассматривает этот эффект в книге «Искусство программирования».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что:

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

Закономерным является тот факт, что каждая пара кроликов порождает ещё две пары на протяжении жизни, а затем погибает.

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

Формула Бине

Формула Бине выражает в явном виде значение как функцию от n:

,

где  — золотое сечение. При этом и являются корнями характеристического уравнения .

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

Формула Бине может быть аналитически продолжена следующим образом:

При этом соотношение выполняется для любого комплексного числа z.

Тождества

И более общие формулы:

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

, а также ,

где матрицы имеют размер , i — мнимая единица.

• Числа Фибоначчи можно выразить через многочлены Чебышева:

• Для любого n,

• Следствие. Подсчёт определителей даёт

Свойства

• Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. . Следствия:
  • делится на тогда и только тогда, когда делится на (за исключением ). В частности, делится на (то есть является чётным) только для ; делится на только для ; делится на только для и т. д.
  • может быть простым только для простых (с единственным исключением ). Например, число простое, и его индекс 13 также прост. Обратное не верно, наименьший контрпример — . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.

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

  .

• В 1964 году Дж. Кон (J. H. E. Cohn) доказал,^[3] что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:

  , , , .

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

• Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена

на множестве неотрицательных целых чисел x и y.^[4]

• Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
• Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность:

  1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)

  • В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.
• Натуральное число N является числом Фибоначчи тогда и только тогда, когда или является квадратом.^[5]
• Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.^[6]
• Число Фибоначчи равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних нулей. При этом равно количеству таких кортежей, начинающихся с нуля, а — начинающихся с единицы.

Вариации и обобщения

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

В других областях

Следует отметить, что почти все утверждения, находящие числа Фибоначчи в природных и исторических явлениях, неверны — это распространенный миф, который почти всегда оказывается неточной подгонкой под желаемый результат^[7][8].

В природе

• Филлотаксис (листорасположение) у растений описывается последовательностью Фибоначчи. Семена подсолнуха, сосновые шишки, лепестки цветков, ячейки ананаса также располагаются согласно последовательности Фибоначчи.^{[9][10][11][12]}
• Длины фаланг пальцев человека относятся примерно как числа Фибоначчи.^[9][13]

В культуре

• Американский писатель-фантаст Дэн Браун в книге «Код да Винчи» описал последовательность Фибоначчи как «лжешифр».
• Светящиеся числа Фибоначчи от 1 до 55 прикреплены на дымовой трубе Turku Energia в Турку^[14] и главном вокзале Цюриха^[15].
• В фильме «Двадцать одно» (англ. 21) последовательность Фибоначчи представлена в виде надписи на торте.
• «Ряд Фибоначчи» — дополнительное название песни 2012 года «Новый сигнал из космоса» российской рок-группы «Сплин».

См. также

• Дерево Фибоначчи
• Задача об упаковке в контейнеры
• Золотое сечение
• Метод Фибоначчи с запаздываниями
• Метод Фибоначчи поиска экстремума
• Непрерывная дробь
• Рекурсия
• Динамическое программирование
• Фибоначчи
• Фибоначчиева система счисления
• Числа Леонардо

Примечания