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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 24 промежуточные версии 6 участников)
Строка 1: Строка 1:
 
==Простейшие операции==
 
==Простейшие операции==
 
Рассмотрим два [[Производящая функция|формальных степенных ряда]] <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex>.
 
Рассмотрим два [[Производящая функция|формальных степенных ряда]] <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex>.
 
+
{{Определение
''Суммой'' <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(s) + B(s) = (a_0 + b_0) + (a_1 + b_1) s + (a_2 + b_2) s^2 + \dots</tex>.
+
|definition = '''Суммой''' (англ. ''addition'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется ряд <tex>A(s) + B(s) = (a_0 + b_0) + (a_1 + b_1) s + (a_2 + b_2) s^2 + \dots</tex>.
 
+
}}
''Произведением'' <tex>A</tex> и <tex>B</tex> называется ряд <tex>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</tex>.
+
{{Определение
 
+
|id=def_mul
 +
|definition = '''Произведением''' (англ. ''multiplication'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется ряд <tex>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</tex>.
 +
}}
 
Операции сложения и умножения формальных степенных рядов коммутативны и ассоциативны.
 
Операции сложения и умножения формальных степенных рядов коммутативны и ассоциативны.
  
 
==Деление==
 
==Деление==
 +
{{Определение
 +
|id = div
 +
|definition=
 +
'''Обратным по умножению''' (англ. ''multiplicative inverse'') к формальному степенному ряду <tex>A(s)</tex> называется такой ряд <tex>B(s)</tex>, что <tex>A(s)B(s) = 1</tex>. Обозначение: <tex>B(s) = A^{-1}(s)</tex>.
 +
}}
 +
 
{{Лемма
 
{{Лемма
|about = деление формальных степенных рядов
+
|statement = Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + a_3 s^3 + \dots </tex> {{---}} формальный степенной ряд, причем <tex>A(0) \ne 0</tex>. Тогда существует единственный обратный по умножению к <tex>A(s)</tex> ряд <tex>B(s) = b_0 + b_1 s + b_2 s^2 + b_3 s^3 + \dots </tex>.
|statement = Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + a_3 s^3 + \dots </tex> {{---}} формальный степенной ряд, причем <tex>A(0) \ne 0</tex>. Тогда существует единственный формальный степенной ряд <tex>B(s) = b_0 + b_1 s + b_2 s^2 + b_3 s^3 + \dots </tex>, такой что <tex>A(s)B(s) = 1</tex>, то есть <tex>B(s) = A^{-1}(s)</tex>.
 
 
|proof =  
 
|proof =  
:Проведем доказательство по индукции. Нам известно, что <tex>b_0 = \dfrac{1}{a_0}</tex>. Пусть теперь все коэффициенты ряда <tex>B</tex> вплоть до степени <tex>n - 1</tex> однозначно определены. Коэффициент при <tex>s^n</tex> определяется из условия <tex>a_0 b_n + a_1 b_{n - 1} + \dots + a_n b_0 = 0</tex>. Это линейное уравнение на <tex>b_n</tex>, причем коэффициент <tex>a_0</tex> при <tex>b_n</tex> отличен от нуля. Такое уравнение имеет единственное решение.
+
:Распишем <tex>A(s)B(s)</tex> по формуле произведения рядов: <tex>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</tex>. Заметим, что условие <tex>A(s)B(s) = 1</tex> выполнено только в том случае, если <tex>a_0 b_0 = 1</tex>, а все остальные слагаемые полученного ряда равны нулю.
 +
:Докажем по индукции, что такой ряд <tex>B</tex> единственен. Нам известно, что <tex>b_0 = \dfrac{1}{a_0}</tex>. Пусть теперь все коэффициенты ряда <tex>B</tex> вплоть до степени <tex>n - 1</tex> однозначно определены. Коэффициент при <tex>s^n</tex> определяется из условия <tex>a_0 b_n + a_1 b_{n - 1} + \dots + a_n b_0 = 0</tex>. Это линейное уравнение на <tex>b_n</tex>, причем коэффициент <tex>a_0</tex> при <tex>b_n</tex> отличен от нуля. Такое уравнение имеет единственное решение.
 +
}}
 +
 
 +
{{Определение
 +
|definition=
 +
'''Делением''' (англ. ''division'') формальных степенных рядов <tex>A(s)</tex> и <tex>B(s)</tex> называется операция <tex>\dfrac{A(s)}{B(s)} = A(s) B(s)^{-1}</tex> (при условии существования у <tex>B(s)</tex> обратного).
 
}}
 
}}
 +
 +
===Примеры===
 +
#Допустим, надо построить обратный ряд для <tex>A(s) = 1 + s</tex>. Воспользуемся леммой:
 +
#:<tex>b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1</tex>
 +
#:<tex>a_0 b_1 + a_1 b_0 = 0 \Rightarrow b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{1 \cdot 1}{1} = -1</tex>
 +
#:<tex>a_0 b_2 + a_1 b_1 + a_2 b_0 = 0 \Rightarrow b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{1 \cdot (-1) + 0}{1} = 1</tex>
 +
#:<tex>\dots</tex>
 +
#:<tex>b_n = - \dfrac{a_1 b_{n - 1}}{a_0} = -b_{n - 1}</tex>
 +
#:<tex>B(s) = 1 - s + s^2 - s^3 + \dots</tex>
 +
#Пусть теперь надо построить обратный ряд для <tex>A(s) = 1 - s - s^2</tex>:
 +
#:<tex>b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1</tex>
 +
#:<tex>b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{(-1) \cdot 1}{1} = 1</tex>
 +
#:<tex>b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{(-1) \cdot 1 + (-1) \cdot 1}{1} = 2</tex>
 +
#:<tex>b_3 = - \dfrac{a_1 b_2 + a_2 b_1}{a_0} = - \dfrac{(-1) \cdot 2 + (-1) \cdot 1}{1} = 3</tex>
 +
#:<tex>\dots</tex>
 +
#:<tex>b_n = - \dfrac{a_1 b_{n - 1} + a_2 b_{n - 2}}{a_0} = b_{n - 1} + b_{n - 2}</tex>
 +
#:<tex>B(s) = 1 + s + 2 s^2 + 3 s^3 + \dots</tex>
  
 
==Композиция==
 
==Композиция==
 
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex> {{---}} два формальных степенных ряда, причем <tex>B(0) = b_0 = 0</tex>.
 
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> и <tex>B(s) = b_0 + b_1 s + b_2 s^2 + \dots</tex> {{---}} два формальных степенных ряда, причем <tex>B(0) = b_0 = 0</tex>.
  
''Композицией (подстановкой)'' рядов <tex>A</tex> и <tex>B</tex> называется формальный степенной ряд <tex>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</tex>.
+
{{Определение
 
+
|id=def_in
 +
|definition =
 +
'''Композицией (подстановкой)''' (англ. ''composition'') формальных степенных рядов <tex>A</tex> и <tex>B</tex> называется ряд <tex>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</tex>.
 +
}}
 
Если, например, <tex>B(t) = -t</tex>, то <tex>A(B(t)) = A(-t) = a_0 -a_1 t + a_2 t^2 - a_3 t^3 + \dots</tex>.
 
Если, например, <tex>B(t) = -t</tex>, то <tex>A(B(t)) = A(-t) = a_0 -a_1 t + a_2 t^2 - a_3 t^3 + \dots</tex>.
  
Операция подстановки в случае, когда <tex>B(0) \ne 0</tex>, не определена. (При попытке подставить такой ряд возникает необходимость суммирования бесконечных числовых рядов).
+
Операция подстановки в случае, когда <tex>B(0) \ne 0</tex>, не определена. (При попытке подставить такой ряд для вычисления коэффициентов результата возникает необходимость суммирования бесконечных числовых рядов).
  
==Обратная==
+
==Обратный ряд==
{{Теорема
 
|about = об обратном формальном степенном ряде
 
|statement = Пусть ряд <tex>B(t) = b_0 + b_1 t + b_2 t^2 + b_3 t^3 + \dots</tex> таков, что <tex>B(0) = b_0 = 0</tex>, а <tex>b_1 \ne 0</tex>. Тогда существуют такие ряды <tex> A(s) = a_1 s + a_2 s^2 + a_3 s^3 + \dots</tex>, <tex>A(0) = 0</tex> и <tex>C(u) = c_1 u + c_2 u^2 + c_3 u^3 + \dots</tex>, <tex>C(0) = 0</tex>, что <tex>A(B(t)) = t</tex> и <tex>B(C(u)) = u</tex>. При этом, ряды <tex>A</tex> и <tex>C</tex> единственны.
 
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Производящие функции, соответствующие рядам <tex>A</tex> и <tex>C</tex>, называется соответственно '''левой''' и '''правой обратной''' к производящей функции, соответствующей ряду <tex>B</tex>.
+
'''Левым обратным''' (англ. ''left inverse'') по операции подстановки формальным степенным рядом для ряда <tex>B(t)</tex> называется такой ряд <tex>A(s)</tex>, что <tex>A(B(t)) = t</tex>. Аналогично, '''правым обратным''' (англ. ''right inverse'') формальным степенным рядом для <tex>B(t)</tex> называется такой <tex>C(u)</tex>, что <tex>B(C(u)) = u</tex>.
 
}}
 
}}
 +
 +
{{Теорема
 +
|about = об обратном формальном степенном ряде
 +
|statement = Пусть ряд <tex>B(t) = b_0 + b_1 t + b_2 t^2 + b_3 t^3 + \dots</tex> таков, что <tex>B(0) = b_0 = 0</tex>, а <tex>b_1 \ne 0</tex>. Тогда существуют такие ряды <tex> A(s) = a_1 s + a_2 s^2 + a_3 s^3 + \dots</tex>, <tex>A(0) = 0</tex> и <tex>C(u) = c_1 u + c_2 u^2 + c_3 u^3 + \dots</tex>, <tex>C(0) = 0</tex>, что <tex>A(t)</tex> является левым обратным, а <tex>C(u)</tex> {{---}} правым обратным для <tex>B(s)</tex>. При этом, ряды <tex>A</tex> и <tex>C</tex> единственны.
 
|proof =
 
|proof =
:Докажем существование и единственность левой обратной функции. Доказательство для правой обратной аналогично.  
+
:Докажем по индукции существование и единственность левого обратного ряда. Доказательство для правого аналогично.  
:Будем определять коэффициенты ряда <tex>A</tex> последовательно. Коэффициент <tex>a_1</tex> определяется из условия <tex>a_1 b_1 = 1</tex>, откуда <tex>a_1 = \dfrac{1}{b_1}</tex>.  
+
:Будем определять коэффициенты ряда <tex>A</tex> последовательно. Поскольку <tex>A(B(t)) = t</tex>, <tex>a_1 b_1 = 1</tex>, откуда <tex>a_1 = \dfrac{1}{b_1}</tex>. Все остальные коэффициенты результирующего ряда при этом равны нулю.
:Предположим теперь, что коэффициенты <tex>a_1, a_2, \dots, a_n</tex> уже определены. Коэффициент <tex>a_{n+1}</tex> определяется из условия <tex>a_{n+1} b_1^{n+1} + \dots = 0</tex>, где точками обозначен неокторый многочлен от <tex>a_1, \dots, a_n</tex> и <tex>b_1, \dots, b_n</tex>. Тем самым, условие представляет собой линейное уравнение на <tex>a_{n+1}</tex>, причем коэффициент <tex>b_1^{n+1}</tex> при <tex>a_{n+1}</tex> отличен от нуля. Такое уравнение имеет единственное решение, и теорема доказана.
+
:Предположим теперь, что коэффициенты <tex>a_1, a_2, \dots, a_n</tex> уже определены. Коэффициент <tex>a_{n+1}</tex> определяется из условия <tex>a_{n+1} b_1^{n+1} + \dots = 0</tex>, где точками обозначен некоторый многочлен от <tex>a_1, \dots, a_n</tex> и <tex>b_1, \dots, b_n</tex>. Тем самым, условие представляет собой линейное уравнение на <tex>a_{n+1}</tex>, причем коэффициент <tex>b_1^{n+1}</tex> при <tex>a_{n+1}</tex> отличен от нуля. Такое уравнение имеет единственное решение, и теорема доказана.
 
}}
 
}}
 +
===Пример===
 +
Найдем левый обратный ряд для <tex>B(t) = t + t^2</tex>:
 +
:<tex>a_0 = 0</tex>
 +
:<tex>a_1 = \dfrac{1}{b_1} = 1</tex>
 +
:<tex>a_1 b_2 + a_2 b_1^2 = 0 \Rightarrow a_2 = - \dfrac{a_1 b_2}{b_1^2} = - \dfrac{1 \cdot 1}{1^2} = -1</tex>
 +
:<tex>a_1 b_3 + 2 a_2 b_1 b_2 + a_3 b_1^3 = 0 \Rightarrow a_3 = - \dfrac{a_1 b_3 + 2 a_2 b_1 b_2}{b_1^3} = - \dfrac{1 \cdot 0 + 2 \cdot (-1) \cdot 1}{1^3} = 2</tex>
 +
:<tex>\dots</tex>
 +
:<tex>A(s) = s - s^2 + 2 s^3 + \dots</tex>
 +
 +
==Сдвиги==
 +
===Сдвиг вправо===
 +
Сдвиг ряда вправо на <tex>k</tex> получается домножением его на <tex>s^k</tex>. Например, пусть исходный ряд <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex>. Сдвинем его на <tex>k</tex> вправо: <tex>B(s) = s^k \cdot A(s) = a_0 s^k + a_1 s^{k + 1} + a_2 s^{k + 2} + \dots = 0 + 0 s + 0 s^2 + \dots + a_0 s^k + a_1 s^{k + 1} + \dots</tex>.
 +
 +
===Сдвиг влево===
 +
Сдвинуть ряд влево на <tex>k</tex> можно, вычтя из него первые <tex>k</tex> слагаемых и затем разделив его на <tex>s^k</tex>. Например, сдвинем ряд <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> на <tex>k</tex> влево: <tex>B(s) = \dfrac{A(s) - (a_0 + a_1 s + a_2 s^2 + \dots + a_{k - 1} s^{k - 1})}{s^k} = a_k + a_{k + 1} s + a_{k + 2} s^2 + \dots</tex>.
 +
 +
 +
Сдвиги могут быть полезны для упрощения вычисления производящих функций.
 +
Например, попробуем получить функцию для чисел Фибоначчи, используя сдвиги. Пусть формальный степенной ряд для нее равен <tex>F(s) = f_0 + f_1 s + f_2 s^2 + \dots</tex>, при этом <tex>f_0 = f_1 = 1</tex>, <tex>f_n = f_{n - 2} + f_{n - 1}, n > 1</tex>. Рассмотрим сумму этого ряда и ряда, полученного из него сдвигом на <tex>1</tex> вправо: <tex>F(s) + s \cdot F(s) = (f_0 + f_1 s + f_2 s^2 + f_3 s^3 + \dots) + (0 + f_0 s + f_1 s^2 + f_2 s^3 + \dots) = (f_0 + 0) + (f_1 + f_0) s + (f_2 + f_1) s^2 + (f_3 + f_2) s^3 + \dots = f_1 + f_2 s + f_3 s^2 + f_4 s^3 + \dots</tex>. Заметим, что результат равен сдвигу <tex>F(s)</tex> на <tex>1</tex> влево. Составим и решим уравнение: <tex>F(s) + s \cdot F(s) = \dfrac{F(s) - 1}{s}</tex>; <tex>F(s)(s^2 + s - 1) = -1</tex>; <tex>F(s) = \dfrac{1}{1 - s - s^2}</tex>.
  
 
==См. также==
 
==См. также==
 +
* [[Производящая функция]]
 +
* [[Производящие функции нескольких переменных]]
 +
* [[Разложение рациональной функции в ряд]]
  
 
==Источники информации==
 
==Источники информации==

Текущая версия на 19:19, 4 сентября 2022

Простейшие операции

Рассмотрим два формальных степенных ряда [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].

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


Определение:
Произведением (англ. multiplication) формальных степенных рядов [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].

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

Деление

Определение:
Обратным по умножению (англ. multiplicative inverse) к формальному степенному ряду [math]A(s)[/math] называется такой ряд [math]B(s)[/math], что [math]A(s)B(s) = 1[/math]. Обозначение: [math]B(s) = A^{-1}(s)[/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]A(s)[/math] ряд [math]B(s) = b_0 + b_1 s + b_2 s^2 + b_3 s^3 + \dots [/math].
Доказательство:
[math]\triangleright[/math]
Распишем [math]A(s)B(s)[/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)B(s) = 1[/math] выполнено только в том случае, если [math]a_0 b_0 = 1[/math], а все остальные слагаемые полученного ряда равны нулю.
Докажем по индукции, что такой ряд [math]B[/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]


Определение:
Делением (англ. division) формальных степенных рядов [math]A(s)[/math] и [math]B(s)[/math] называется операция [math]\dfrac{A(s)}{B(s)} = A(s) B(s)^{-1}[/math] (при условии существования у [math]B(s)[/math] обратного).


Примеры

  1. Допустим, надо построить обратный ряд для [math]A(s) = 1 + s[/math]. Воспользуемся леммой:
    [math]b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1[/math]
    [math]a_0 b_1 + a_1 b_0 = 0 \Rightarrow b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{1 \cdot 1}{1} = -1[/math]
    [math]a_0 b_2 + a_1 b_1 + a_2 b_0 = 0 \Rightarrow b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{1 \cdot (-1) + 0}{1} = 1[/math]
    [math]\dots[/math]
    [math]b_n = - \dfrac{a_1 b_{n - 1}}{a_0} = -b_{n - 1}[/math]
    [math]B(s) = 1 - s + s^2 - s^3 + \dots[/math]
  2. Пусть теперь надо построить обратный ряд для [math]A(s) = 1 - s - s^2[/math]:
    [math]b_0 = \dfrac{1}{a_0} = \dfrac{1}{1} = 1[/math]
    [math]b_1 = - \dfrac{a_1 b_0}{a_0} = - \dfrac{(-1) \cdot 1}{1} = 1[/math]
    [math]b_2 = - \dfrac{a_1 b_1 + a_2 b_0}{a_0} = - \dfrac{(-1) \cdot 1 + (-1) \cdot 1}{1} = 2[/math]
    [math]b_3 = - \dfrac{a_1 b_2 + a_2 b_1}{a_0} = - \dfrac{(-1) \cdot 2 + (-1) \cdot 1}{1} = 3[/math]
    [math]\dots[/math]
    [math]b_n = - \dfrac{a_1 b_{n - 1} + a_2 b_{n - 2}}{a_0} = b_{n - 1} + b_{n - 2}[/math]
    [math]B(s) = 1 + s + 2 s^2 + 3 s^3 + \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].


Определение:
Композицией (подстановкой) (англ. composition) формальных степенных рядов [math]A[/math] и [math]B[/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(0) \ne 0[/math], не определена. (При попытке подставить такой ряд для вычисления коэффициентов результата возникает необходимость суммирования бесконечных числовых рядов).

Обратный ряд

Определение:
Левым обратным (англ. left inverse) по операции подстановки формальным степенным рядом для ряда [math]B(t)[/math] называется такой ряд [math]A(s)[/math], что [math]A(B(t)) = t[/math]. Аналогично, правым обратным (англ. right inverse) формальным степенным рядом для [math]B(t)[/math] называется такой [math]C(u)[/math], что [math]B(C(u)) = u[/math].


Теорема (об обратном формальном степенном ряде):
Пусть ряд [math]B(t) = b_0 + 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(t)[/math] является левым обратным, а [math]C(u)[/math] — правым обратным для [math]B(s)[/math]. При этом, ряды [math]A[/math] и [math]C[/math] единственны.
Доказательство:
[math]\triangleright[/math]
Докажем по индукции существование и единственность левого обратного ряда. Доказательство для правого аналогично.
Будем определять коэффициенты ряда [math]A[/math] последовательно. Поскольку [math]A(B(t)) = t[/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]B(t) = t + t^2[/math]:

[math]a_0 = 0[/math]
[math]a_1 = \dfrac{1}{b_1} = 1[/math]
[math]a_1 b_2 + a_2 b_1^2 = 0 \Rightarrow a_2 = - \dfrac{a_1 b_2}{b_1^2} = - \dfrac{1 \cdot 1}{1^2} = -1[/math]
[math]a_1 b_3 + 2 a_2 b_1 b_2 + a_3 b_1^3 = 0 \Rightarrow a_3 = - \dfrac{a_1 b_3 + 2 a_2 b_1 b_2}{b_1^3} = - \dfrac{1 \cdot 0 + 2 \cdot (-1) \cdot 1}{1^3} = 2[/math]
[math]\dots[/math]
[math]A(s) = s - s^2 + 2 s^3 + \dots[/math]

Сдвиги

Сдвиг вправо

Сдвиг ряда вправо на [math]k[/math] получается домножением его на [math]s^k[/math]. Например, пусть исходный ряд [math]A(s) = a_0 + a_1 s + a_2 s^2 + \dots[/math]. Сдвинем его на [math]k[/math] вправо: [math]B(s) = s^k \cdot A(s) = a_0 s^k + a_1 s^{k + 1} + a_2 s^{k + 2} + \dots = 0 + 0 s + 0 s^2 + \dots + a_0 s^k + a_1 s^{k + 1} + \dots[/math].

Сдвиг влево

Сдвинуть ряд влево на [math]k[/math] можно, вычтя из него первые [math]k[/math] слагаемых и затем разделив его на [math]s^k[/math]. Например, сдвинем ряд [math]A(s) = a_0 + a_1 s + a_2 s^2 + \dots[/math] на [math]k[/math] влево: [math]B(s) = \dfrac{A(s) - (a_0 + a_1 s + a_2 s^2 + \dots + a_{k - 1} s^{k - 1})}{s^k} = a_k + a_{k + 1} s + a_{k + 2} s^2 + \dots[/math].


Сдвиги могут быть полезны для упрощения вычисления производящих функций. Например, попробуем получить функцию для чисел Фибоначчи, используя сдвиги. Пусть формальный степенной ряд для нее равен [math]F(s) = f_0 + f_1 s + f_2 s^2 + \dots[/math], при этом [math]f_0 = f_1 = 1[/math], [math]f_n = f_{n - 2} + f_{n - 1}, n \gt 1[/math]. Рассмотрим сумму этого ряда и ряда, полученного из него сдвигом на [math]1[/math] вправо: [math]F(s) + s \cdot F(s) = (f_0 + f_1 s + f_2 s^2 + f_3 s^3 + \dots) + (0 + f_0 s + f_1 s^2 + f_2 s^3 + \dots) = (f_0 + 0) + (f_1 + f_0) s + (f_2 + f_1) s^2 + (f_3 + f_2) s^3 + \dots = f_1 + f_2 s + f_3 s^2 + f_4 s^3 + \dots[/math]. Заметим, что результат равен сдвигу [math]F(s)[/math] на [math]1[/math] влево. Составим и решим уравнение: [math]F(s) + s \cdot F(s) = \dfrac{F(s) - 1}{s}[/math]; [math]F(s)(s^2 + s - 1) = -1[/math]; [math]F(s) = \dfrac{1}{1 - s - s^2}[/math].

См. также

Источники информации

  • Ландо С. К., Лекции о производящих функциях. — 3-е изд., испр. — М.: МЦНМО, 2007. — 144с. ISBN 978-5-94057-042-4