Интегрирование/дифференцирование производящих функций — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Создание страницы)
 
(Пример 3)
 
(не показаны 24 промежуточные версии 4 участников)
Строка 1: Строка 1:
==Дифференцирование и интегрирование производящих рядов==
+
==Дифференцирование и интегрирование производящих функций==
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> - степенной ряд.  
+
Пусть <tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex> — [[Производящая функция | производящая функция]].  
  
''Производная'' этого степенного ряда выражается формулой
+
''Производной'' этой функции называется функция
<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>
 
  
''Интеграл'' этого степенного ряда выражается формулой
+
:<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots</tex>
<tex>\int\limits A(s) = a_0 s + a_1 \dfrac{s^2}{2} + a_2 \dfrac{s^3}{3} + \dots + a_n \dfrac{s^{n+1} }{n + 1} + \dots</tex>
+
 
 +
''Интегралом'' называется функция
 +
 
 +
:<tex>\int\limits A(s) = a_0 s + a_1 \dfrac{s^2}{2} + a_2 \dfrac{s^3}{3} + \dots + a_n \dfrac{s^{n+1} }{n + 1} + \dots</tex>
 
}}
 
}}
  
 
Операция дифференцирования обратна операции интегрирования:
 
Операция дифференцирования обратна операции интегрирования:
  
<tex>(\int\limits A(s))' = A(s)</tex>.
+
:<tex>(\int\limits A(s))' = A(s)</tex>.
  
 
Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.
 
Операция же интегрирования производной приводит к функции с нулевым свободным членом, и поэтому результат, вообще говоря, отличается от исходной функции.
  
<tex> \int\limits A'(s) = A(s) - A(0) </tex>
+
:<tex> \int\limits A'(s) = A(s) - a_0</tex>.
  
 
===Замечание===
 
===Замечание===
Строка 26: Строка 28:
 
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом
 
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом
  
<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
+
:<tex> \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi </tex>.
 
}}
 
}}
  
==Радиусы сходимости==
+
==Примеры==
 +
 
 +
===Пример <tex>1</tex>===
 +
 
 +
Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию
 +
 
 +
:<tex> f(s) = \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} s + \dfrac{1}{3 \times 4} s^2 + \dots + \dfrac{1}{(n + 1)(n + 2)} s^n + \dots </tex>
 +
 
 +
Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем
 +
 
 +
:<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln \dfrac{1}{1 -
 +
s}</tex>,
 +
 
 +
откуда
 +
 
 +
:<tex> f(s) = s^{-2} \int\limits \ln \dfrac{1}{1 - s} = s^{-1} ((s - 1) \ln \dfrac{1}{1 - s} + s) </tex>.
 +
 
 +
===Пример <tex>2</tex>===
 +
 
 +
Используя только что полученные знания о дифференцировании и интегрировании производящих функций, попробуем решить следующее рекуррентное уравнение:
 +
 
 +
:<tex> g_0 = 1</tex>
 +
:<tex> g_1 = 1</tex>
 +
:<tex> g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n</tex>
 +
 
 +
Умножим обе части всех равенств на <tex>z</tex> в соответствующей степени и просуммируем:
 +
 
 +
:<tex> z^0 g_0 = 1</tex>
 +
:<tex> z^1 g_1 = z</tex>
 +
:<tex> z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n</tex>
 +
 
 +
:<tex> g_0 + g_1 z + \sum\limits_{n = 2}^{\infty} g_n z^n = 1 + z + \sum\limits_{n = 2}^{\infty} g_{n - 1} z^n + 2 \sum\limits_{n = 2}^{\infty} g_{n - 2} z^n + \sum\limits_{n = 2}^{\infty} (-1)^n z^n </tex>
 +
 
 +
Левая часть <tex> G(z) = g_0 + g_1 z + \sum\limits_{n = 2}^{\infty} g_n z^n = \sum\limits_{n = 0}^{\infty} g_n z^n </tex> представляет собой производящую функцию в бесконечном виде.
 +
 
 +
Попытаемся выразить правую часть через <tex>G(z)</tex>. Рассмотрим каждое слагаемое:
 +
 
 +
:<tex>\sum\limits_{n = 2}^{\infty} g_{n - 1} z^n = z \sum\limits_{n = 2}^{\infty} g_{n - 1} z^{n - 1} = z (G(z) - g_0) = z(G(z) - 1)</tex>
  
{{Теорема
+
:<tex>\sum\limits_{n = 2}^{\infty} g_{n - 2} z^n = z^2 \sum\limits_{n = 2}^{\infty} g_{n - 2} z^{n - 2} = z^2 G(z)</tex>
|statement= Ряд
+
 
 +
:<tex>\sum\limits_{n = 2}^{\infty} (-1)^n z^n = z^2 - z^4 + z^6 - z^8 + \dots = 1 - z + z^2 -z^4 + z^6 -z^8 + \dots -1 + z = \sum\limits_{n = 0}^{\infty} (-1)^n z^n - 1 + z = \dfrac{1}{1 + z} - 1 + z</tex>
 +
 
 +
Составляем уравнение:
 +
 
 +
:<tex>G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z</tex>
 +
:<tex>G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z</tex>
 +
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}</tex>
 +
:<tex>G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}</tex>
 +
 
 +
Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений <tex>z</tex>), получаем:
 +
 
 +
:<tex>G(z) = \dfrac{1}{3} \times \dfrac{1}{(1 + z)^2} - \dfrac{1}{9} \times \dfrac{1}{1 + z} + \dfrac{7}{9} \times \dfrac{1}{1 - 2 z}</tex>
 +
 
 +
Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придётся чуть повозиться. Используя правило дифференцирования производящих функций имеем:
 +
 
 +
:<tex>\dfrac{1}{(1 + z)^2} = (- \dfrac{1}{1 + z})' = (\sum\limits_{n = 0}^{\infty} (-1)^{n + 1} z^n)' = \sum\limits_{n = 0}^{\infty} (-1)^{n + 1} n z^{n - 1} = \sum\limits_{n = 0}^{\infty} (-1)^n (n + 1) z^n</tex>
 +
 
 +
Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:
 +
 
 +
<tex>G(z) = \dfrac{1}{3} \sum\limits_{n = 0}^{\infty} (-1)^n (n + 1) z^n - \dfrac{1}{9} \sum\limits_{n = 0}^{\infty} (-1)^n z^n + \dfrac{7}{9} \sum\limits_{n = 0}^{\infty} 2^n z^n = \sum\limits_{n = 0}^{\infty} (\dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})) z^n</tex>
 +
 
 +
Мы искали <tex>G(z)</tex> в виде <tex>G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n</tex>, значит
 +
 
 +
:<tex>g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})</tex>
  
<tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots</tex>
+
===Пример <tex>3</tex>===
  
имеет тот же интервал сходимости, что и ряд
+
Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся [[Производящая функция#Приложения | разложением экспоненты]]:
  
<tex>\int\limits A(s) = a_0 s + a_1 \dfrac{s^2}{2} + a_2 \dfrac{s^3}{3} + \dots + a_n \dfrac{s^{n+1} }{n + 1} + \dots</tex>
+
:<tex>e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n</tex>
}}
 
  
{{Теорема
+
Разложение экспоненты начинается с <tex>1</tex>, поэтому аргумент логарифма нужно сдвинуть в <tex>1</tex>:
|statement= Ряд
 
  
<tex>A(s) = a_0 + a_1 s + a_2 s^2 + \dots (1)</tex>
+
:<tex>\ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots</tex>
  
имеет тот же интервал сходимости, что и ряд
+
(свободный член в разложении равен <tex>0</tex>, поскольку <tex>\ln(1) = 0</tex>). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают <tex>1</tex>. Поскольку <tex>\dfrac{d}{ds} e^s = e^s</tex>, получаем
  
<tex>A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots (2)</tex>
+
:<tex>\dfrac{d}{dt} \ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots</tex>,
  
|proof=
+
откуда, интегрируя,
  
Пусть <tex> x_0 </tex> - произвольная точка интервала сходимости ряда <tex> (1) </tex>, т.е. <tex> |x_0| < R </tex>. Возьмем число <tex> r </tex>, удовлетворяющее условию <tex> |x_0| < r < R </tex>. Оценим модуль общего члена ряда <tex> (5) </tex> в рассматриваемой точке <tex> x_0 </tex>. Имеем
+
:<tex>\ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots</tex>
  
<tex> |n a_n x_0^{n - 1}| \leqslant |a_n r^n| \dfrac{n |x_0|^{n-1}}{r^n} </tex>
+
Чаще используется следующий вариант:
  
Ряд <tex> (1) </tex> абсолютно сходится в точке <tex> r </tex>, т.е. сходится ряд <tex> \sum\limits_{n = 0}^{\infty} |a_n| r^n </tex> и, следовательно, <tex> \lim\limits_{n \to \infty} |a_n| r^n = 0 </tex>. Значит последовательность <tex> \{|a_n| r^n\} </tex> ограничена, т.е. <tex> |a_n| r^n < M </tex> при <tex> n \in \mathbb{N} </tex>, где <tex> M \in \mathbb{R} </tex>. Учитывая это, находим
+
:<tex>-\ln(1 - t) = \ln \dfrac{1}{1 - t} = t + \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 + \dfrac{1}{4}t^4 + \dots</tex>
  
<tex> |n a_n x_0^{n - 1}| \leqslant M \dfrac{n |x_0|^{n - 1}}{r^n} </tex>
+
==Решение обыкновенных дифференциальных уравнений на производящие функции==
  
Ряд <tex> \sum\limits_{n = 1}^{\infty} \dfrac{n |x_0|^{n - 1}}{r^n} = \sum\limits_{n = 1}^{\infty} b_n </tex> сходится, так как
+
{{Теорема
 +
|about= О существовании и единственности решения
 +
|statement=
 +
Рассмотрим обыкновенное дифференциальное уравнение
  
<tex> \lim\limits_{n \to \infty} \dfrac{b_{n + 1}}{b_n} = \lim\limits_{n \to \infty} \dfrac{(n + 1)}{n} \dfrac{|x_0|}{r} = \dfrac{|x_0|}{r} < 1 </tex>.
+
:<tex>f'(s) = F(s, f(s)) \text{ }\text{ }\text{ }\text{ }\text{ } (1)</tex>
  
Используя теорему сравнения, получаем сходимость ряда
+
на производящую функцию <tex>f(s)</tex>, где <tex>F = F(s, t)</tex> — [[Производящие функции нескольких переменных | производящая функция двух переменных]], являющаяся многочленом по <tex>t</tex> (т.е. степень <tex>F</tex> по <tex>t</tex> конечна). Тогда для каждого <tex>f_0</tex> уравнение <tex>(1)</tex> имеет единственное решение, удовлетворяющее условию <tex>f(0) = f_0</tex>
  
<tex> \sum\limits_{n = 1}^{\infty} |n a_n x_0^{n - 1}| </tex>
+
|proof=
 +
Доказательство проводится обычным способом последовательного нахождения коэффициентов функции <tex>f</tex>. Пусть степень <tex>F</tex> по <tex>t</tex> равна <tex>n</tex> и
  
или, что то же, абсолютную сходимость ряда <tex> \sum\limits_{n = 1}^{\infty} n a_n x_0^{n - 1} </tex> в точке <tex> x_0 </tex>. В силу произвольности выбора точки <tex> x_0 </tex> из интервала <tex> (-R, R) </tex>, заключаем, что ряд <tex> (2) </tex> имеет интервал сходимости не меньший интервала сходимости ряда <tex> (1) </tex>. Докажем, что интервал сходимости ряда <tex> (2) </tex> не больше интервала сходимости ряда <tex> (1) </tex>. Допустим противное, а именно допустим, что ряд <tex> (2) </tex> сходится в интервале <tex> (-R_1, R_1) </tex>, где <tex> R_1 > R </tex>. Так как ряд <tex> (2) </tex> степенной, его можно почленно интегрировать в пределах от <tex> 0 </tex> до <tex> x </tex>, где <tex> |x| < R_1 </tex>. Ряд, полученный в результате интегрирования, сходится в интервале <tex> (-R_1, R_1) </tex>. Он отличается от ряда <tex> (1) </tex> только на постоянное слагаемое. Следовательно, и ряд <tex> (2) </tex> сходится в интервале <tex> (-R_1, R_1) </tex>, что противоречит допущению <tex> R_1 > R </tex>.
+
:<tex>F(s, t) = (F_{00} + F_{10} s + F_{20} s^2 + \dots) + (F_{01} + F_{11} s + F_{21} s^2 + \dots) t + \dots + (F_{0n} + F_{1n} s + F_{2n} s^2 + \dots) t^n, f(s) = f_0 + f_1 s + f_2 s^2 + \dots</tex>
  
}}
+
Приравнивая коэффициенты при <tex>s^0</tex> в левой и правой частях уравнения <tex>(1)</tex>
  
==Примеры==
+
Возьмем с первого слагаемого:
  
===Пример 1===
+
:<tex>(F_{00} + F_{10} s + F_{20} s^2 + \dots) \rightarrow F_{00}</tex>
  
Последнее замечание позволяет подсчитывать (т. е. выражать в терминах элементарных) производящие функции для большого числа разнообразных последовательностей. Вычислим, например, производящую функцию
+
Возьмем со второго слагаемого:
  
<tex> f(s) = \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} s + \dfrac{1}{3 \times 4} s^2 + \dots + \dfrac{1}{(n + 1)(n + 2)} s^n + \dots </tex>
+
:<tex>(F_{01} + F_{11} s + F_{21} s^2 + \dots) t = (F_{01} + F_{11} s + F_{21} s^2 + \dots) (f_0 + f_1 s + f_2 s^2 + \dots) \rightarrow F_{01} f_0</tex>
  
Умножая функцию <tex> f </tex> на <tex> s^2 </tex> и дифференцируя, получаем
+
Возьмем с <tex>n</tex>-го слагаемого:
  
<tex>(s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln(1 -
+
:<tex>(F_{0n} + F_{1n} s + F_{2n} s^2 + \dots) t^n = (F_{0n} + F_{1n} s + F_{2n} s^2 + \dots) (f_0 + f_1 s + f_2 s^2 + \dots)^n \rightarrow F_{0n} f_0^n</tex>
s)^{-1}</tex>,
 
  
откуда
+
Итого выходит:
  
<tex> f(s) = s^{-2} \int\limits \ln (1 - s)^{-1} = s^{-1} ((s - 1) \ln (1 - s)^{-1} + s) </tex>.
+
:<tex>f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n</tex>
  
 +
Аналогично, равенство коэффициентов при <tex>s^1</tex> дает
  
===Пример 2===
+
:<tex>2 f_2 = F_{10} + F_{01} f_1 + F_{11} f_0 + \dots + F_{0n} f_0^{n - 1} f_1 + F_{1n} f_0^n</tex>
  
Найдем представление в виде степенного ряда функции <tex> \ln (1 + x), |x| < 1 </tex>.
+
Вообще, <tex>f_n</tex> находится из уравнения
  
Воспользуемся разложением
+
:<tex>n f_n = \dots \text{ }\text{ }\text{ }\text{ }\text{ } (2)</tex>,
  
<tex> \dfrac{1}{1 + x} = 1 - x + x^2 - x^3 + \dots = \sum\limits_{n = 0}^{\infty} (-1)^n x^n, |x| < 1 </tex>
+
где точками обозначен многочлен от коэффициентов функции <tex>F</tex> и коэффициентов <tex>f_0, f_1, \dots, f_{n-1}</tex> функции <tex>f</tex>. При каждом <tex>n > 0</tex> уравнение <tex>(2)</tex> имеет единственное решение. Значит уравнение <tex>(1)</tex> имеет однозначное решение для каждого <tex>f_0</tex>.
  
Интегрируя этот ряд почленно на отрезке <tex> [0, x] </tex>, находим
+
}}
  
<tex> \ln (1 + x) = \int\limits_{0}^{x} \dfrac{dt}{1 + t} = \int\limits_{0}^{x} (1 - t + t^2 - t^3 + \dots)dt = x - \dfrac{x^2}{2} + \dfrac{x^3}{3} - \dfrac{x^4}{4} + \dots = \sum\limits_{n = 0}^{\infty} \dfrac{(-1)^n x^{n + 1}}{n + 1} =  \sum\limits_{n = 1}^{\infty} \dfrac{(-1)^{n + 1} x^n}{n} </tex>
+
==См. также==
 +
* [[Производящая функция]]
 +
* [[Производящие функции нескольких переменных]]
 +
* [[Арифметические действия с формальными степенными рядами]]
  
 
==Источники информации==
 
==Источники информации==
 
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4
 
* ''Ландо С. К.'', Лекции о производящих функциях. {{---}} 3-е изд., испр. {{---}} М.: МЦНМО, 2007. {{---}} 144с. ISBN 978-5-94057-042-4
  
* [http://www.apmath.spbu.ru/ru/education/final/question06.pdf Степенные ряды. Радиус сходимости и интервал сходимости. Характер сходимости. Интегрирование и дифференцирование] (07.06.2017)
+
* [https://habrahabr.ru/post/204258/ Производящие функции — туда и обратно] (10.06.2017)
 +
 
 +
* [https://math.hse.ru/data/2011/02/18/1208528471/DiscrMath09.pdf Элементы перечислительной комбинаторики] (10.06.2017)
  
* [http://www.math24.ru/%D0%B4%D0%B8%D1%84%D1%84%D0%B5%D1%80%D0%B5%D0%BD%D1%86%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5-%D0%B8-%D0%B8%D0%BD%D1%82%D0%B5%D0%B3%D1%80%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5-%D1%81%D1%82%D0%B5%D0%BF%D0%B5%D0%BD%D0%BD%D1%8B%D1%85-%D1%80%D1%8F%D0%B4%D0%BE%D0%B2.html Дифференцирование и интегрирование степенных рядов]
+
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Производящие функции]]

Текущая версия на 19:28, 17 апреля 2018

Дифференцирование и интегрирование производящих функций[править]

Определение:
Пусть [math]A(s) = a_0 + a_1 s + a_2 s^2 + \dots[/math] производящая функция.

Производной этой функции называется функция

[math]A'(s) = a_1 + 2 a_2 s + 3 a_3 s^2 + \dots + n a_n s^{n-1} + \dots[/math]

Интегралом называется функция

[math]\int\limits A(s) = a_0 s + a_1 \dfrac{s^2}{2} + a_2 \dfrac{s^3}{3} + \dots + a_n \dfrac{s^{n+1} }{n + 1} + \dots[/math]


Операция дифференцирования обратна операции интегрирования:

[math](\int\limits A(s))' = A(s)[/math].

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

[math] \int\limits A'(s) = A(s) - a_0[/math].

Замечание[править]

Утверждение:
Для функций, представимых в виде степенных рядов, формула для производной соответствует обычной. Формула для интеграла соответствует значению интеграла с переменным верхним пределом
[math] \int\limits A(s) = \int\limits_{0}^{s} A(\xi) d \xi [/math].

Примеры[править]

Пример [math]1[/math][править]

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

[math] f(s) = \dfrac{1}{1 \times 2} + \dfrac{1}{2 \times 3} s + \dfrac{1}{3 \times 4} s^2 + \dots + \dfrac{1}{(n + 1)(n + 2)} s^n + \dots [/math]

Умножая функцию [math] f [/math] на [math] s^2 [/math] и дифференцируя, получаем

[math](s^2 f(s))' = s + \dfrac{1}{2} s^2 + \dfrac{1}{3} s^3 + \dots = \ln \dfrac{1}{1 - s}[/math],

откуда

[math] f(s) = s^{-2} \int\limits \ln \dfrac{1}{1 - s} = s^{-1} ((s - 1) \ln \dfrac{1}{1 - s} + s) [/math].

Пример [math]2[/math][править]

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

[math] g_0 = 1[/math]
[math] g_1 = 1[/math]
[math] g_n = g_{n - 1} + 2 g_{n - 2} + (-1)^n[/math]

Умножим обе части всех равенств на [math]z[/math] в соответствующей степени и просуммируем:

[math] z^0 g_0 = 1[/math]
[math] z^1 g_1 = z[/math]
[math] z^n g_n = z^n g_{n-1} + 2 z^n g_{n-2} + (-1)^n z^n[/math]
[math] g_0 + g_1 z + \sum\limits_{n = 2}^{\infty} g_n z^n = 1 + z + \sum\limits_{n = 2}^{\infty} g_{n - 1} z^n + 2 \sum\limits_{n = 2}^{\infty} g_{n - 2} z^n + \sum\limits_{n = 2}^{\infty} (-1)^n z^n [/math]

Левая часть [math] G(z) = g_0 + g_1 z + \sum\limits_{n = 2}^{\infty} g_n z^n = \sum\limits_{n = 0}^{\infty} g_n z^n [/math] представляет собой производящую функцию в бесконечном виде.

Попытаемся выразить правую часть через [math]G(z)[/math]. Рассмотрим каждое слагаемое:

[math]\sum\limits_{n = 2}^{\infty} g_{n - 1} z^n = z \sum\limits_{n = 2}^{\infty} g_{n - 1} z^{n - 1} = z (G(z) - g_0) = z(G(z) - 1)[/math]
[math]\sum\limits_{n = 2}^{\infty} g_{n - 2} z^n = z^2 \sum\limits_{n = 2}^{\infty} g_{n - 2} z^{n - 2} = z^2 G(z)[/math]
[math]\sum\limits_{n = 2}^{\infty} (-1)^n z^n = z^2 - z^4 + z^6 - z^8 + \dots = 1 - z + z^2 -z^4 + z^6 -z^8 + \dots -1 + z = \sum\limits_{n = 0}^{\infty} (-1)^n z^n - 1 + z = \dfrac{1}{1 + z} - 1 + z[/math]

Составляем уравнение:

[math]G(z) = 1 + z + z(G(z) - 1) + 2 z^2 G(z) + \dfrac{1}{1 + z} - 1 + z[/math]
[math]G(z) (1 - z - 2 z^2) = \dfrac{1}{1 + z} + z[/math]
[math]G(z) = \dfrac{1 + z + z^2}{(1 + z) (1 - z - 2 z^2)}[/math]
[math]G(z) = \dfrac{1 + z + z^2}{(1 + z)^2 (1 - 2 z)}[/math]

Это и есть производящая функция для заданного рекуррентного уравнения. Раскладывая её на простейшие дроби (например, методом неопределенных коэффициентов или методом подстановки различных значений [math]z[/math]), получаем:

[math]G(z) = \dfrac{1}{3} \times \dfrac{1}{(1 + z)^2} - \dfrac{1}{9} \times \dfrac{1}{1 + z} + \dfrac{7}{9} \times \dfrac{1}{1 - 2 z}[/math]

Второе и третье слагаемые легко раскладываются в степенной ряд, а вот с первым придётся чуть повозиться. Используя правило дифференцирования производящих функций имеем:

[math]\dfrac{1}{(1 + z)^2} = (- \dfrac{1}{1 + z})' = (\sum\limits_{n = 0}^{\infty} (-1)^{n + 1} z^n)' = \sum\limits_{n = 0}^{\infty} (-1)^{n + 1} n z^{n - 1} = \sum\limits_{n = 0}^{\infty} (-1)^n (n + 1) z^n[/math]

Собственно всё. Раскладываем каждое слагаемое в степенной ряд и получаем ответ:

[math]G(z) = \dfrac{1}{3} \sum\limits_{n = 0}^{\infty} (-1)^n (n + 1) z^n - \dfrac{1}{9} \sum\limits_{n = 0}^{\infty} (-1)^n z^n + \dfrac{7}{9} \sum\limits_{n = 0}^{\infty} 2^n z^n = \sum\limits_{n = 0}^{\infty} (\dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})) z^n[/math]

Мы искали [math]G(z)[/math] в виде [math]G(z) = \sum\limits_{n = 0}^{\infty} g_n z^n[/math], значит

[math]g_n = \dfrac{7}{9} 2^n + (-1)^n (\dfrac{1}{3} n + \dfrac{2}{9})[/math]

Пример [math]3[/math][править]

Вычислим обратную функцию к экспоненте. Для этого мы воспользуемся разложением экспоненты:

[math]e^z = \sum\limits_{z = 0}^{\infty} \dfrac{1}{n!} z^n[/math]

Разложение экспоненты начинается с [math]1[/math], поэтому аргумент логарифма нужно сдвинуть в [math]1[/math]:

[math]\ln(1 + t) = l_1 t + l_2 t^2 + l_3 t^3 + \dots[/math]

(свободный член в разложении равен [math]0[/math], поскольку [math]\ln(1) = 0[/math]). Для вычисления коэффициентов разложения логарифма воспользуемся тем, что производная функции и обратной к ней в произведении дают [math]1[/math]. Поскольку [math]\dfrac{d}{ds} e^s = e^s[/math], получаем

[math]\dfrac{d}{dt} \ln(1 + t) = \dfrac{1}{1 + t} = 1 - t + t^2 - t^3 + t^4 - \dots[/math],

откуда, интегрируя,

[math]\ln(1 + t) = t - \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 - \dfrac{1}{4}t^4 + \dots[/math]

Чаще используется следующий вариант:

[math]-\ln(1 - t) = \ln \dfrac{1}{1 - t} = t + \dfrac{1}{2}t^2 + \dfrac{1}{3}t^3 + \dfrac{1}{4}t^4 + \dots[/math]

Решение обыкновенных дифференциальных уравнений на производящие функции[править]

Теорема (О существовании и единственности решения):
Рассмотрим обыкновенное дифференциальное уравнение
[math]f'(s) = F(s, f(s)) \text{ }\text{ }\text{ }\text{ }\text{ } (1)[/math]
на производящую функцию [math]f(s)[/math], где [math]F = F(s, t)[/math] производящая функция двух переменных, являющаяся многочленом по [math]t[/math] (т.е. степень [math]F[/math] по [math]t[/math] конечна). Тогда для каждого [math]f_0[/math] уравнение [math](1)[/math] имеет единственное решение, удовлетворяющее условию [math]f(0) = f_0[/math]
Доказательство:
[math]\triangleright[/math]

Доказательство проводится обычным способом последовательного нахождения коэффициентов функции [math]f[/math]. Пусть степень [math]F[/math] по [math]t[/math] равна [math]n[/math] и

[math]F(s, t) = (F_{00} + F_{10} s + F_{20} s^2 + \dots) + (F_{01} + F_{11} s + F_{21} s^2 + \dots) t + \dots + (F_{0n} + F_{1n} s + F_{2n} s^2 + \dots) t^n, f(s) = f_0 + f_1 s + f_2 s^2 + \dots[/math]

Приравнивая коэффициенты при [math]s^0[/math] в левой и правой частях уравнения [math](1)[/math]

Возьмем с первого слагаемого:

[math](F_{00} + F_{10} s + F_{20} s^2 + \dots) \rightarrow F_{00}[/math]

Возьмем со второго слагаемого:

[math](F_{01} + F_{11} s + F_{21} s^2 + \dots) t = (F_{01} + F_{11} s + F_{21} s^2 + \dots) (f_0 + f_1 s + f_2 s^2 + \dots) \rightarrow F_{01} f_0[/math]

Возьмем с [math]n[/math]-го слагаемого:

[math](F_{0n} + F_{1n} s + F_{2n} s^2 + \dots) t^n = (F_{0n} + F_{1n} s + F_{2n} s^2 + \dots) (f_0 + f_1 s + f_2 s^2 + \dots)^n \rightarrow F_{0n} f_0^n[/math]

Итого выходит:

[math]f_1 = F_{00} + F_{01} f_0 + \dots + F_{0n} f_0^n[/math]

Аналогично, равенство коэффициентов при [math]s^1[/math] дает

[math]2 f_2 = F_{10} + F_{01} f_1 + F_{11} f_0 + \dots + F_{0n} f_0^{n - 1} f_1 + F_{1n} f_0^n[/math]

Вообще, [math]f_n[/math] находится из уравнения

[math]n f_n = \dots \text{ }\text{ }\text{ }\text{ }\text{ } (2)[/math],
где точками обозначен многочлен от коэффициентов функции [math]F[/math] и коэффициентов [math]f_0, f_1, \dots, f_{n-1}[/math] функции [math]f[/math]. При каждом [math]n \gt 0[/math] уравнение [math](2)[/math] имеет единственное решение. Значит уравнение [math](1)[/math] имеет однозначное решение для каждого [math]f_0[/math].
[math]\triangleleft[/math]

См. также[править]

Источники информации[править]

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