Данное соотношение легко доказать по индукции. Но существует и более сложный метод. Он начинается с простого доказательства по индукции матричного тождества

V F„ Fn-J Vl о)

Теперь, вычислив определители обеих частей этого равенства, получим (4).

Из формулы (4) следует, что числа F„ и Fn+i являются взаимно простыми, так как любой их общий делитель должен быть также делителем (-1)".

Из определения (2) непосредственно следует, что

Fn+3 = Fn+2 + Fn+1 = 2F„+i + Fn; Fn+4 - Fn+i -(- 2F„. В общем случае по индукции получаем, что

Fn+m = FmFn+l + Fm-\Fn (6)

ДЛЯ любого положительного целого т.

Если в (6) взять т, кратное п, то по индукции находим, что

Fnk кратно Fn.

Следовательно, каждое третье число последовательности Фибоначчи является четным, каждое четвертое кратно 3, каждое пятое кратно 5 и т. д.

На самом деле справедливо намного более сильное утверждение. Если наибольший общий делитель чисел тип обозначить через gcd(m,n)*, то можно сформулировать следующую удивительную теорему.

Теорема А (Э. Люка, 1876). Некоторое целое число делит и F, и Fn тогда и только тогда, когда оно является делителем Fd, где d - gcd(m, n); в частности,

gcd(F,„,F„) = Fgcd(m,„). t7)

Доказательство. Для доказательства данной теоремы используется алгоритм Евклида. Из (6) следует, что любой общий делитель Fm и jF„ является также делителем Fn+mi И наоборот, любой общий делитель Fn+m и Fn является делителем FmFn+i-Поскольку Fn+i и Fn взаимно просты, общий делитель Fn+m и Fn также делит Fm-Таким обр£130м мы доказали, что для любого числа d

d делит Fm и Fn тогда и только тогда, когда d делит Fm+n " Fn- (8)

а теперь покажем, что любая последовательность {Fn), для которой Fq о и выполняется утверждение (8), удовлетворяет теореме а.

Сначала, воспользовавшись индукцией по к, обобщим утверждение (8) следующим образом:

d делит Fm и Fn тогда и только тогда, когда d делит Fm+kn и F„,

где к - любое неотрицательное целое число. Этот результат можно сформулировать более сжато:

d делит Fm mod n и F„ тогда и только тогда, когда d делит Fm и Fn- (9)

Greatest common divisor - наибольший общий делитель. - Прим. перев.

Пусть г - остаток от деления числа m на п, т. е. г = т mod п. Тогда общие делители {Fm,Fn] являются общими делителями {F„,Fr}- Отсюда следует, что в процессе выполнения алгоритма 1.1Е множество общих делителей чисел {Fm-,Fn] остается неизменным при изменении m и п. И наконец, при г = О общие делители - это

просто делители чисел Fq - О и Fgccl(m,n)- I

Большинство важных результатов, связанных с числами Фибоначчи, можно вывести из формулы, в которой числа F„ выражаются через ф. Эту формулу мы сейчас и получим. Метод, которым мы воспользуемся, чрезвычайно важен, поэтому читателю, интересующемуся математикой, следует внимательно его изучить. Данный метод будет подробно рассматриваться в следующем разделе.

Для начала рассмотрим бесконечный ряд

G{z) = Fo + Fiz + F2Z + F3Z + Fz" + •

= г + 2 + + Зг" + • • •. (10)

У нас нет никакой причины заранее ожидать, что этот бесконечный ряд сходится или что функция G{z) вообще представляет какой-либо интерес. Но давайте будем оптимистами и посмотрим, что можно сказать о функции G{z), если бесконечный ряд сходится. Преимущество подобного метода заключается в том, что G{z) представляет всю последовательность Фибоначчи одновременно. Если же мы выясним, что представляет собой функция G{z), то сможем определить ее коэффициенты. G{z) называется производящей функцией для последовательности (F„). Теперь перейдем к исследованию функции G{z):

zG{z) = Foz + Fi2 + f203 + F3Z* + zGiz) = Foz + Fiz + F2Z +

Вычитая два эти равенства из (10), получаем

(1 - г - z)G{z) = Fo + (Fl - Fo) + (F2 - Fl - Fo)

+ (f3 - F2 - Fi)3 + (f4 - f3 - F2) + • • •.

Из определения F„ следует, что все члены, кроме второго, обращаются в нуль. Так как (Fl - Fo) - 1, значение выражения в правой части равно z. Следовательно, если ряд (10) сходится, то

G{z) = zl{l-z-z). (11)

Эту функцию на самом деле можно представить в виде бесконечного ряда по степеням z (ряд Тейлора); отсюда следует, что коэффициенты степенного ряда для функции (11) должны быть числами Фибоначчи.

Теперь давайте выполним некоторые операции над G{z), чтобы больше узнать о последовательности Фибоначчи. В формуле (11) знаменатель \ - z - z представляет собой квадратный трехчлен; решив соответствующее квадратное уравнение, найдем два корня \{-\±\/Ъ). После выполнения несложных преобразований можно разложить функцию G{z) на элементарные дроби:

/ 1 1

С(г)-- ------], (12)

у/Ъ - фг I- фг

= 1-,/,= i(l-V5). (13)

Величина 1/(1 - фг) представляет собой сумму геометрической прогрессии 1 + фг + фг Н----, поэтому

С(г) = {1 + фг + /г + ... i 22 ... V5

Коэффициенты при г" должны быть равны F„, поэтому

Рп= {Ф" - Г). (14)

Это важное выражение в замкнутой форме для чисел Фибоначчи было впервые получено в начале 18 века (См. D. Bernoulli, Comment. Acad. Sci. Petrop. 3 (1728), 85-100, §7; a также A. de Moivre, Philos. Trans. 32 (1922), 162-178. Де Муавр показал, как решать линейные рекуррентные соотношения общего вида. Он сделал это практически так же, как и мы при выводе формулы (14).)

Можно было бы просто привести формулу (14) и доказать ее по индукции. Но мы дали ее довольно длинное доказательство, в первую очередь, для того, чтобы показать, как открывать формулы с помощью метода производящих функций, который очень важен для решения многих задач.

Из формулы (14) можно вывести много важных фактов. Прежде всего, отметим, что ф-это отрицательное число (-0.61803...), мод>ль которого меньше единицы. Поэтому с увеличением п последовательность " убывает. Фактически величина всегда настолько мала, что можно принять

Fn = ф"/л/5, округленное до ближайшего целого числа. (15)

Другие результаты можно непосредственно получить из определения С{г), например

<( = к 71-ТТ2 + п-- 1-2 (6

5 \[1 - фг)- {1-фг) 1 - г - г J

а коэффициент при г" в формуле для 0{г) равен }2к=о kFn-k- Отсюда получаем

FfeF„ fc = i((n + 1)(<" + ФП ~ 2Fn+i)

= i({n + l)(F„+2F„-,)-2F„+i) = i(n-l)F„ + nF„ b (17)

(Второй шаг в этих выкладках следует из результата упр. 11.)

УПРАЖНЕНИЯ

1. [10] Решите первоначальную задачу, поставленную Леонардо Фибоначчи: сколько пар кроликов будет в наличии через год?

► 2. [20] С помощью формулы (15) найдите приближенное значение Fiooo- (Возьмите значения логарифмов из таблицы, приведенной в приложении А.)