693
правки
Изменения
→Теорема о связи этих понятий
Разобьём полученную сумму на две: <tex>p_n = \sum\limits_{i = 0}^{k} a_{n-i}\cdot q_{i} + \sum\limits_{i = k+1}^n a_{n-i}\cdot q_{i}</tex>. Так как <tex> Q(t)</tex> известно, можем определить, чему равны эти суммы. Для первой выполняются равенства:
:<tex> q_0 = 1</tex>, :<tex> q_i = -c_i</tex> для всех <tex> i</tex> за исключением нуля.
Вторая же компонента равна нулю, поскольку <tex>deg(Q) = k</tex>. Тогда <tex>p_n = a_n + \sum\limits_{i = 1}^k a_{n-i} \cdot (-c_{i}) = a_n - \sum\limits_{i = 1}^k a_{n-i} \cdot c_{i} = 0</tex>.
Развернём выражение для <tex>p_n</tex>:
:<tex> a_n - \sum\limits_{i = 1}^k a_{n-i} \cdot c_{i} = a_n - a_{n-1} \cdot c_1 - \ldots - a_{n-k} \cdot c_k = 0</tex>.
Перенесём все слагаемые, кроме <tex>a_n</tex>, вправо:
:<tex> a_n = a_{n-1} \cdot c_1 + a_{n-2} \cdot c_2 + \ldots + a_{n-k} \cdot c_k</tex>.
Видим, что <tex>a_n</tex> {{---}} член линейной рекуррентной последовательности, заданной коэффициентами <tex>c_1, c_2, \ldots, c_k</tex>, причём это выполнено для всех <tex>n \geqslant k </tex>, так как индекс <tex>n</tex>, удовлетворяющий данному условию, выбирался произвольно.
