| Заглавная страница | Руководство пользователя | Практикум абитуриента | Учебные программы |
| Математический кружок | Занимательная математика| Формулы, словари | Новости |
|Странички истории | Экзамены, тесты | Библиография | Ссылки | Карта |


Числа Фибоначчи

Задача о кроликах.

Пусть имеется пара кроликов. Известно, что от каждой пары кроликов каждый месяц рождается новая пара кроликов, которая в свою очередь становится способной производить потомство в возрасте одного месяца. Требуется определить, сколько пар кроликов будет через n месяцев.

Вначале изложим историю этой задачи, затем её решение и другие задачи связанные с ней.

Говоря об античной математике, каждый назовет таких математиков, как Евклид, Пифагор, Герон и др. Одним из самых знаменитых математиков средних веков, наравне с Виетом был Леонардо из Пизы, известный под именем Фибоначчи (сокращенное filius Bonacci, т.е. сын Боначчи).

Фибоначчи родился в Италии в 1175г., был воспитан на Севере Африки, где его отец занимал пост дипломата. Вернувшись в Италию, в 1202г. публикует математический трактат под названием "Liber abacci". Этот трактат, содержавший почти все арифметические и алгебраические сведения того времени, сыграл главную роль в течении последующих столетий в развитии математики в Европе. В частности, на основе этого трактата, европейцы познакомились с арабскими цифрами, т.е. с позиционной системой исчисления. Также Фибоначчи публикует: в 1220г. "Practica geometrica", в 1225, "Liber quadratorum". Трактат "Liber abacci" был переиздан в 1228г. Одна из задач упоминаемая в "Liber abacci" называется "задача о кроликах" (с.123-124 издания 1228г.), представленная в начале этого материала.

Перейдем к решению этой задачи.

Пусть fn число пар кроликов после n месяцев. Число пар кроликов после n + 1 месяцев fn+1, будет равно числу пар на n-ом месяце, т.е. fn, плюс число пар новорожденных кроликов. Поскольку кролики рождаются от пары кроликов возраста больше одного месяца, новорожденных кроликов будет fn-1 пар. Следовательно, справедливо соотношение

fn+1 = fn + fn-1, (1)

причем
f0 = 0       f1 = 1. (2)

Таким образом получим рекуррентную числовую последовательность
0, 1, 1, 2, 3, 5, 8, ... (3)
которая была названа рядом Фибоначчи. Каждый член этой последовательности, начиная с третьего, равен сумме двух предыдущих. Первые два члена считаются заданными f0 = 0, f1 = 1.

Таким образом, "задача о кроликах" свелась к решению функционального уравнения (1), т.е. к нахождению общего члена последовательности fn удовлетворяющего соотношению (1) при условиях (2).

Предположим, что последовательность fn имеет вид
fn = ln, (4)
где l - вещественный параметр.

Подставив fn в (1) получим

ln+1 = ln + ln-1,
или, эквивалентно,
ln-1(l2 - l - 1) = 0.
Так как fn № 0     ("n О N*), последнее равенство принимает вид
l2 - l - 1 = 0, (5)
которое представляет собой квадратное уравнение по отношению к действительному параметру l. Из (5 ) получим
Таким образом, последовательности
удовлетворяют равенству (1). Отсюда заключаем, что уравнение (1) имеет много решений. В общем, существует бесконечное число последовательностей, удовлетворяющих (1). Легко заметить, что последовательность вида
(6)
где c1, c2 - фиксированные действительные константы, также удовлетворяет (1). Более того, можно показать, что любая последовательность, удовлетворяющая равенству (1) имеет вид (6). Имея другие цели, не будем доказывать этот факт в рамках этой работы. Для интересующихся общей теорией решения уравнений вида (1), называемых уравнениями в конечных разностях, рекомендуем обратиться к литературе [1]-[4].

Возвращаясь к последовательности Фибоначчи, отметим, что эта последовательность однозначно определена, и однозначность обеспечивается первыми двумя членами, т.е. начальными условиями (2). Подставляя n = 0 и n = 1 в (6), получим линейную систему

с решением

В результате получим, что n-ый член последовательности Фибоначчи имеет вид
(7)

Свойства последовательности Фибоначчи.

1°. f1 + f2 + ... + fn = fn+2 - 1. (8)

Доказательство.

f1 = f3 - f2
f2 = f4 - f3
...
fn-1 = fn+1 - fn
fn = fn+2 - fn+1.

Сложив все эти равенства почленно, получим

f1 + f2 + ... + fn = fn+2 - f2,
и так как f2 = 1, получим (8).

2°. f1 + f3 + f5 + ... + f2n-1 = f2n.

3°. f2 + f4 + ... + f2n = f2n+1 - 1.

Свойства 2° - 3° доказываются аналогично 1°.

4°. f12 + f22 + ... + fn2 = fn·fn+1. (9)

Доказательство. Легко заметить, что имеет место соотношение

fn·fn+1 - fn-1fn = fn(fn+1 - fn-1) = fn2     (n О N).

Из этого соотношения получаем равенства

f12 = f1·f2,
f22 = f2·f3 - f1·f2,
f32 = f3·f4 - f2·f3,
...
fn2 = fn·fn+1 - fn-1·fn.
Складывая эти равенства почленно получаем (9).

5°. Показать, что   fn+m = fn-1·fm + fn·fm+1, (10)
где fn обозначает n-ый член последовательности Фибоначчи.

Доказательство. Зная общий вид члена fn (см. (9)) можно подставив его в показать, что имеет место (10) равенство. Докажем (10) используя метод математической индукции. Проведем индукцию по m О N.

Для m = 1, равенство (10) примет вид

fn+1 = fn-1·f1 + fn·f2,
что очевидно. При m = 2 формула (10) также очевидна. Действительно,
fn+2 = fn-1f2 + fnf3 = fn-1 + 2fn = fn-1 + fn + fn = fn+1 + fn.

Таким образом, пусть основание индукции проверено (m = 1; m = 2). Пусть (10) верно для m = k и m = k + 1. Докажем, что тогда (10) верно и для m = k + 2.

Таким образом, пусть верны равенства

fn+k = fn-1fk + fnfk+1,
fn+k+1 = fn-1fk+1 + fnfk+2.
Суммируя почленно последниие равенства, получим равенство
fn+k+2 = fn-1·fk+2 + fn·fk+3,
которое представляет (10) при m = k + 2.

6°. f2n = fn-1fn + fn·fn+1.

Доказательство следует из (10) при m = n.

7°. Член f2n делится на fn.

Доказательство. Из 6° следует

f2n = fn(fn-1 + fn+1),
откуда следует, что f2n fn.

8°.

9°.

Свойства 8° - 9°, являющиеся прямыми следствиями 6°, предлагается доказать самостоятельно.

10°. fn2 = fn-1fn+1 + (-1)n+1 (11)

Доказательство. Будем доказывать равенство (11) индукцией по n. При n = 2 равенство (11) преобразуется в справедливое равенство

f22 = f1·f3 - 1,

Предположим, что равенство (11) справедливо для n и докажем, что тогда оно справедливо и для n + 1. Таким образом, пусть справедливо равенство

fn2 = fn-1·fn+1 + (-1)n+1.
Прибавим к обеим частям последнего равенства fn·fn+1. В результате получим
fn2 + fn·fn+1 = fn-1·fn+1 + fn·fn+1 + (-1)n+1,
или
fn(fn + fn+1) = fn+1(fn-1 + fn) + (-1)n+1,
и так как fn+2 = fn + fn+1 (см. определение последовательности Фибоначчи), заключаем что
fnfn+2 = fn+12 + (-1)n+1,
или
fn+12 = fn·fn+2 + (-1)n+2.
Следовательно (11) справедливо и для n + 1.

11°. Показать, что если n делится на m, то fn делится на fm.

Доказательство. Пусть n m, т.е. n = mk. Докажем свойство 11° индукцией по k. При k = 1, n = m, следовательно fn делится на fm. Предположим, что fmk делится на fm. Рассмотрим fm(k+1). Из равенства fm(k+1) = fmk+m на основании соотношения (10) получим

fm(k+1)2 = fmk-1fm + fmk·fm+1.
Первый член суммы из правой части равенства, очевидно, делится на fm. Второй член делится на fm согласно индукционному предположению. Следовательно сумма этих членов делится на fm, и значит, fm(k+1) fm. Свойство 11° доказано.

Для ознакомления с другими свойствами чисел Фибоначчи, связанными с делимостью, геометрией, теорией алгоритмов и т.д., читатель может обратиться к библиографии, указанной в конце этой работы.

Задачи для самостоятельного решения

  1. Пусть (fn)n О N последовательность Фибоначчи. Доказать, что

    1. f1f2 + f2f3 + f3f4 + ... + f2n-1·f2n = f2n2
    2. f1f2 + f2f3 + ... + f2nf2n+1 = f2n+12 - 1
    3. nf1 + (n - 1)f2 + ... + 2fn-1 + fn = fn+4 - (n + 3)
    4. f1 + 2f2 + 3f3 + ... + nfn = nfn+2 - fn+3 + 2

  2. Доказать, что для любого m О N, среди первых m2 - 1 чисел Фибоначчи существует число, делящееся на m.
  3. Доказать, что:

    1. Число Фибоначчи fn четно тогда и только тогда, когда n делится на 3;
    2. Число Фибоначчи fn делится на 3 тогда и только тогда, когда n делится на 4;
    3. fn 4 тогда и только тогда, когда n 6;
    4. fn 5 тогда и только тогда, когда n 5;
    5. fn 7 тогда и только тогда, когда n 8;
    6. fn 16 тогда и только тогда, когда n 12.

Литература
  1. A.I.Hincin, Fractii continue, Ed. Tehnica, Bucuresti 1960.
  2. I.Munteanu, D.Popa, Metoda sirurilor recurente, Editura GIL, ZALAU.
  3. Н.М.Воробьёв, Числа Фибоначчи, Москва, Наука, 1992.
  4. А.И.Маркушевич, Возврватные последовательности, Москва, Наука, 1975.


| Заглавная страница | Руководство пользователя | Практикум абитуриента | Учебные программы |
| Математический кружок | Занимательная математика| Формулы, словари | Новости |
|Странички истории | Экзамены, тесты | Библиография | Ссылки | Карта |