Линейные рекуррентные соотношения с постоянными коэффициентами. Общий метод решения рекуррентных соотношений.

Опр. Пусть имеется {a_n}. Пусть для всех членов этойпослед-ти, начиная с r-го выполняется(*): , где с₁…с_r=const. Тогда говорят, что на послед-ти {a_n} задана лин. однор. рек. соотн. с пост. коэфф. порядка r.

Зам.: очевидно, что зная соотношения (*) и первые r членов послед-ти можно найти любой член послед-ти. В общем случае этот способ полная лажа.

Опр.: Решить соотношение (*), значит, найти n-й член соответствующей послед-ти как ф-ю от n.

Общий метод решения:

Для того, чтобы решить соотнош. (*), достаточно найти приводящую ф-ю соответствующей послед-ти.

Пусть есть (*). Найти a_n=A(n). A(x)-? Рассмотрим многочлен k(x): k(x)=1-c₁x-c₂x-…-c_rx^r. K(x)*A(x)=C(x). Можно показать, что мн-н С(х) обладает таким св-ом: degC(x) ≤ r-1. A(x)=C(x)/K(x).

Дата добавления: 2015-07-20