Производящие функции

Производящая функция — это бесконечный ряд

коэффициенты которого порождают (производят, генерируют) последовательность чисел a₀, a₁, a₂, … Тот факт, что коэффициент a_nявляется множителем при zⁿ обозначают следующим образом:

Замечательная особенность производящих функций заключается в том, что они часто могут быть записаны в компактном виде. Например, если a₀=a₁=…=1, то

Другой пример: если a_n=n, то

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

Рассмотрим абстрактный пример. Пусть в некоторой задаче удалось отыскать закономерность

То есть обнаружилась последовательность 1, 7, 19, 43, 91, 187,…, удовлетворяющая рекуррентному соотношению. Требуется вывести общую формулу для a_n, n≥0. В этом случае говорят «решить рекуррентное уравнение» или «решить рекуррентное соотношение».

Сначала будем искать производящую функцию в виде

Домножим левую и правую части рекуррентного соотношения на z в соответствующей степени:

Сложим все уравнения для всех значений n:

Слева в точности получается значение G(z), а справа — некоторое выражение, которое нужно свернуть (любым законным способом). Сначала рассмотрим первую сумму

Первое равенство получается, если изменить индекс суммирования (уменьшить на 1) и вынести 2 за знак суммы. Второе равенство получается путём вынесения z за знак суммы. Третье очевидно. Вторая сумма сворачивается почти аналогично:

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

Окончательно, подставив упрощённые выражения в полученное выше уравнение (*), имеем

Это называется уравнение для производящей функции. Разрешив его относительно G(z), получим

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

Это означает, что

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