2.5  Возвратные последовательности, производящие функции,

рекуррентные соотношения

 

Последовательность  называется возвратной, если для некоторого k и при всех n выполняется соотношение вида

,                               (1)

где коэффициенты , не зависят от n. Многочлен

                                          (2)

называется характеристическим  для возвратной последовательности .

Теорема. 1. Если  – простые корни характеристического многочлена (2), то общее решение рекуррентного соотношения (1) имеет вид

.

2. Пусть  является корнем кратности  характеристического многочлена (2). Тогда общее решение рекуррентного соотношения (1) имеет вид

,

где  – произвольные константы.

С каждой последовательностью  можно связать ряд

,

называемый производящей функцией для последовательности . В тех случаях, когда ряд   сходится к некоторой функции , функцию  также называют производящей для последовательности . Экспоненциальной производящей функцией для последовательности  называется ряд

.

Можно определить операции сложения, умножения и умножения на константу для производящих функций, рассматривая их как формальные ряды.