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

Метод производящих функций позволяет получить выражение для чисел, удовлетворяющих рекуррентному соотношению. neerc.ifmo.ru Алгоритм решения состоит из четырёх шагов: neerc.ifmo.ru

1. Записать рекуррентное соотношение и начальные данные для него. neerc.ifmo.ru www.matburo.ru Если порядок соотношения равен k, то нужно записать уравнения для чисел a0, a1, ak-1 и так далее, а также для числа an, где n ≥ k. neerc.ifmo.ru www.matburo.ru
2. Домножить каждую строчку на z в соответствующей степени и сложить все выражения. neerc.ifmo.ru www.matburo.ru В левой части получится сумма, которая и будет производящей функцией, назовём её G(z). neerc.ifmo.ru www.matburo.ru
3. Преобразовать правую часть так, чтобы она превратилась в выражение, включающее G(z). neerc.ifmo.ru www.matburo.ru
4. Решить полученное уравнение, получив для G(z) выражение в замкнутом виде. neerc.ifmo.ru
5. Разложить G(z) в степенной ряд, коэффициент при zn будет искомым выражением для an. neerc.ifmo.ru www.matburo.ru

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