18
правок
Изменения
Добавил примеры вывода n-го члена последовательности из производящей функции, вставил в лемму id
{{Лемма
|id=lemma1
|statement=Производящая функция для последовательности <tex>a_0, a_1,
a_2, \dots</tex> рациональна тогда и только тогда, когда существуют такие числа <tex>q_1, \dots, q_l</tex> и такие многочлены <tex>p_1(n),
|proof= Для доказательства теоремы осталось заметить, что произведение квазимногочленов является квазимногочленом. Это утверждение непосредственно вытекает из формулы <tex>a_n = p_1(n) q_1^n + \dots + p_l(n) q_l^n</tex>.}}
== Примеры применения теоремы ==
{{Задача
|definition = Представьте в виде линейной рекуррентности производящую функцию <tex>A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}</tex>
}}
Разобьем дробь на сумму простых дробей: <tex>A(s)=\dfrac{1 + 2s}{(1 - 2s)(1 + 3s)}=\dfrac{1/5}{1 + 3s} + \dfrac{4/5}{1 - 2s}</tex>
Воспользуемся результатом [[#lemma1|леммы]]: коэффициент при <tex>s^n</tex> равен <tex>\dfrac{(n + 1)(n + 2)\dots(n + k - 1)}{(k - 1)!} q^{n}</tex>.
Для первой дроби <tex>k = 1,\, q = -3</tex>, для второй: <tex>k = 1,\, q = 2</tex>.
Тогда <tex>a_{n} = \frac{1}{5} \cdot \dfrac{1}{(1 - 1)!} (-3)^{n} + \frac{4}{5} \cdot \dfrac{1}{(1 - 1)!} (2)^{n} =
\frac{(-3)^{n}}{5} + \frac{4}{5} \cdot 2^{n} </tex>
{{Задача
|definition = Представьте в виде линейной рекуррентности производящую функцию <tex>A(s)=\dfrac{s^2}{(1 - 2s)^{2}(1 + s)(1 - s)}</tex>
}}
Разобьем на сумму простых дробей: <tex>A(s)=\dfrac{s^2}{(1 - 2s)^{2}(1 + s)(1 - s)} = \dfrac{1/18}{1 + s} + \dfrac{-8/9}{1 - 2s} + \dfrac{1/3}{(1 - 2s)^2} + \dfrac{1/2}{1 - s}</tex>
Используем лемму:
первая дробь: <tex>k = 1,\, q = -1</tex>, вторая: <tex>k = 1, q = 2</tex>, третья: <tex>k = 2,\, q = 2</tex>, четвертая: <tex>k = 1,\, q = 1</tex>,
тогда <tex>a_{n} = \dfrac{(-1)^n}{18} - \dfrac{8}{9} \cdot 2^n + \dfrac{n + 1}{(2 - 1)!} \cdot 2^n + \dfrac{(1)^n}{2}=(n + \frac{1}{9}) \cdot 2^n + (-1)^{n}\frac{1}{18} + \frac{1}{2}</tex>
== См. также ==
