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

Каждый раз, когда необходимо получить информацию о последовательности чисел {а„) = 00,01,02,..., можно рассмотреть бесконечную сумму от "параметра" z

= 00 + 01+022+ ••• = Еа„г". (1)

п>0

А теперь можно заняться исследованием свойств функции G. Данная функция характерна тем, что с ее помощью можно представить всю последовательность. Это очень важно, особенно если последовательность (о„) была определена методом индукции (т. е. если о„ определяется через oo,oi,... ,o„ i). Более того, с помощью методов дифференциального исчисления по функции Giz) можно восстановить все члены последовательности оо, oi, ... (при условии, что бесконечный ряд (1) сходится для некоторого ненулевого z).

G{z) называется производящей функцией для последовательности oo,ai,02, - Использование производящих функций открывает новые горизонты методов и приемов и существенно расширяет наши возможности при решении задач. Как уже упоминалось в предыдущем разделе, А. де Муавр ввел производящие функции, чтобы решить линейные рекуррентные соотношения в общем виде. Джеймс Стирлинг применил теорию де Муавра для решения более сложных рекуррентных соотношений и показал, как применять для этого не только арифметические операции, но также дифференцирование и интегрирование [Methodus Differentialis (London, 1730), Proposition 15]. Через несколько лет Л. Эйлер нашел новые способы использования производящих функций, например, при исследовании разбиений [Commentarii Acad. Sci. Pet. 13 (1741), 64-93; Novi Comment. Acad. Sci. Pet. 3 (1750), 125-169]. Дальнейшее развитие эти методы получили в классическом труде Пьера С. Лапласа (Pierre S. Laplace) Theorie Analytique des Probabilites (Paris, 1812).

Очень важен вопрос о сходимости бесконечного ряда (1). В любом учебнике по теории бесконечных рядов доказываются следующие утверждения.

a) Если ряд (1) сходится для некоторого z = zq, то он сходится для всех z, таких, что \z\ < \zo\.

b) Этот ряд сходится для некоторого z ф О тогда и только тогда, когда последовательность (\/ап) ограничена. (Если это условие не выполняется, то .можно получить сходящийся ряд для последовательности (a„/n!) или другой последовательности, связанной с исходной.)

С другой стороны, во время работы с производящими функциями не всегда стоит беспокоиться о сходимости приведенного ряда, так как часто мы только исследуем возможные подходы к решению конкретной задачи. Найдя решение некоторым способом, каким бы нестрогим оно ни было, мы сможем обосновать его независимым образом. Например, в предыдущем разделе для вывода формулы (14) мы воспользовались производящей функцией. После того как данное равенство получено, уже не составляет труда доказать его по индукции и можно даже не упоминать, что оно было найдено с помощью производящей функции. Более того, можно показать, что большинство операций (если не все), вьшолняемых над производящими функциями, можно строго обосновать, не затрагивая вопроса о сходимости ряда. Например, см. работу Е. Т. Bell, Trans. Amer. Math. Soc. 25 (1923), 135-154; Ivan Niven, AMM

76 (1969), 871-889; Peter Henrici, Applied and Computational Complex Analysis 1 (Wiley, 1974), Chapter 1.

A теперь давайте рассмотрим основные методы работы с производящими функциями.

A. Сложение. Если G[z) -производящая функция для (а„) = ао, oi,... и H{z) - производящая функция для (6„) = bo,bi,..., то aG{z) + PH{z)-производящая функция для (аа„ --6„) = аоо + 0Ьо, aai + /3bi,

aanz" + j3bnZ = J2{aan+j3bn)z. (2j

n>0 n>0 n>0

B. Сдвиг. Если Giz) -производящая функция для (а„) = ао,fli,..., то z"G{z) - производящая функи,ия для (а„ т) = О,..., О, ао, ai,...:

z"" anz" = J2 an-mz". (3]

n>0 n>m

Ё сумме справа суммирование можно распространить на все п > О, если считать, что а„ = О для любого отрицательного п.

Аналогично {G{z) - ао - - - am-iz"~)/z" - производящая функция для (ап+т) = ат,ат+1,

z-anz = ап+тг". (4)

n>m п>0

В предыдущем разделе для решения задачи Фибоначчи мы комбинировали операции АиВ: G(z) была производящей функцией для (F„), zG{z)-для (F„ i), zG{z) -для (F„ 2), а (1 - z - z)Giz)-для (F„-F„ i -F„ 2)- Затем, так как разность Fn - Fn-i - Fn-2 равна нулю при п >2, мы выяснили, что (1 - z - z)G{z) - это многочлен. Аналогично производящая функция для любой линейной рекуррентной последовательности (т. е. такой последовательности, для которой а„ = cia„ i Н-----h c„,a„ m) является многочленом, деленным на (1 - Ciz - • • • - сг"*).

Давайте рассмотрим простейший пример. Если G{z)-производящая функция для постоянной последовательности 1,1,1,..., то zG{z) порождает последовательность 0,1,1,..., поэтому (1 - z)G{z) = 1. В результате получаем простую, но очень важную формулу:

= 1 + Z + 2 + • • . (5)

I - z

C. Умножение. Если G{z) - производящая функция для ao,ai,... и H{z) - производящая функция для bo,bi,..., то

G{z)H{z) = (ао + aiz -\- a2Z? + ){bo + biz -\- b2Z + )

= (aobo) -Ь (ao6i -I- aibo)z -\- {aob2 -I- aibi -f a2bo)z -I----.

Следовательно, G{z)H{z)-производящая функция для последовательности cq, Cl,.-., где

Cn = Yakbn-k- (6)

Соотношение (3) являетсж частным случаем (6). Другой важный частный случай имеет место, когда все 6„ равны единице:

--G{z) = Оо + (ао + ai)z + (oq + oi + аг) + • • •. (7)

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

Из соотношения (6) следует правило для проговедения трех функций; F{z)G{z)H{z) порождает последовательность do, di, 2,..., где

dn= XI iik- (8)

i,j,k>0 i+j+k=n

Общее правило для произведения любого числа функций (в тех случаях, когда это имеет смысл) выглядит следующим образом:

j>0 Jfe>0 n>0 feo,*i,-..>0

ko+ki+---=n

Когда в рекуррентном соотношении для некоторой последовательности содержатся биномиальные коэффициенты, часто возникает необходимость в получении производящей функции для последовательности co,ci,..., которая определяется формулой

в этом случае, как правило, лучше воспользоваться производящими функциями последовательностей (а„/п!), (6„/п!), (сп/п!), поскольку

где с„ определяется формулой (10).

D. Замена переменной z. Очевидно, что G{cz) - производящая функция для последовательности ao,cai,ca2, В частности, производящей функцией для последовательности 1, с, с, с,... является 1/(1 - cz).

Воспользуемся известным приемом для извлечения членов ряда через один:

i(G(z)+G(-z)) =ао + 022 + 042* +

\{G{z) - G{-z)) = aiz + azz + agz + •••

Извлекая комплексные корни из единицы, можно развивать эту идею и выбирать каждый т-й член. Пусть ш = 1 = cos(27r/m) -I- г sin(27r/m). Тогда

X a„z" = - X w-*G(w=2), О < г < m. (13)

п mod m=r 0<A;<m

(См. упр. 14.) Например, если т = 3иг=1, тоа; = --- -г (комплексный кубический корень из единицы). Отсюда следует, что

aiz-1-04 + 072= \ {G{z)-\-uj-G{y)z)-\-u>-G{uPz)).