Решение рекуррентных соотношений методом производящих функций

Определение числа расстановок скобок в выражении с неассоциативной бинарной операцией. Ранее для числа расстановки скобок в неассоциативном произведении была получена формула

(10)

Введем для последовательности производящую функцию: .

Заменим коэффициенты их выражениями из рекуррентного соотношения (10). Так как это соотношение имеет место, начиная с , то первый член отделим от суммы:

.

Последовательность представляет собой свертку последовательности с собой. В силу свойства 5) имеем

. (12)

Таким образом, можно найти как решение квадратного уравнения (12):

(13)

Перед корнем выбран знак минус, так как . Чтобы найти , надо разложить в ряд по степеням правую часть уравнения (13). Для этого используем формулу бинома Ньютона (8) при и :

,

где

.

Умножим числитель и знаменатель последней дроби на произведение последовательных четных чисел от 2 до : .

Тогда

.

Из формулы (13) получим

.

Таким образом, число расстановок скобок в неассоциативном произведении равно

.

Решение линейных рекуррентных соотношений с постоянными коэффициентами. Пусть последовательность является решением линейного рекуррентного соотношения

, (14)

Для производящей функции (1) этой последовательности обозначим начальные отрезки ряда

Заменим коэффициенты, начиная с -го, по формуле (14)

. (15)

Внутреннюю сумму представим в виде

и подставим в (15):

.

Из этого уравнения найдем производящую функцию :

, (16)

где , .

Сравнивая с характеристическим многочленом

,

найдем

.

Если имеет корни , , …, кратности соответственно , , …, , то

.

Тогда

.

Раскладывая дробь (16) на простые, получим

, (17)

где – константы.

Используя степенные ряды (3) для простых дробей, получим

. (18)

Подставляя (18) в (17) и определяя коэффициент при , можно убедиться, что представляется линейной комбинацией функций

(19)

Другими словами, функции (19) образуют базис в пространстве решений рекуррентного соотношения (14). Ранее без доказательства было сформулировано, что решениями этого соотношения являются линейные комбинации функций

(20)

Можно показать, что функции (19) линейно выражаются через функции (20). Например, при

.

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