Карлукова M32342 временная статья — различия между версиями
(не показаны 3 промежуточные версии этого же участника) | |||
Строка 10: | Строка 10: | ||
<tex>\Rightarrow</tex> | <tex>\Rightarrow</tex> | ||
− | Пусть <tex>c_1, c_2, \ldots, c_k</tex> {{---}} коэффициенты, задающие линейную рекуррентную последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </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}^k c_i \cdot a_{n - i}</tex>. |
Напишем друг под другом несколько производящих функций и соответствующих им формальных степенных рядов: | Напишем друг под другом несколько производящих функций и соответствующих им формальных степенных рядов: | ||
Строка 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}^ | + | <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}^k c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex> |
− | Для всех <tex>n \geqslant k</tex> выполняется равенство <tex>a_n = \sum\limits_{i = 1}^ | + | Для всех <tex>n \geqslant k</tex> выполняется равенство <tex>a_n = \sum\limits_{i = 1}^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>. | <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>. | ||
Строка 49: | Строка 49: | ||
<tex> q_i = -c_i</tex> для всех <tex> i</tex> за исключением нуля. | <tex> q_i = -c_i</tex> для всех <tex> i</tex> за исключением нуля. | ||
− | Вторая же компонента равна нулю, поскольку <tex>deg(Q) = k</tex>. Тогда <tex>p_n = a_n + \sum\limits_{i = 1}^k a_{n-i} \cdot (-c_{i}) = 0</tex>. | + | Вторая же компонента равна нулю, поскольку <tex>deg(Q) = k</tex>. Тогда <tex>p_n = a_n + \sum\limits_{i = 1}^k a_{n-i} \cdot (-c_{i}) = a_n - \sum\limits_{i = 1}^k a_{n-i} \cdot c_{i} = 0</tex>. |
Развернём выражение для <tex>p_n</tex>: | Развернём выражение для <tex>p_n</tex>: | ||
− | <tex> a_n | + | <tex> a_n - \sum\limits_{i = 1}^k a_{n-i} \cdot c_{i} = a_n - a_{n-1} \cdot c_1 - \ldots - a_{n-k} \cdot c_k = 0</tex>. |
Перенесём все слагаемые, кроме <tex>a_n</tex>, вправо: | Перенесём все слагаемые, кроме <tex>a_n</tex>, вправо: |
Версия 22:38, 31 мая 2020
Примечание: в редактируемой статье указано, что достаточно рассматривать . :)
Теорема о связи этих понятий
Теорема: |
Последовательность является линейной рекуррентной последовательностью с первыми заданными членами, определяемыми коэффициентами её производящая функция является дробно-рациональной, причём представимой в виде , где , . |
Доказательство: |
Пусть — коэффициенты, задающие линейную рекуррентную последовательность , то есть первые членов заданы, а для следующих справедливо соотношение .Напишем друг под другом несколько производящих функций и соответствующих им формальных степенных рядов:
Сложим все равенства и получим
Для всех выполняется равенство , поэтому в правой части все коэффициенты при степенях, начиная с , обнулятся, а равенство будет выглядеть следующим образом:. Заметим, что второй множитель в левой части равен в точности , а степень правой части не превосходит . Получили требуемое построение.
Пусть , , .Перепишем первое равенство, выразив через и : .Так как произведения степенных рядов, получаем . , выполнено для любого . Расписывая по определениюРазобьём полученную сумму на две: . Так как известно, можем определить, чему равны эти суммы. Для первой выполняются равенства:, для всех за исключением нуля. Вторая же компонента равна нулю, поскольку . Тогда .Развернём выражение для :. Перенесём все слагаемые, кроме , вправо:Видим, что . — член линейной рекуррентной последовательности, заданной коэффициентами , причём это выполнено для всех , так как индекс , удовлетворяющий данному условию, выбирался произвольно. |