Карлукова M32342 временная статья — различия между версиями
Строка 5: | Строка 5: | ||
{{Теорема | {{Теорема | ||
|id=th_main. | |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> | + | |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= | |proof= | ||
Строка 26: | Строка 26: | ||
Сложим все равенства и получим | Сложим все равенства и получим | ||
− | <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>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 c_i \cdot a_{n - i}</tex>, поэтому в правой части все коэффициенты при степенях, начиная с <tex>k</tex>, обнулятся, а равенство будет выглядеть следующим образом: | Для всех <tex>n \geqslant k</tex> выполняется равенство <tex>a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, поэтому в правой части все коэффициенты при степенях, начиная с <tex>k</tex>, обнулятся, а равенство будет выглядеть следующим образом: |
Версия 23:17, 26 мая 2020
Примечание: в редактируемой статье указано, что достаточно рассматривать . :)
Теорема о связи этих понятий
Теорема: |
Последовательность является линейной рекуррентной последовательностью с первыми заданными членами её производящая функция является дробно-рациональной, причём представимой в виде , , . |
Доказательство: |
Пусть — коэффициенты, задающие линейную рекуррентную последовательность .Напишем друг под другом несколько производящих функций и соответствующих им формальных степенных рядов:
Сложим все равенства и получим
Для всех выполняется равенство , поэтому в правой части все коэффициенты при степенях, начиная с , обнулятся, а равенство будет выглядеть следующим образом:. Заметим, что второй множитель в левой части имеет степень , а степень правой части не превосходит . Значит, многочлены и всегда могут быть найдены. Более того, многочлен в знаменателе после нашего построения всегда принимает вид .
Пусть , , .Перепишем первое равенство, выразив через и : .Так как произведения степенных рядов, получаем , выполнено для любого . Расписывая по определениюРазобьём полученную сумму на две: . Вторая компонента равна нулю, поскольку . Тогда .Развернём выражение для :. Перенесём все слагаемые, кроме , вправо:Видим, что . — коэффициент линейной рекуррентной последовательности, где роли играют при каждом , причём это выполнено для всех , так как индекс , удовлетворяющий данному условию, выбирался произвольно. |