Рекуррентные соотношения

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

Понятие рекуррентных соотношений проиллюстрируем классической проблемой, которая была поставлена около 1202 года Леонардо из Пизы, известным как Фибоначчи. Важность чисел Фибоначчи для анализа комбинаторных алгоритмов делает этот пример весьма подходящим.

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

Пусть

$Рекуррентные соотношения$

- число пар кроликов в популяции по прошествии

$Рекуррентные соотношения$

месяцев, и пусть эта популяция состоит из

$Рекуррентные соотношения$

пар приплода и

$Рекуррентные соотношения$

"старых" пар, то есть

$Рекуррентные соотношения$

. Таким образом, в очередном месяце произойдут следующие события:

$Рекуррентные соотношения$

. Старая популяция в

$Рекуррентные соотношения$

-й момент увеличится на число родившихся в момент времени

$Рекуррентные соотношения$

. Каждая старая пара в момент времени

$Рекуррентные соотношения$

производит пару приплода в момент времени

$Рекуррентные соотношения$

. В последующий месяц эта картина повторяется:

$Рекуррентные соотношения$

Объединяя эти равенства, получим следующее рекуррентное соотношение:

$Рекуррентные соотношения$

(7.1)

Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенное свойство этой последовательности определяется рекуррентным соотношением. Будем предполагать

$Рекуррентные соотношения$

(иногда

$Рекуррентные соотношения$

Рассмотрим эту задачу немного иначе.

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

Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары.
А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через

$Рекуррентные соотношения$

количество пар кроликов по истечении

$Рекуррентные соотношения$

месяцев с начала года. Ясно, что через

$Рекуррентные соотношения$

месяцев будут эти

$Рекуррентные соотношения$

пар и еще столько новорожденных пар кроликов, сколько было в конце месяца

$Рекуррентные соотношения$

, то есть еще

$Рекуррентные соотношения$

пар кроликов. Иными словами, имеет место рекуррентное соотношение

$Рекуррентные соотношения$

(7.2)

Так как, по условию,

$Рекуррентные соотношения$

, то последовательно находим

$Рекуррентные соотношения$

и т.д.

В частности,

$Рекуррентные соотношения$

.

Числа

$Рекуррентные соотношения$

называются числами Фибоначчи. Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через

$Рекуррентные соотношения$

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

Найти число
$Рекуррентные соотношения$
последовательностей,состоящих из нулей и единиц, в которых никакие две единицы не идут подряд.

Чтобы установить эту связь, возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями - все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию": сама пара появилась в конце 11-го месяца, ее родители - в конце 7-го месяца, "дед" - в конце 5-го месяца и "прадед" - в конце второго месяца. Исходная пара кроликов тогда зашифровывается последовательностью 000000000000.

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

Установленная связь показывает, что число

$Рекуррентные соотношения$

-последовательностей, обладающих указанным свойством, равно

$Рекуррентные соотношения$

.

Докажем теперь, что

$Рекуррентные соотношения$