137
правок
Изменения
Нет описания правки
=== Необходимые определения ===
{{Определение
|id=def_rational.
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
|definition=Производящая функция <tex>F(t)</tex> называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \fracdfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> - многочлены конечной степени
}}
|definition=Последовательность <tex>a_0, a_1, ..., a_n, ... </tex> называется заданной линейной рекуррентой, если её члены <tex>a_0 ... a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}</tex>
}}
=== Теорема ===
{{Теорема
|id=th_main.
|statement=<tex>a_0, a_1, ..., a_n, ... </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \fracdfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>
|proof=
<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \fracdfrac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < 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 - ... - c_k \cdot t^k</tex>.
Так как <tex>deg P(t) < k, \forall n \geqslant k p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>
