Глава 3. Производящие функции

Пусть {a_k} – последовательность чисел, где k³0 пробегают неотрицательные целые значения. Производящей функцией a(x) последовательности {a_k} называется сумма ряда . Иногда сумма берется по всем натуральным k³1. Это происходит в случаях, когда число a₀ не определено.

Например, производящая функция для последовательности (где при k>n), будет равна .

Имеет место обобщение бинома Ньютона

.

Производящие функции применяются для решения рекуррентных уравнений, возникающих при анализе алгоритмов [2]. Для знакомства с решением рекуррентных уравнений рекомендуем небольшую книгу Маркушевича [8]. Для дальнейшего изучения – книги [10] и [12].