Пусть последовательность <tex>(a_0, a_1, a_2, ...)</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \ge 0</tex>) в замкнутом виде. Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:
1)Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен k, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером n, равно k):
<tex>a_0=# #: текст и формулы#: текст и формулы# выведется «2.».блаблабла#: бла# выведется «3.»# Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен k,</tex>то есть количество предшествующих элементов, требуемых для вычисления элемента с номером n, равно k):
#: <tex>a_1a_0=...,</tex>
#: <tex>a_{k-1}a_1=...,</tex>
#: <tex>a_{nk-1}=..., n \ge k.</tex>
2)Домножить каждую строчку на z в соответствующей степени и просуммировать строчки для всех n #: <tex> a_{n}=..., n \ge 0 k.</tex>.
3)В полученном уравнении привести все суммы # Домножить каждую строчку на z в соответствующей степени и просуммировать строчки для всех n <tex>\sumge 0 </tex> к замкнутому виду. Получить уравнение для производящей функции.
4)# В полученном уравнении привести все суммы <tex>\sum</tex> к замкнутому виду. Получить уравнение для производящей функции. # Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.
Для демонстрации универсальности метода рассмотрим довольно произвольное рекуррентное соотношение:
