2.5
Возвратные последовательности,
производящие функции,
Последовательность
называется возвратной, если для некоторого k и при всех n выполняется соотношение вида
, (1)
где коэффициенты
, не зависят от n. Многочлен
(2)
называется характеристическим для возвратной последовательности
.
Теорема. 1. Если
– простые корни
характеристического многочлена (2), то общее решение рекуррентного соотношения
(1) имеет вид
.
2. Пусть
является корнем
кратности
характеристического
многочлена (2). Тогда общее решение рекуррентного соотношения (1) имеет вид
,
где
– произвольные
константы.
С каждой
последовательностью
можно связать ряд
,
называемый производящей функцией для последовательности
. В тех случаях,
когда ряд
сходится к некоторой
функции
, функцию
также называют производящей для
последовательности
. Экспоненциальной производящей функцией для
последовательности
называется ряд
.
Можно определить операции сложения,
умножения и умножения на константу для производящих функций, рассматривая их
как формальные ряды.