Линейное рекуррентное соотношение.
Соотношение вида
an+k+p1an+k-1+…+pkan=h(n) (2)
где h(n) – функция от числа , а , называется линейным рекуррентным соотношением.
Линейное рекуррентное соотношение называют однородным, если f(n)=0:
an+k+p1an+k-1+…+pkan=0. (3)
Многочлен xk+p1xk-1+…+pk-1x+pk называется характеристическим для соотношения (2).
Корень a многочлена называется простым, если делится на , но не делится на .
Корень a многочлена называется кратным, если делится на , но не делится на , .
При этом число называется кратностью корня .
Основная теорема алгебры: многочлен степени с комплексными коэффициентами имеет комплексных корней с учетом их кратности.
Теорема 1. Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет n простых корней a1, …, an. Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:
, (4)
где c1,…,ckÎC.
Доказательство. Легко проверить следующие два утверждения.
(a) Последовательность cxn, где cÎC, является решением рекуррентного соотношения (3).
(b) Если последовательности an и bn являются решениями соотношения (3), то последовательность an+bn также является решением соотношения (3).
Из (a) и (b) следует, что любая последовательность вида (4) является решением соотношения (3).
Обратно, любое решение соотношения (3) имеет вид (4).
При n=0,1,…,k-1, из равенства (4) мы получим систему линейных уравнений относительно c1,…,ck:
(5)
Определитель системы (5) есть известный в алгебре определитель Вандермонда:
.
Так как простые корни x1,…,xk попарно различные, то D¹0. Значит, система (5) имеет (единственное) решение.
Теорема 2. Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет k корней: a1 кратности , …, ak кратности , , . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:
, (6)
где .
Замечание. Общее решение неоднородного линейного соотношения (2) можно найти как сумму общего решения однородного линейного соотношения (3) и частного решения неоднородного линейного соотношения (2).