Просмотр исходного текста страницы Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

== Необходимые определения ==

{{Определение
|id=def_rational. 
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется дробно-рациональной(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
}}

Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.

Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].

Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>

{{Определение
|id=def_linear. 
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется заданной линейной рекуррентой (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
}}






== Теорема о связи этих понятий ==

{{Теорема
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
|proof=

<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.

Так как <tex>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>

Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = k</tex>)

Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex>

Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>

<tex>\Rightarrow)</tex>

Напишем друг под другом несколько производящих функций:

<tex>A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</tex>

<tex>-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>

<tex>-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - \ldots - c_2 \cdot a_{k - 2} \cdot t^k - \ldots - c_2 \cdot a_{n - 2} \cdot t^n - \ldots</tex>

<tex>\cdots</tex>

<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex>

Почленно складывая эти формальные степенные ряды, получаем

<tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1} + (a_k - \sum\limits_{i = 1}^k c_i \cdot a_{k - i}) \cdot t^k + \ldots + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex> 

Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</tex>-ой степени включительно обнулятся.

Тогда <tex>A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \\ + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>. 

Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</tex>, 

а <tex>P(t) = a_0 + (a_1 - c_1 \cdot a_0) \cdot t + (a_2 - c_1 \cdot a_1 - c_2 \cdot a_0) \cdot t^2 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>

Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
}}



== Примеры применения теоремы ==

* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = a_{n - 1}</tex>
*: Так как последовательность задана линейной рекуррентой, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - x</tex> (так как <tex>c_1 = 1</tex>), а <tex>deg(P) < 2</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - x}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots = \dfrac{C}{1 - x}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots) \cdot (1 - x) = C</tex>
*: Пользуясь правилом перемножения формальных степенных рядов, получаем
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1<tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - x}<tex>

==См. также==
* [[Арифметические действия с формальными степенными рядами| Арифметические действия с формальными степенными рядами]]
* [[Производящая функция| Производящая функция]]

== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика]]
[[Категория: Производящие функции]]