Портал | Содержание | О нас | Авторам | Новости | Первая десятка | Дискуссионный клуб | Чат Научный форум --> Первая десятка "Русского переплета" Темы дня:

Президенту Путину о создании Института Истории Русского Народа. |Нас посетило 40 млн. человек | Чем занимались русские 4000 лет назад?

| Кому давать гранты или сколько в России молодых ученых?

Рассказано о числах Фибоначчи, некоторых их свойствах. Основное внимание уделено рассказу о том, какое множество на плоскости образует точки, координатами которых являются пары последовательных чисел Фибоначчи. Эта задача решается также для более общего случая возвратных последовательностей второго порядка.

И ДРУГИХ ВОЗВРАТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ВТОРОГО ПОРЯДКА

А. А. АРТЕМОВ

Тамбовский государственный университет имени Г.Р. Державина

1. ЗАДАЧА О КРОЛИКАХ

Рассмотрим известную задачу Фибоначчи о кроликах. Сколько пар кроликов образуется от одной пары в течение года, если новорожденные кролики достигают зрелости в течение месяца, а зрелая пара каждый месяц производит новую пару?

Итак, в начальный момент есть одна пара кроликов. Через месяц она достигает зрелости, но по-прежнему имеется только одна пара кроликов. К концу второго месяца она производит еще одну пару, всего число пар кроликов равно двум, причем среди них лишь одна зрелая. К концу третьего месяца зрелая пара производит еще пару кроликов, общее число пар будет равно трем, зрелых среди них уже две пары. К концу четвертого месяца всего пар будет пять, из них три зрелые. К концу пятого месяца будет восемь пар, из них пять зрелых и т.д.

Запишем получившуюся последовательность чисел

1, 1, 2, 3, 5, 8, _

Эту последовательность называют последовательностью Фибоначчи, ее члены - числами Фибоначчи. Легко заметить, что каждый член последовательности Фибоначчи (начиная с третьего) равен сумме двух предыдущих членов. В самом деле, обозначим число имеющихся пар кроликов к концу n-го месяца через un . Тогда к концу (n + 1)-го месяца зрелыми будут именно эти un пар, а всего пар кроликов будет un + 1 . Тогда еще через месяц число пар кроликов получится равным

un + 2 = un + 1 + un .

Теперь с помощью равенства (2) каждый может продолжить последовательность (1) и найти ответ на задачу о кроликах. К концу двенадцатого месяца число пар кроликов окажется равным u12 = 233.

2. НЕКОТОРЫЕ СВОЙСТВА

ЧИСЕЛ ФИБОНАЧЧИ

Рассмотрим числовую последовательность

u0 , u1 , u2 , _, un , _,

удовлетворяющую уравнению (2).

Отметим сразу же, что условием (2) последовательность (3) не определяется однозначно. Другими словами, последовательность (3) необязательно совпадает с последовательностью (1) чисел Фибоначчи. Можно составить бесконечно много различных числовых последовательностей, удовлетворяющих уравнению (2). Для однозначного определения последовательности (3) следует задать еще два первых ее члена. В случае u0 = u1 = 1 имеем последовательность (1). При другом задании u0 , u1 получим другие последовательности, например

2, 5, 7, 12, 19, 31, _,

1, - 4, - 3, - 7, -10, -17, _

Все эти и другие последовательности, удовлетворяющие уравнению (2), обладают замечательными свойствами. Отметим некоторые из них.

а. Для любого члена uk последовательности (3) из формулы (2) имеем

uk = uk + 2 - uk + 1 .

Просуммируем равенство (4) по k от 1 до n:

Получим

или

u1 + u2 + u3 + _ + un = un + 2 - u2 .

Таким образом, сумма первых n членов последовательности (3) есть (n + 2)-й ее член, уменьшенный на u2 .

б. На основании формулы (2) запишем

uk + 1 = uk + 2 - uk .

Просуммировав равенство (6) по всем четным k от 0 до 2n - 2 , получим

u1 + u3 + u5 + _ + u2n - 1 = u2n - u0 ,

то есть сумма первых n членов последовательности (3) с нечетными номерами равна 2n-му ее члену, уменьшенному на u0 .

в. Из (5) и (7) как следствие получаем

u2 + u4 + u6 +_ + u2n = u2n + 1 - u1 ,

то есть сумма первых n членов последовательности (3) с четными номерами равна (2n + 1)-му ее члену, уменьшенному на u1 .

г. Каждый, кто знает свойства чисел Фибоначчи и их аналогов - решений уравнения (2), может продемонстрировать способности быстрого счета (см. свойства а-в). Приведем еще один пример.

Следует попросить зрителей назвать два любых числа. Далее по закону (2) образовать еще восемь чисел и быстро вычислить сумму получившихся десяти последовательных чисел Фибоначчи. Она равна седьмому из чисел, умноженному на 11. Непосредственное вычисление суммы будет длиться много дольше.

Докажем указанное свойство

u1 + u2 + _ + u10 = 11u7 .

Для этого на каждом шаге будем по формуле (2) члены, подчеркнутые одной чертой, сворачивать в один, а члены, подчеркнутые двумя чертами, разбивать в сумму двух. Итак, имеем

Тем самым (8) доказано.

Более подробно о числах Фибоначчи и их свойствах см. [2].

3. "ГЕОМЕТРИЯ" ЧИСЕЛ ФИБОНАЧЧИ

Рассмотрим следующую задачу. Изобразим точками плоскости xOy пары последовательных чисел из последовательности (3), удовлетворяющей уравнению (2):

(x, y) = (un , un + 1).

Получим последовательность пар

(u1 , u2), (u2 , u3), (u3 , u4), _, (un , un + 1), _

Выясним, на каких линиях лежат эти точки. Рассмотрим для этого определитель

Применяя выражение (2) для un + 2 , имеем Wn = = - Wn - 1 . Поступая так же с Wn - 1 и т.д., получим

Wn = (-1)n " C,

где постоянная C определяется по первым двум членам последовательности (3). Из (10) и (11), переходя к x, y, окончательно получим, что все члены последовательности (3) лежат на кривых

x2 + xy - y2 = ? C.

При C ? 0 это две сопряженные равносторонние гиперболы (см. приложение). В частности, для чисел Фибоначчи (1) точки (9) суть (1, 1), (1, 2), (2, 3), (3, 5), (5, 8), (8, 13), (13, 21), (21, 34), (34, 55), _ Они лежат на гиперболах (здесь C = -1)

x2 + xy - y2 = ? 1.

Уравнения (12) задают пару сопряженных равносторонних гипербол с квадратом фокального параметра (рис. 1).

Асимптотами гипербол служат прямые y = k1x и y = = k2x, где k1 , k2 - корни уравнения k2 - k - 1 = 0, а именно

Точки (9) принадлежат двум ветвям этих гипербол, лежащим выше прямой y = k2x (см. рис. 1). Причем точки (un , un + 1) с нечетным n лежат на правой ветви, а с четным n - на левой ветви. Заметим здесь, что последовательность (1) можно, используя выражение (4), продолжить влево:

_, - 55, 34, - 21, 13, - 8, 5, - 3, 2, -1, 1, 0,

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, _

4. ВОЗВРАТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ

Рассмотрим последовательность

u1 , u2 , u3 , _, un , _

Если для этой последовательности существует натуральное число k и числа a1 , a2 , _, ak (ak ? 0), такие, что начиная с (k + 1)-номера имеет место

un + k = a1un + k - 1 + a2un + k - 2 + _ + akun ,

то такая последовательность называется возвратной (или рекуррентной) последовательностью порядка k, а соотношение (13) - возвратным (или рекуррентным) уравнением порядка k.

Приведем примеры возвратных последовательностей.

Геометрическая прогрессия задается уравнением

un + 1 = qun .

Здесь k = 1, a1 = q. Следовательно, геометрическая прогрессия есть возвратная последовательность первого порядка.

Арифметическая прогрессия. Из школьного курса известен признак арифметической прогрессии: каждый ее член, начиная со второго, есть среднее арифметическое соседних с ним членов:

Отсюда

un + 2 = 2un + 1 - un .

Здесь k = 2, a1 = 2, a2 = -1. Таким образом, арифметическая прогрессия является возвратной последовательностью второго порядка.

Последовательность Фибоначчи также является примером возвратной последовательности второго порядка (см. (2)). Для нее k = 2, a1 = a2 = 1.

Элементы общей теории возвратных последовательностей в популярном изложении и их примеры рассмотрены в [4] (см. также [1]). Более глубокое изложение см., например, в [3]. Отметим лишь некоторые факты из этой теории.

Для каждого возвратного уравнения порядка k существует бесконечно много различных удовлетворяющих ему последовательностей, называемых решениями этого уравнения. Каждое такое решение есть линейная комбинация базисных решений, число которых совпадает с порядком k возвратного уравнения. Базисные решения линейно независимы. Для их нахождения решают уравнение

lk = a1lk - 1 + a2lk - 2 + _ + ak ,

называемое характеристическим уравнением, соответствующим уравнению (13). Если все корни уравнения (14) различны, то в качестве базиса можно брать k геометрических прогрессий с различными знаменателями, являющимися корнями характеристического уравнения (14).

Так, для чисел Фибоначчи (1) характеристическое уравнение и его корни k1 , k2 см. в разделе 3. Поэтому для чисел Фибоначчи имеет место формула Бине

Хотя эта формула содержит иррациональные выражения, мы видим, что удивительным образом все иррациональности исчезают и в результате формула дает целые числа, именно члены последовательности (1).

5. ИЗОБРАЖЕНИЕ ВОЗВРАТНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ

ПЕРВОГО И ВТОРОГО ПОРЯДКОВ

Рассмотрим возвратное уравнение

un + 2 = рun + 1 + qun .

При q = 0 получим уравнение первого порядка, решением которого является геометрическая прогрессия со знаменателем р. При q ? 0 получим уравнение второго порядка. Заметим, что всякая арифметическая прогрессия удовлетворяет уравнению (15) с p = 2, q = -1. При p = q = 1 решением уравнения (15) является последовательность чисел Фибоначчи. Поэтому последовательности, являющиеся решениями уравнения (15), можно считать в некотором смысле обобщениями чисел Фибоначчи.

Рассмотрим для этих последовательностей задачу, решенную нами в разделе 3 для чисел Фибоначчи. Изобразим на плоскости хОу точки последовательности (9), получающейся из решений уравнения (15).

Найдем для этого определитель (он называется определителем Вронского)

двух решений un и un уравнения (15). Используя условие (15), получаем

откуда следует, что

Wn = (- q)n " C.

Пусть un - решение уравнения (15). Убрав из последовательности un первый член, получим ее подпоследовательность un + 1 , которая тоже является решением уравнения (15). Определитель Вронского этих двух решений

Приравняв правые части (16) и (17), получим уравнение, дающее зависимость между un и un + 1 :

Правая часть этого равенства не зависит (или почти не зависит) от n только при q = 0, ?1.

Рассмотрим эти случаи. Полагаем, что C ? 0. Случай C = 0 в различных ситуациях предлагаем проанализировать читателям.

Пусть q = 0. В этом случае, как уже отмечалось, мы получаем геометрическую прогрессию. Точки (un , un + 1) тогда лежат на прямой у = рx, проходящей через начало координат. Угловой коэффициент прямой есть знаменатель геометрической прогрессии (рис. 2).

Пусть q = 1. Тогда из (17) получаем, что точки (un , un + 1) лежат на кривых

x2 + pxy - y2 = ? C.

При p = 1 этот случай был нами рассмотрен в разделе 3. При других p результат аналогичен: эти кривые суть (при C ? 0) две сопряженные равносторонние гиперболы, для которых квадрат фокального параметра равен По поводу исследования уравнения кривой см. приложение. Здесь инвариант

Пусть теперь q = -1. Тогда точки (un , un + 1) лежат на кривой второго порядка

x2 - рxy + y2 = C.

Рассмотрим различные случаи в зависимости от знака инварианта (см. приложение), то есть в зависимости от того, больше, меньше или равно двум число | р |.

При | р | = 2 уравнение (18) определяет пару параллельных прямых. Именно, при p = 2 - пару прямых (y - x)2 = C (C > 0); в частности для арифметической прогрессии с разностью d точки (9) лежат на прямой y = x + d - одной из указанных прямых с C = d 2. При p = = - 2 - пару прямых (y + x)2 = C (C > 0) (рис. 3).

Если | р | > 2, то уравнение (18) задает гиперболу, осями которой служат биссектрисы координатных углов (рис. 4).

В случае | р | < 2 уравнение (18) задает эллипс с центром в начале координат, осями которого также являются биссектрисы координатных углов.

Например, последовательность (C = 4)

0, 2, 2, 0, - 2, - 2, 0, 2, _

является решением уравнения

un + 2 = un + 1 - un ,

получающегося при р = 1. При этом последовательность пар (9) лежит на эллипсе, изображенном на рис. 5.

ПРИЛОЖЕНИЕ

Линией второго порядка называется множество точек плоскости, координаты которых в прямоугольной декартовой системе координат удовлетворяют алгебраическому уравнению второй степени:

a11x2 + 2a12xy + a22y2 + 2a13x + 2a23y + a33 = 0.

У нас встречаются уравнения вида

ax2 + 2bxy + cy2 = h.

Как следует из общей теории кривых второго порядка (см., например, [5] или любой учебник по аналитической геометрии), для определения вида линии (19) используют инвариант

Возможны следующие случаи.

I. Если D > 0, то уравнение (19) определяет линию эллиптического типа, именно:

a) эллипс (при (a + c)h > 0),

б) точку (при h = 0).

II. Если D < 0, то уравнение (19) определяет линию гиперболического типа, именно:

a) гиперболу (при h ? 0);

б) пару пересекающихся прямых (при h = 0).

III. Если D = 0, то уравнение (19) определяет линию параболического типа, именно:

a) пару параллельных прямых (при (a + c)h > 0);

б) пару совпадающих параллельных прямых (при (a + c)h = 0).

Заметим, что уравнение линии второго порядка можно привести (в некоторой системе координат) к одному из девяти канонических видов (см. [5]).

ЛИТЕРАТУРА

1. Виленкин Н.Я. Комбинаторика. М.: Наука, 1969. 328 с.

2. Воробьев Н.Н. Числа Фибоначчи. М.: Наука, 1984. 144 с.

3. Гельфонд А.О. Исчисление конечных разностей. М.: Наука, 1967. 479 с.

4. Маркушевич А.И. Возвратные последовательности. М.: Наука, 1983. 48 с.

5. Математический энциклопедический словарь. М.: Сов. энциклопедия, 1988. 847 с.

Рецензент статьи Ю.П. Соловьев

* * *

Анатолий Анатольевич Артемов, кандидат физико-математических наук, доцент кафедры математического анализа Тамбовского государственного университета им. Г.Р. Державина. Область научных интересов - асимптотические разложения, теория представлений групп, гармонический анализ на однородных пространствах. Автор 23 публикаций.