Простейшие свойства

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

F0 = 0, F1 = 1, F2 = 1, F3 = 2, F4 = 3, F5 = 5, F6 = 8,…

удовлетворяет рекуррентному соотношению

Fn+2 = Fn+1 + Fn. (1)

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

Обозначим через un, un+1, un+2 число пар зрелых кроликов соответственно через n месяцев, через n + 1 месяц и через n + 2 месяца. Нетрудно убедиться, что un+2 = un+1 + un: к моменту n + 2 зрелости достигают un пар кроликов, родившихся в момент n,

которые добавляются к un+1 паре кроликов, зрелых на момент n + 1.

Рассмотрим еще одну задачу, так называемую задачу о прыгуне. Некоторая величина x увеличивается за единицу времени на 1 или на 2. Требуется определить, сколькими способами может произойти увеличение рассматриваемой величины на n единиц. Обозначим искомое число способов через un. Пусть x(t) – значение величины x в момент времени t. Ясно, что x(1) = x(0) + 1 или x(1) = x(0) + 2 в зависимости от того, на 1 или на 2 изменилась величина x за первый временной промежуток. Имеются два пути достичь значения x(0) + n: вырасти на n – 1 единицу со значения x(0) + 1 или на n – 2 единицы со значения x(0) + 2. Первое может произойти un–1 способами, второе – un–2 способами. Следовательно,

un = un–1 + un–2.

Многие свойства чисел Фибоначчи нетрудно получить по индукции. Например, для любого n ≥ 0 справедливо равенство

1 1 

 

n 1

Fn 1 

. (2)

1 0 

 Fn 1

Fn 

В самом деле, (2) выполняется при n = 0. Следующая

выкладка позволяет сделать индуктивный шаг:

n2

 

1 0

F

Fn 1

F

1 1 

  =

1 0

  

n 1

n  

Fn2

=  Fn 3

Fn2 

.

 Fn1  Fn

Fn1 

 Fn 2

Fn1 

Если взять определители матриц, стоящих в правой и левой

частях (2), получится следующее соотношение:

Fn+2Fn –

= (–1)n+1.

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

Каждое целое положительное число имеет единственное представление вида

1 2

 K  Fk

, (3)

где k1 ≥ k2 +2; k2 ≥ k3 +2; …, kr–1 ≥ kr +2; kr ≥ 2.

взять наибольшее число Фибоначчи, не превосходящее n, в

– наибольшее число Фибоначчи, не

n − F

, и т. д., пока очередной «остаток» не

станет равным нулю. Например:

1 = F1; 2 = F2; 3 = F3;4 = F3 + F1; 5 = F4; 8 = F5; 13 = F6;

20 = F6 + F4 + F2.