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

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

(8.3)

где

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

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

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

(8.4)

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

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

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

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

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

А это означает, что
является решением соотношения(8.4).
Если
является корнем квадратного уравнения

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

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

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

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

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

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

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

(8.5)

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

(8.6)

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

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

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

являются решениями нашего соотношения. А тогда по утверждению 1 и

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

. Поэтому достаточно показать, что система уравнений

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

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

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

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

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