Однородные и неоднородные линейные рекуррентные соотношения

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

Определение. Последовательность называется возвратной, если для некоторого k и всех n выполняется соотношение вида

(13)

где постоянные коэффициенты p_i;i=1;2;…;k не зависят от n.

Многочлен (14)

называется характеристическим многочленом для возвратной последовательности.

Соотношение (15)

называют однородным линейным рекуррентным соотношением.

Из формулы (15) найдем общий член , для этого достаточно найти производящую функцию последовательности - функцию . Введем вспомогательный многочлен и рассмотрим произведение , при этом степень С(t) не превышает k-1, поскольку коэффициенты при t^n+k ,k=0;1;… будут равны нулю в силу уравнения (15). Пусть характеристическое уравнение (14) имеет простые (может быть кратные) корни, т.е. допускает разложение вида . Тогда ,

.

Характеристическую функцию можно представить в виде

(16)

Известно, что , то , и, следовательно, . (17)

Формула (17) дает разложение производящей функции последовательности . Для нахождения формулы общего члена необходимо найти коэффициенты при tⁿ в разложении (17).

Пример1. Найти общий член последовательности , удовлетворяющей рекуррентному соотношению .

Решение. Перепишем исходное рекуррентное соотношение в виде (15)

Характеристический многочлен L(t) имеет вид , тогда

,

Т.к. тогда .

Методом неопределенных коэффициентовполучим

.

Способы нахождения общего решения рекуррентных соотношений:

1. Если возвратная последовательность (13) полностью определяетсязаданием еепервых k членов, то

…………………………………….

.
2. Если t является корнем характеристического многочлена (14), то последова- тельность {tⁿ} удовлетворяет соотношению (13), тогда .

3. Если t_1;t₂;…;t_k простые (некратные) корни характеристического многочлена(14), тогда общее решение рекуррентного соотношения (13) имеет вид

, (18)

где с₁;с₂;…;с_к – подходящие константы.

4. Если есть корень многочлена (14) кратности , то общее решение рекуррентного соотношения (13) имеет вид

, (19)

где с_i,j=1;2;…;r; j=1;…;- произвольные константы, r – количество кратных корней.

Пример 2. Найти общее решение для примера 1.

Решение. Характеристический многочлен имеет корни t₁=1; t₂=3, тогда по формуле (18) получим .

Пример 3. Решить неоднородное рекуррентное соотношение.