Карлукова M32342 временная статья — различия между версиями
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 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> | + | |statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> является линейной рекуррентной последовательностью с <tex>k</tex> первыми заданными членами, определяемыми коэффициентами <tex>c_1, c_2, \ldots, c_k</tex> <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём представимой в виде <tex>A(t) = \dfrac{P(t)}{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>. |
|proof= | |proof= | ||
Строка 32: | Строка 32: | ||
<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>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)</tex>, а степень правой части не превосходит <tex>k-1</tex>. Получили требуемое построение. |
+ | <!----Значит, многочлены <tex>Q(t)</tex> и <tex>P(t)</tex> всегда могут быть найдены. Более того, многочлен в знаменателе после нашего построения всегда принимает вид <tex>Q(t)=1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex-----> | ||
<tex>\Leftarrow</tex> | <tex>\Leftarrow</tex> | ||
− | Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}</tex>, <tex> deg(Q) = k</tex>, <tex> deg(P) < k</tex>. | + | Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}</tex>, <tex> deg(Q) = k</tex>, <tex> deg(P) < k</tex>. (да, я подумаю, как красиво исправить <tex> deg(Q) = k</tex> на <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>. просто страшно сносить дальнейшие рассуждения, где используются <tex>q_i</tex> :( ... либо же буду рада любым идеям :3). |
Перепишем первое равенство, выразив <tex>P(t)</tex> через <tex>A(t)</tex> и <tex>Q(t)</tex>: <tex>P(t) = A(t) \cdot Q(t)</tex>. | Перепишем первое равенство, выразив <tex>P(t)</tex> через <tex>A(t)</tex> и <tex>Q(t)</tex>: <tex>P(t) = A(t) \cdot Q(t)</tex>. |
Версия 01:54, 27 мая 2020
Примечание: в редактируемой статье указано, что достаточно рассматривать . :)
Теорема о связи этих понятий
Теорема: |
Последовательность является линейной рекуррентной последовательностью с первыми заданными членами, определяемыми коэффициентами её производящая функция является дробно-рациональной, причём представимой в виде , где , . |
Доказательство: |
Пусть — коэффициенты, задающие линейную рекуррентную последовательность .Напишем друг под другом несколько производящих функций и соответствующих им формальных степенных рядов:
Сложим все равенства и получим
Для всех выполняется равенство , поэтому в правой части все коэффициенты при степенях, начиная с , обнулятся, а равенство будет выглядеть следующим образом:. Заметим, что второй множитель в левой части равен в точности , а степень правой части не превосходит . Получили требуемое построение.
Пусть , , . (да, я подумаю, как красиво исправить на . просто страшно сносить дальнейшие рассуждения, где используются :( ... либо же буду рада любым идеям :3).Перепишем первое равенство, выразив через и : .Так как произведения степенных рядов, получаем . , выполнено для любого . Расписывая по определениюРазобьём полученную сумму на две: . Вторая компонента равна нулю, поскольку . Тогда .Развернём выражение для :. Перенесём все слагаемые, кроме , вправо:Видим, что . — коэффициент линейной рекуррентной последовательности, где роли играют при каждом , причём это выполнено для всех , так как индекс , удовлетворяющий данному условию, выбирался произвольно. |