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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 10: Строка 10:
  
 
Остаётся ситуация, при которой <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>
 
Остаётся ситуация, при которой <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, ..., 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>F(t)</tex> является дробно-рациональной, причём она представима в виде <tex>F(t) = \frac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) < k</tex>
 +
|proof=доказательство (необязательно)
 +
}}

Версия 00:22, 3 марта 2018

Определение:
Производящая функция [math]F(t)[/math] называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть [math]F(t) = \frac{P(t)}{Q(t)}[/math], где [math]P(t), Q(t)[/math] - многочлены конечной степени


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

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

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


Определение:
Последовательность [math]a_0, a_1, ..., a_n, ... [/math] называется заданной линейной рекуррентой, если её члены [math]a_0 ... a_{k - 1} [/math] заданы, а [math]\forall n \geqslant k [/math] выполняется [math] a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}[/math]


Теорема:
[math]a_0, a_1, ..., a_n, ... [/math] задана линейной рекуррентой с [math]k[/math] первыми заданными членами [math]\Leftrightarrow[/math] её производящая функция [math]F(t)[/math] является дробно-рациональной, причём она представима в виде [math]F(t) = \frac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) \lt k[/math]
Доказательство:
[math]\triangleright[/math]
доказательство (необязательно)
[math]\triangleleft[/math]