Формула Бине и некоторые ее применения

Напомним (см. 11.3, формула (5)), что производящая функция для последовательности чисел Фибоначчи имеет вид

F(z) = F0 + F1z + F2z2 + … =

z .

1 − z − z 2

Корнями характеристического многочлена

k(z) = z2 – z –1

являются числа

б  1 5

и в  1− 5 .

Число Фибоначчи как функция своего номера

представляется в виде:

или

Fn =

б n − в n

5

, (4)

n

 1 5 

n

 1− 5 

  − 

2 2

Fn 

   ,

5

Формула (4) называется формулой Бине.

Так как 2 =  + 1, то любую степень числа  можно представить в виде целочисленной комбинации a + b. Оказывается, коэффициентами служат числа Фибоначчи:

k+2 = Fk+2 + Fk+1.

Формула Бине позволяет убедиться в этом прямой проверкой.

Приведем несколько оценок чисел Фибоначчи.

Число Фибоначчи Fn есть ближайшее целое к числу .

Следовательно,

бn − в n бn

 −

5 5

5 2

Из (4) вытекает также следующее свойство.

С ростом n числа Фибоначчи неограниченно сближаются с

членами геометрической прогрессии с начальным членом 1 и

знаменателем  

5  1 :

2

 n 

lim  F − б

  0 .

Отношение соседних чисел Фибоначчи (следующего к

Действительно,

2 ≈ 0,618 .

5  1

Fn 

б n − в n

 1− (в / б) .

Fn 1

бn 1 −вn 1

б − в(в / б)n

Так как / < 1, то (/)n с ростом n стремится к нулю.

Следовательно,

lim

Fn  1

≈ 0,618 .

n→∞ Fn 1 б

Из предыдущего равенства следует, что

lim

Fn  1

≈ 0,382 .

n→∞ Fn  2 б 2

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

При любом n справедливо следующее равенство:

Fn 1 

∑ C k− k . (6)

Заметим сначала, что при четном n равенство (6) имеет вид

0 1 n / 2

а при нечетном –

Fn 1  Cn

 Cn −1 ... Cn / 2 ,

0 1 (n −1) / 2

Например:

Fn 1  Cn

 Cn −1 ... C(n 1) / 2 .

0 1 2

0 1 2

F5  C4

 C3  C2 ;

F6  C5

 C4  C3 .

Для доказательства (6) воспользуемся производящей функцией последовательности чисел Фибоначчи:

z

F(z) = F0 + F1z + F2z2 +… =

1− z − z 2

. (7)

Используя формулу для суммы членов бесконечно убывающей геометрической прогрессии, преобразуем правую часть равенства (7):

z

1− z − z 2

 z ⋅

1− ( z  z 2 )

= z(1 + (z + z2) + (z + z2)2 +…) =

низких, чем n + 1. Так как

z p 1 ∑C k z k k ≤ p

 ∑C k zk  p 1 ,

k ≤ p

то коэффициент при zn+1 получается суммированием по p всех

C k , что k + p +1 = n + 1 и k ≤ p.

Последние условия означают, что p = n – k и 2k ≤ n. Таким

C k k , 2k ≤ n, и

получаем сумму, стоящую в правой части (6), что и доказывает это равенство.

С учетом формулы Бине равенство (7) может быть записано

следующим образом:

1 1

n 1

5 

1 −

n 1

5 

−   .