Документ взят из кэша поисковой машины. Адрес оригинального документа : http://kvant.mccme.ru/pdf/2003/02/32.pdf Дата изменения: Fri Dec 23 19:27:20 2005 Дата индексирования: Tue Oct 2 00:31:07 2012 Кодировка: Windows-1251

КАЛЕЙДОСКОП

'КВАНТА'

Числа Фибоначчи
В 1202 году Леонардо Фибоначчи (Леонардо Пизанский) в 'Книге об абаке' рассмотрел последовательность 1, 1, 2, 3, 5, 8, 13, ... , каждый следующий член которой равен сумме двух предыдущих. Формулами это можно записать так: 1 = 2 = 1 , n + 2 = n + 1 + n . Пользуясь ими, можно посчитать сколь угодно много первых членов последовательности: В общем виде это можно записать так: 1 1+ = 1+ n = n + 1 n n + 1 + n n +2 = n +1 = n + 1 n + 1 . Следующий пример. Давайте выясним: сколькими способами можно разрезать полоску размером 2 Ч n на доминошки (т.е. прямоугольники размером 1 Ч 2 )? При маленьких n можно все нарисовать: обозначив искомое число способов через f (n ) , видим из рисунков 14, что сунка 6, т.е.
f (5) = f (4 ) + f ( 3) = 5 + 3 = 8 .

Вообще, при любом n > 1 верна рекуррентная формула

f (n + 1) = f (n ) + f (n - 1) .
Поскольку f ( 1) = 2 и f (2 ) = 3 , имеем

f (n ) = n + 1 .
Теперь выясним: сколько существует n-значных чисел, составленных из цифр 2 и 5, в которых никакие две двойки не стоят рядом? Обозначим искомое количество способов через g (n ) . Очевидно, g (1) = 2 и g (2 ) = 3 (годятся числа 25, 52 и 55). Легко выписать и трехзначные числа: 252, 255, 525, 552 и 555. Значит, g (3) = 5 . Впрочем, это значение находить даже и не обязательно. Важнее то, что любое интересующее нас (n + 1)значное число начинается либо с двойки, либо с пятерки. В первом случае после двойки должна идти пятерка, после которой любое из g (n - 1) чисел, во втором случае никаких ограничений пятерка не создает, так что годится любой из g (n ) вариантов. Мы получили рекуррентную формулу

n
n

1 1

2 1

3 2 11

4 3 12

5 5

6 8

7 13

8 21

n

9 10

13 14 15 16

n 34 55 89 144 233 37 7 610 987

Последовательность Фибоначчи возникает во многих задачах и обладает интересными свойствами. Например, рассмотрим выражения 12 1 3 1, 1 + = , 1 + =, 11 12 1+ 1 1 5 1+ =, 1 3 1+ 1 1+ 1 1 8 1+ =, 1 5 1+ 1 1+ 1 1+ 1 1 13 1+ = ... 1 8 1+ 1 1+ 1 1+ 1 1+ 1 Возникают дроби вида n + 1 n . Да оно и не удивительно: 1 1 1+ = 1+ = 1 13 8 1+ 1 1+ 1 1+ 1 1+ 1 1+ 1 8 13 + 8 2 1 . = 1+ = = 13 13 13

Рис. 1

Рис. 2

Рис. 3

Рис. 4

f ( 1) = 1 , f (2 ) = 2 , f ( 3) = 3 , f (4 ) = 5 . Как найти следующее значение, т.е. f (5) ? Да очень просто: левая верхняя клетка покрыта либо вертикально (рис.5), либо горизонтально

g (n + 1) = g (n - 1) + g (n ) ,
совпадающую с формулой Фибоначчи. Поскольку g ( 1) = 3 , g (2 ) = 4 , имеем

Рис. 5

(рис.6) расположенной доминошкой. Значит, f (5) вариантов

g (n ) = n + 2 . Опять последовательность Фибоначчи! На рисунке 7 числа Фибоначчи выражают длины сторон спиральной последовательности квадратов на клетчатой бумаге. Из этого рисунка очевидна формула
2 2 + 2 + 2 + K + n = n n +1 . 1 2 3

Рис. 6

распадаются на f ( 4) вариантов рисунка 5 и f ( 3) вариантов ри-

Между числами Фибоначчи есть и другие любопытные соот-