Арифметические действия с формальными степенными рядами

Суммой двух производящих функций [math]A(s) = a_0 + a_1 s + a_2 s^2 + \dots[/math] и [math]B(s) = b_0 + b_1 s + b_2 s^2 + \dots[/math] называется производящая функция [math]A(s) + B(s) = (a_0 + b_0) + (a_1 + b_1) s + (a_2 + b2) s^2 + \dots[/math].

Произведением производящих функций [math]A[/math] и [math]B[/math] называется производящая функция [math]A(s)B(s) = a_0 b_0 + (a_0 b_1 + a_1 b_0) s + (a_0 b_2 + a_1 b_1 + a_2 b_0) s^2 + \dots[/math].

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

Пусть [math]A(s) = a_0 + a_1 s + a_2 s^2 + \dots[/math] и [math]B(s) = b_0 + b_1 s + b_2 s^2 + \dots[/math] — две производящие функции, причем [math]B(0) = b_0 = 0[/math]. Подстановкой производящей функции [math]B[/math] в производящую функцию [math]A[/math] называется производящая функция [math]A(B(t)) = a_0 + a_1 b_1 t + (a_1 b_2 + a_2 b_1^2) t^2 + (a_1 b_3 + 2 a_2 b_1 b_2 + a_3 b_1^3) t^3 + \dots[/math].

Если, например, [math]B(t) = -t[/math], то [math]A(B(t)) = A(-t) = a_0 -a_1 t + a_2 t^2 - a_3 t^3 + \dots[/math].

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

Теорема (об обратной функции):

Пусть функция [math]B(t) = b_1 t + b_2 t^2 + b_3 t^3 + \dots[/math] такова, что [math]B(0) = b_0 = 0[/math], а [math]b_1 \ne 0[/math]. Тогда существуют такие функции [math] A(s) = a_1 s + a_2 s^2 + a_3 s^3 + \dots[/math], [math]A(0) = 0[/math] и [math]C(u) = c_1 u + c_2 u^2 + c_3 u^3 + \dots[/math], [math]C(0) = 0[/math], что [math]A(B(t)) = t[/math] и [math]B(C(u)) = u[/math]. При этом, функции [math]A[/math] и [math]C[/math] единственны. Функция [math]A[/math] называется левой обратной, а функция [math]C[/math] — правой обратной к функции [math]B[/math].

Доказательство:

[math]\triangleright[/math]

Докажем существование и единственность левой обратной функции. Доказательство для правой обратной аналогично. Будем определять кожффициенты функции [math]A[/math] последовательно. Коэффициент [math]a_1[/math] определяется из условия [math]a_1 b_1 = 1[/math], откуда [math]a_1 = \dfrac{1}{b_1}[/math]. Предположим теперь, что коэффициенты [math]a_1, a_2, \dots, a_n[/math] уже определены. Коэффициент [math]a_{n+1}[/math] определяется из условия [math]a_{n+1} b_1^{n+1} + \dots = 0[/math], где точками обозначен неокторый многочлен от [math]a_1, \dots, a_n[/math] и [math]b_1, \dots, b_n[/math]. Тем самым, условие представляет собой линейное уравнение на [math]a_{n+1}[/math], причем коэффициент [math]b_1^{n+1}[/math] при [math]a_{n+1}[/math] отличен от нуля. Такое уравнение имеет единственное решение, и теорема доказана.

[math]\triangleleft[/math]

Лемма (деление формальных степенных рядов):

Пусть [math]A(s) = a_0 + a_1 s + a_2 s^2 + a_3 s^3 + \dots [/math] — формальный степенной ряд, причем [math]A(0) \ne 0[/math]. Тогда существует единственный формальный степенной ряд [math]B(s) = b_0 + b_1 s + b_2 s^2 + b_3 s^3 + \dots [/math], такой что [math]A(s)B(s) = 1[/math].

Доказательство:

[math]\triangleright[/math]

Снова проведем доказательство по индукции. [math]b_0 = \dfrac{1}{a_0}[/math]. Пусть теперь все коэффициенты ряда [math]B[/math] вплоть до степени [math]n - 1[/math] однозначно определены. Коэффициент при [math]s^n[/math] определяется из условия [math]a_0 b_n + a_1 b_{n - 1} + \dots + a_n b_0 = 0[/math]. Это линейное уравнение на [math]b_n[/math], причем коэффициент [math]a_0[/math] при [math]b_n[/math] отличен от нуля. Поэтому уравнение имеет единсвтенное решение.

[math]\triangleleft[/math]