|
[math]\Rightarrow[/math]
Напишем друг под другом несколько производящих функций:
[math]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[/math]
[math]-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[/math]
[math]-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[/math]
[math]\cdots[/math]
[math]-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[/math]
Почленно складывая эти формальные степенные ряды, получаем
[math]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 - 1} - \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[/math]
Так как [math]\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}[/math], то все коэффициенты при степенях, начиная с [math]k[/math]-ой включительно, обнулятся.
Тогда [math]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 - 1} - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}[/math].
Обозначим [math]Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)[/math],
а [math]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 - 1} - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}[/math]
Тогда [math]A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) \lt k[/math]
[math]\Leftarrow[/math]
Пусть [math]A(t) = \dfrac{P(t)}{Q(t)}[/math], [math] deg(Q) = k[/math], [math] deg(P) \lt k[/math].
Перепишем первое равенство, выразив [math]P(t)[/math] через [math]A(t)[/math] и [math]Q(t)[/math]: [math]P(t) = A(t) \cdot Q(t)[/math].
Так как [math]deg(P) \lt k[/math], выполнено [math]p_n = 0[/math] для [math]\forall n \geqslant k [/math]. Расписывая [math]p_n[/math] по определению произведения степенных рядов, получаем [math]p_n = \sum\limits_{i = 0}^n a_{n-i} \cdot q_{i} = 0[/math]
Раскрывая сумму, получаем [math]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[/math]. ///// [math]deg(Q) = k[/math].
Так как [math]q_0 = 1[/math], а [math]q_i = -c_i[/math], то [math]a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0[/math]
Тогда [math]a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}[/math] | 