3.    ПРОИЗВОДЯЩИЕ ФУНКЦИИ

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

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

.

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

.

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