|
|
| (не показано 58 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | Примечание: в редактируемой статье указано, что достаточно рассматривать <tex>q_0=1</tex>. :)
| |
| | | | |
| − | == Теорема о связи этих понятий ==
| |
| − |
| |
| − | {{Теорема
| |
| − | |id=th_main.
| |
| − | |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) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_k \cdot t^k + \ldots + a_n \cdot t^n + \ldots</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 - \ldots - c_1 \cdot a_{k - 1} \cdot t^k - \ldots - c_1 \cdot a_{n - 1} \cdot t^n - \ldots</tex>
| |
| − |
| |
| − | <tex>-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</tex>
| |
| − |
| |
| − | <tex>\cdots</tex>
| |
| − |
| |
| − | <tex>-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</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>\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 - \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>.
| |
| − |
| |
| − | Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - 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 + \ldots + (a_{k - 1} - \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) = 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)</tex> через <tex>A(t)</tex> и <tex>Q(t)</tex>: <tex>P(t) = A(t) \cdot Q(t)</tex>.
| |
| − |
| |
| − | Так как <tex>deg(P) < k</tex>, выполнено <tex>p_n = 0</tex> для <tex>\forall n \geqslant k </tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul|произведения степенных рядов]], получаем <tex>p_n = \sum\limits_{i = 0}^n a_{n-i} \cdot q_{i} = 0</tex>
| |
| − |
| |
| − | Разобьём полученную сумму на две: <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>deg(Q) = k</tex>. Тогда <tex>p_n = \sum\limits_{i = 0}^k a_{n-i} \cdot q_{i} = 0</tex>.
| |
| − |
| |
| − | Развернём выражение для <tex>p_n</tex>:
| |
| − |
| |
| − | <tex> \sum\limits_{i = 0}^k = a_{n-i} \cdot q_{i} = a_n \cdot q_0 + a_{n-1} \cdot q_1 + \ldots + a_{n-k} \cdot q_k = 0</tex>.
| |
| − |
| |
| − | Перенесём все слагаемые, кроме <tex>a_n \ldots q_0</tex>, вправо и поделим обе части на <tex>-1</tex>:
| |
| − |
| |
| − | <tex> a_n = a_{n-1} \cdot (-q_1) + \ldots + a_{n-k} \cdot (-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>
| |
| − | }}
| |
