Общие и частные решения рекуррентных соотношений.

Общим решением рекуррентного соотношения (1) называется множество всех последовательностей, удовлетворяющих этому соотношению.

Частным решением соотношения (1) называется одна из последовательностей, удовлетворяющих этому соотношению.

Пример 1¢. Последовательность an=a0+nd является общим решением соотношения an=an-1+d. Это – формула общего члена арифметической прогрессии с разностью d и с начальным членом прогрессии a0.

Пример 2¢. Последовательность bn=b0×qn является общим решением соотношения bn=bn-1×q. Это – формула общего члена геометрической прогрессии со знаменателем q¹0 и с начальным членом прогрессии b0.

Пример 3¢. Так называемая формула Бине jn=является частным решением соотношения jn=jn-2+jn-1 при j0=j1=1.

3. Линейные рекуррентные соотношения. Соотношение вида

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) имеет (единственное) решение.

Задача 1. Найти общий член геометрической прогрессии по формуле (4).

Решение. Характеристический многочлен рекуррентного соотношения bn=qbn-1 имеет вид . Поэтому .

Задача 2. Найти общее решение соотношения Фибоначчи an+2=an+an+1.

Решение. Характеристический многочлен рекуррентного соотношения an+2=an+an+1 имеет вид . Поэтому .

Приведем без доказательства следующее обобщение теоремы 1.

Теорема 2. Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет k корней: a1 кратности , …, ak кратности , , . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:

, (6)

где .

Задача 3. Найти общее решение соотношения .

Решение. Характеристический многочлен имеет корень 2 кратности 3. Поэтому .

Замечание. Общее решение неоднородного линейного соотношения (2) можно найти как сумму общего решения однородного линейного соотношения (3) и частного решения неоднородного линейного соотношения (2).