Числа Фибоначчи

Чи́сла Фибона́ччи (вариант написания — Фибона́чи) — элементы числовой последовательности
 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, … (),
в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Названы в честь средневекового математика Леонардо Пизанского (известного как Фибоначчи).

Правда, в некоторых книгах, особенно в старых, член , равный нулю, опускается — тогда последовательность Фибоначчи начинается с .

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

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

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

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

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

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

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Книга абака» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, где условия таковы: изначально дана новорождённая пара кроликов (самец и самка); со второго месяца после своего рождения кролики начинают спариваться и производить новую пару кроликов, причём уже каждый месяц; кролики никогда не умирают, — а в качестве искомого выдвигает количество пар кроликов через год.
 В начале первого месяца есть только одна новорождённая пара (1).
 В конце первого месяца по-прежнему только одна пара кроликов, но уже спарившаяся (1).
 В конце второго месяца первая пара рождает новую пару и опять спаривается (2).
 В конце третьего месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара только спаривается (3).
 В конце четвёртого месяца первая пара рождает ещё одну новую пару и спаривается, вторая пара рождает новую пару и спаривается, третья пара только спаривается (5).

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

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

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

Обоснование 

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

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

Следствие и обобщение 
Из формулы Бине следует, что для всех  число  есть округление  то есть 
В частности, при  справедлива асимптотика 

Формула Бине может быть аналитически продолжена следующим образом:
 
При этом соотношение  выполняется для любого комплексного числа z.

Тождества 

 

 

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

И более общие формулы:
 
 
 
 Числа Фибоначчи представляются значениями континуант на наборе единиц:  то есть
 , а также 
 где матрицы имеют размер  и где i — мнимая единица.
 Числа Фибоначчи можно выразить через многочлены Чебышёва:
 
 
 Для любого n справедливо
 
 Как следствие, подсчёт определителей даёт тождество Кассини:
 

 С равенством Кассини сопряжено более общее утверждение, названное в честь Эжена Каталана:

 Это утверждение выводится из тождества Кассини при помощи основного соотношения чисел Фибоначчи:

Свойства 

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

 Нахождение числа Фибоначчи  с помощью Бинома Ньютона 

 В 1964 году Дж. Кон (J. H. E. Cohn) доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:
    
 Производящей функцией последовательности чисел Фибоначчи является:
 
 В частности, 1/998,999 = 0.001001002003005008013021…
Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена
 
 на множестве неотрицательных целых чисел x и y.

 Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.
 Период чисел Фибоначчи по модулю натурального числа  называется периодом Пизано и обозначается . Периоды Пизано  образуют последовательность:
 1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … ().
 В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом , последняя пара цифр чисел Фибоначчи образует последовательность с периодом , последние три цифры — с периодом  последние четыре — с периодом  последние пять — с периодом  и т. д.
 Натуральное число  является числом Фибоначчи тогда и только тогда, когда  или  является квадратом.
 Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.
 Число Фибоначчи  равно количеству кортежей длины n из нулей и единиц, в которых нет двух соседних единиц. При этом  равно количеству таких кортежей, начинающихся с нуля, а  — начинающихся с единицы.
 Произведение любых  подряд идущих чисел Фибоначчи делится на произведение первых  чисел Фибоначчи.
 Бесконечная сумма чисел, обратных числам Фибоначчи, сходится, его сумма («обратная постоянная Фибоначчи») равна 3,359884...

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

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

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

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

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

В искусстве 
В поэзии чаще находят отношение «золотого сечения» (золотую пропорцию), связанное через формулу Бине с числами Фибоначчи. Например, в поэме Ш. Руставели «Витязь в тигровой шкуре» и на картинах художников.

Однако числа Фибоначчи встречаются и непосредственно в поэзии и в музыке

В кодировании 
В теории кодирования предложены устойчивые так называемые «коды Фибоначчи», причём основание этих кодов — иррациональное число.

См. также 
 Дерево Фибоначчи
 Метод Фибоначчи с запаздываниями
 Метод Фибоначчи поиска экстремума
 Фибоначчи
 Фибоначчиева система счисления
 Числа Бине
 Числа Леонардо
 Таблица Витхоффа
 Последовательность коров Нараяны
 Золотое сечение
 Пропорционирование
 Последовательность без простых чисел

Примечания

Литература 
 
 
 
 
 
 Грант Аракелян. Математика и история золотого сечения. — М.: Логос, 2014. — 404 с. — ISBN 978-5-98704-663-0.
 .
 .
 .
 .
 .
 
 .

Ссылки 

 Первые 300 чисел Фибоначчи
 Числа Фибоначчи в природе

Целочисленные последовательности
Золотое сечение
 
История математики
Фибоначчи