logo
Коды и шифры

Глава 6 м5. Последовательность чисел Фибоначчи

Через Un обозначим n-й элемент последовательности. Тогда последовательность порождается линейной рекуррентой

U(n+1) = Un + U(n-1), где U0 = 0 и U1 = 1.

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

,

где A, B,  и  являются константами. Подставим это выражение в данную рекурренту. Чтобы общий член последовательности имел такой вид, необходимо, чтобы  и  являлись корнями квадратного уравнения

X2 - X - 1 = 0.

Если в качестве  взять положительный корень уравнения, то имеем:

и ,

или, в десятичной записи,  = 1.6180... и =-0.6180...

Значения A и B находим, налагая начальные условия Un = 0 и U1 = 1, откуда получаем:

A = -B =  .

Для больших значений n элемент последовательности Un равен целому числу, ближайшему к An, так что каждый элемент приблизительно в 1.6180... раз больше предыдущего. Поэтому 8-й элемент равен целому числу, ближайшему к

.

Это значение (с точностью до трех десятичных знаков) равно 21.006; ближайшее целое число поэтому равно 21. И действительно, 8-й элемент последовательности чисел Фибоначчи равен 21.

Описание свойств последовательности чисел Фибоначчи можно найти во многих книгах по элементарной теории чисел. Эта последовательность имеет давнюю историю. Фибоначчи, также известный под именем Леонардо из Пизы, привел ее в своей книге "Liber Abaci"*) в 1207 году. Эта последовательность обладает большим количеством различных свойств: например, каждый 5-й ее элемент делится на 5, каждый 8-й ее элемент делится на 7, а каждый 10-й элемент делится на 11. Подобные свойства, хоть и красивые с математической точки зрения, делают эту последовательность совершенно непригодной с криптографических позиций. Те, кто желает подробно изучить эту последовательность, могут обратиться к [6.5]. Также выпускается журнал, посвященный изучению последовательности Фибоначчи и других линейных последовательностей (см. [6.6]). Материалы по смежной тематике можно найти также в статьях, посвященных непрерывным дробям (см. [6.7]).