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

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

F 0 = 0, F 1 = 1, F 2 = 1, F 3 = 2, F 4 = 3, F 5 = 5, F 6 = 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 +2 Fn –

= (–1) n +1.

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

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

1 2

 K  Fk

, (3)

где k 1 ≥ k 2 +2; k 2 ≥ k 3 +2; …, kr –1 ≥ kr +2; kr ≥ 2.

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

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

n − F

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

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

1 = F 1; 2 = F 2; 3 = F 3;4 = F 3 + F 1; 5 = F 4; 8 = F 5; 13 = F 6;

20 = F 6 + F 4 + F 2.

Не нашли, что искали? Воспользуйтесь поиском: