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