693
правки
Изменения
Нет описания правки
|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)}</tex>, <tex>deg(Q) = k</tex>, <tex>deg(P) < k</tex>
|proof=
<tex>\Rightarrow</tex>
Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</tex>
<tex>\Leftarrow</tex>
Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}</tex>, <tex> deg(Q) = k</tex>, <tex> deg(P) < k</tex>. Тогда имеем <tex>P(t) = A(t) \cdot Q(t)</tex>.
<!---- Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - q_1 \cdot t - q_2 \cdot t^2 - \ldots - q_k \cdot t^k</tex>. --->
Так как <tex>deg(P) < k</tex>, то для <tex>\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 q_{k+1} + a_{n - k - 2} \cdot q_{k+2} + \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>
}}
