Изменения
Нет описания правки
{{Теорема
|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)}, deg(Q) = k, deg(P) < k</tex>
|proof=
<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.
Так как <tex>deg(P) < k</tex>, то для <tex>\forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</tex>
Тогда <tex>a_n \cdot q_0 + a_{n - 1} \cdot q_1 + \ldots + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + \ldots + a_{0} \cdot 0 = 0</tex> (так как <tex>deg(Q) = 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} + (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 - \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 - \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>a_0 = 1, a_n = k \cdot a_{n - 1}</tex>
*: Так как последовательность является линейно рекуррентной, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - k \cdot t</tex> (так как <tex>c_1 = k</tex>), а <tex>deg(P) < 21</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{C}{1 - k \cdot t}, C \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots </tex>, тогда <tex>a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots = \dfrac{C}{1 - k \cdot t}</tex>, следовательно <tex>(a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots a_n \cdot t^n + \ldots) \cdot (1 - k \cdot t) = C</tex>
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - k \cdot t}</tex>
*: Таким образом, <tex> 1 + k \cdot t + (k \cdot t)^2 + \ldots + (k \cdot t)^n + \ldots = \sum\limits_{n = 0}^{\infty}(k^n \cdot t)^n = \dfrac{1}{1 - k \cdot t}</tex>
*: Частным случаем этой формулы являются соотношения <tex>1 + t + t^2 + \ldots t^n + \cdots = \sum\limits_{n = 0}^{\infty}t^n =\dfrac{1}{1 - t}</tex> и <tex>1 - t + t^2 + \ldots (-1)^n \cdot t^n + \cdots = \sum\limits_{n = 0}^{\infty}(-1)^n \cdot t^n = \dfrac{1}{1 + t}</tex>
* Вычислим производящую функцию последовательности Фибоначчи <tex>f_0 = f_1 = 1, f_n = f_{n - 1} + f_{n - 2}</tex>
*: Так как последовательность является линейно рекуррентной, её производящая функция, согласно теореме, имеет вид <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>Q(t) = 1 - t - t^2</tex> (так как <tex>c_1 = c_2 = 1</tex>), а <tex>deg(P) < 32</tex>.
*: Будем искать производящую функцию в виде <tex>F(t) = \dfrac{B + At}{1 - t - t^2}, A, B \in \mathbb{R}</tex>
*: Пусть <tex>F(t) = f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots </tex>, тогда <tex>f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots = \dfrac{C}{1 - t - t^2}</tex>, следовательно <tex>(f_0 + f_1 \cdot t + f_2 \cdot t^2 + \ldots + f_n \cdot t^n + \ldots) \cdot (1 - t - t^2) = B + At</tex>
*: Пользуясь правилами перемножения формальных степенных рядов, получаем <tex>p_n = \sum\limits_{i = 0}^{n} f_i \cdot q_{n - i}</tex>, в частности, <tex>B = p_0 = f_0 \cdot q_0 = 1 \cdot 1 = 1</tex>, а <tex>A = p_1 = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 1 - 1 = 0</tex>
*: Таким образом, <tex>F(t) = \dfrac{1}{1 - t - t^2}</tex>
