Производящие функции и рекуррентные соотношения

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

$Производящие функции и рекуррентные соотношения$

разложены в степенные ряды,

$Производящие функции и рекуррентные соотношения$

- два многочлена, причем

$Производящие функции и рекуррентные соотношения$

. Мы будем, кроме того, предполагать, что

$Производящие функции и рекуррентные соотношения$

, то есть, что алгебраическая дробь

$Производящие функции и рекуррентные соотношения$

правильна (в противном случае мы всегда можем выделить из нее целую часть). Мы знаем, что если

$Производящие функции и рекуррентные соотношения$

(10.10)

то

$Производящие функции и рекуррентные соотношения$

Раскроем в правой части этого равенства скобки и сравним коэффициенты при одинаковых степенях

$Производящие функции и рекуррентные соотношения$

слева и справа. Сначала мы получим

$Производящие функции и рекуррентные соотношения$

соотношений такого вида:

$Производящие функции и рекуррентные соотношения$

(10.11)

(если

$Производящие функции и рекуррентные соотношения$

, то мы считаем, что

$Производящие функции и рекуррентные соотношения$

). А дальше все соотношения имеют один и тот же вид:

$Производящие функции и рекуррентные соотношения$

(10.12)

(ведь в

$Производящие функции и рекуррентные соотношения$

нет членов, содержащих

$Производящие функции и рекуррентные соотношения$

и т.д.). Таким образом, коэффициенты

$Производящие функции и рекуррентные соотношения$

ряда (10.10) удовлетворяют рекуррентному соотношению (10.12). Коэффициенты этого соотношения зависят лишь от знаменателя дроби. Числитель же дроби нужен для нахождения первых членов

$Производящие функции и рекуррентные соотношения$

рекуррентной последовательности.

Обратно, если дано рекуррентное соотношение (10.12) и заданы члены

$Производящие функции и рекуррентные соотношения$

, то мы сначала по формулам (10.11) вычислим значения

$Производящие функции и рекуррентные соотношения$

. А тогда производящей функцией для последовательности чисел

$Производящие функции и рекуррентные соотношения$

является алгебраическая дробь

$Производящие функции и рекуррентные соотношения$

(10.13)

На первый взгляд кажется, что мы мало выиграли при замене рекуррентного соотношения производящей функции. Ведь все равно придется делить числитель на знаменатель, а это приведет к тому же самому рекуррентному соотношению (10.12). Но дело в том, что над дробью (10.13) можно выполнять некоторые алгебраические преобразования, а это облегчит отыскание чисел

$Производящие функции и рекуррентные соотношения$

Содержание раздела

Главная сайта