Комбинаторные алгоритмы для программистов

         

Линейные рекуррентные соотношения с постоянными коэффициентами


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

(8.3)

где

- некоторые числа. Такие соотношения называют линейными рекуррентными соотношениями с постоянными коэффициентами.

Сначала рассмотрим, как решаются такие соотношения при

, то есть изучим соотношение вида

(8.4)

Решение этих соотношений основано на следующих двух утверждениях.

  1. Если
    и
    являются решениями рекуррентного соотношения (8.4), то при любых числах
    и

    последовательность

    также является решением этого соотношения.

    В самом деле, по условию, имеем

    Умножим эти равенства на

    и
    соответственно и сложим полученные тождества. Получим, что

    А это означает, что

    является решением соотношения(8.4).

  2. Если
    является корнем квадратного уравнения

    то последовательность

    является решением рекуррентного соотношения

    В самом деле, если

    , то
    и
    . Подставляя эти значения в соотношение (8.4), получаем равенство

    Оно справедливо, так как по условию имеем

    . Заметим, что наряду с последовательностью
    любая последовательность вида

    также является решением соотношения (8.4). Для доказательства достаточно использовать утверждение (8.4), положив в нем



Из утверждений 1 и 2 вытекает следующее правило решения линейных рекуррентных соотношений второго порядка с постоянными коэффициентами.

Пусть дано рекуррентное соотношение

(8.5)

Составим квадратное уравнение

(8.6)

которое называется характеристическим для данного соотношения. Если это уравнение имеет два различных корня

, то общее решение соотношения (8.5) имеет вид

Чтобы доказать это правило, заметим сначала, что по утверждению 2

являются решениями нашего соотношения. А тогда по утверждению 1 и
является его решением. Надо только показать, что любое решение соотношения (8.5) можно записать в этом виде. Но любое решение соотношения второго порядка определяется значениями
. Поэтому достаточно показать, что система уравнений

имеет решение при любых

.
Этими решениями являются




(Случай, когда оба корня уравнения (8.6) совпадут друг с другом, разберем в следующем пункте.)

Пример на доказанное правило.

При изучении чисел Фибоначчи мы пришли к рекуррентному соотношению


(8.7)
Для него характеристическое уравнение имеет вид


Корнями этого квадратного уравнения являются числа


Поэтому общее решение соотношения Фибоначчи имеет вид


(8.8)
(Мы воспользовались сделанным выше замечанием и взяли показатели


вместо
). Мы называли числами Фибоначчи решения соотношения (8.7), удовлетворяющее начальным условиям
( то есть последовательность
). Часто бывает более удобно добавить к этой последовательности вначале числа 0 и 1, то есть рассматривать последовательность
Ясно, что эта последовательность удовлетворяет тому же самому рекуррентному соотношению (8.6) и начальным условиям
. Полагая в формуле (8.6)
, получаем для


систему уравнений




Отсюда находим, что
и потому


(8.9)
На первый взгляд кажется удивительным, что это выражение при всех натуральных значениях
принимает целые значения.


Содержание раздела