Общим решением рекуррентного соотношения (1) называется множество всех последовательностей, удовлетворяющих этому соотношению.
Частным решением соотношения (1) называется одна из последовательностей, удовлетворяющих этому соотношению.
Пример 1¢. Последовательность an = a 0+ nd является общим решением соотношения an = an -1+ d. Это – формула общего члена арифметической прогрессии с разностью d и с начальным членом прогрессии a 0.
Пример 2¢. Последовательность bn = b 0× qn является общим решением соотношения bn = bn -1 ×q. Это – формула общего члена геометрической прогрессии со знаменателем q ¹0 и с начальным членом прогрессии b 0.
Пример 3¢. Так называемая формула Бине j n =является частным решением соотношения j n =j n -2+j n -1 при j0=j1=1.
3. Линейные рекуррентные соотношения. Соотношение вида
an + k + p 1 an + k -1+…+ pkan = h (n) (2)
где h (n) – функция от числа , а , называется линейным рекуррентным соотношением.
Линейное рекуррентное соотношение называют однородным, если f (n)=0:
an + k + p 1 an + k -1+…+ pkan =0. (3)
|
|
Многочлен xk + p 1 xk -1+…+ pk -1 x + pk называется характеристическим для соотношения (2).
Корень a многочлена называется простым, если делится на , но не делится на .
Корень a многочлена называется кратным, если делится на , но не делится на , .
При этом число называется кратностью корня .
Основная теорема алгебры: многочлен степени с комплексными коэффициентами имеет комплексных корней с учетом их кратности.
Теорема 1. Пусть характеристический многочлен однородного линейного рекуррентного соотношения (3) имеет n простых корней a1, …, a n. Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:
, (4)
где c 1,…, 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) мы получим систему линейных уравнений относительно c 1,…, ck:
(5)
Определитель системы (5) есть известный в алгебре определитель Вандермонда:
.
Так как простые корни x 1,…, 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 кратности , …, a k кратности , , . Тогда общее решение рекуррентного соотношения (3) имеет следующий вид:
, (6)
где .
Задача 3. Найти общее решение соотношения .
Решение. Характеристический многочлен имеет корень 2 кратности 3. Поэтому .
Замечание. Общее решение неоднородного линейного соотношения (2) можно найти как сумму общего решения однородного линейного соотношения (3) и частного решения неоднородного линейного соотношения (2).
4. Производящие функции. Формальный ряд a 0+ a 1 x + a 2 x 2+…+ akxk +… называется производящей функцией последовательности a 0, a 1, a 2,…, ak,…
Производящая функция является или сходящимся рядом, или расходящимся рядом. Два расходящихся ряда могут быть равны как функции, но быть производящимися функциями различных последовательностей. Например, ряды 1+2 x +22 x 2+…+2 kxk +… и 1+3 x +32 x 2+…+3 kxk +… определяют одну и ту же функцию (равную 1 в точке x =1, неопределенную в точках x >1), но являются производящими функциями различных последовательностей.
Свойства производящих функций последовательностей:
сумма (разность) производящих функций последовательностей an и bn равна производящей функции сумме (разности) последовательностей an + bn;
произведение производящих функций последовательностей an и bn является производящей функцией свёртки последовательностей an и bn:
cn = a 0 bn + a 1 bn -1+…+ an -1 b 1+ anb 0.
Пример 1. Функция является производящей для последовательности
Пример 2. Функция является производящей для последовательности 1, 1, 1, …