693
правки
Изменения
Нет описания правки
<tex>\Rightarrow</tex>
Пусть <tex>c_1, c_2, \ldots, c_k</tex> {{---}} коэффициенты, задающие линейную рекуррентную последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex>, то есть первые <tex>k-1</tex> членов заданы, а для следующих справедливо соотношение <tex>a_n = \sum\limits_{i = 1}^n k c_i \cdot a_{n - i}</tex>.
Напишем друг под другом несколько производящих функций и соответствующих им формальных степенных рядов:
<tex>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</tex>
Для всех <tex>n \geqslant k</tex> выполняется равенство <tex>a_n = \sum\limits_{i = 1}^n k c_i \cdot a_{n - i}</tex>, поэтому в правой части все коэффициенты при степенях, начиная с <tex>k</tex>, обнулятся, а равенство будет выглядеть следующим образом:
<tex>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}</tex>.
