|
|
| (не показано 20 промежуточных версий 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>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=
| |
| − |
| |
| − | <tex>\Rightarrow</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>.
| |
| − |
| |
| − | Напишем друг под другом несколько производящих функций и соответствующих им формальных степенных рядов:
| |
| − |
| |
| − | <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 +0-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}^k c_i \cdot a_{n - i}) \cdot t^n + \ldots</tex>
| |
| − |
| |
| − | Для всех <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>Q(t)</tex>, а степень правой части не превосходит <tex>k-1</tex>. Получили требуемое построение.
| |
| − |
| |
| − | '''Замечание.''' Многочлен <tex>P(t)</tex> можно найти по формуле <tex>A(t) \cdot Q(t)</tex> как числитель получившейся дроби. К результату можно применить взятие его по модулю <tex>t^k</tex>. Это действие не испортит многочлен, так как его степень строго меньше <tex>k</tex>. При этом мы сократим число операций при вычислении <tex>P(t)</tex>, поскольку достаточно найти только <tex>k</tex> первых членов результирующего ряда, а для этого можно обойтись только первыми <tex>k</tex> слагаемыми степенных рядов, соответствующих производящим функциям <tex>A(t)</tex> и <tex>Q(t)</tex>.
| |
| − | <!-------Для того чтобы сократить число операций, все действия могут быть выполнены по модулю <tex>t^k</tex>.-------->
| |
| − |
| |
| − | Итак, <tex>P(t) = A(t) \cdot Q(t) \mathrm{\ mod\ } t^k</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>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>. <!--------<tex> deg(Q) = 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>deg(P) < k</tex>, выполнено <tex>p_n = 0</tex> для любого <tex>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> Q(t)</tex> известно, можем определить, чему равны эти суммы. Для первой выполняются равенства:
| |
| − |
| |
| − | <tex> q_0 = 1</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}) = a_n - \sum\limits_{i = 1}^k a_{n-i} \cdot c_{i} = 0</tex>.
| |
| − |
| |
| − | Развернём выражение для <tex>p_n</tex>:
| |
| − |
| |
| − | <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 = a_{n-1} \cdot c_1 + a_{n-2} \cdot c_2 + \ldots + a_{n-k} \cdot c_k</tex>.
| |
| − |
| |
| − | Видим, что <tex>a_n</tex> {{---}} член линейной рекуррентной последовательности, заданной коэффициентами <tex>c_1, c_2, \ldots, c_k</tex>, причём это выполнено для всех <tex>n \geqslant k </tex>, так как индекс <tex>n</tex>, удовлетворяющий данному условию, выбирался произвольно.
| |
| − | }}
| |
| − |
| |
| − | == Примеры ==
| |
| − | === Представление в виде отношения многочленов производящей функции для последовательности чисел Фибоначчи ===
| |
| − |
| |
| − | Введём обозначения:
| |
| − |
| |
| − | <tex>F(t)</tex> {{---}} производящая функция для чисел Фибоначчи, <tex>f_n = [t^n]F(t)</tex>.
| |
| − |
| |
| − | Последовательность задаётся следующим образом:
| |
| − | <tex>f_0 = f_1 = 1</tex>,
| |
| − |
| |
| − | <tex>f_n = f_{n-1} + f_{n-2}</tex>, <tex>n \geq 2</tex>.
| |
| − |
| |
| − | Здесь <tex>k=2</tex> и <tex>c_1 = c_2 = 1</tex>, следовательно <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2</tex>. К числителю применим формулу <tex>P(t) = F(t) \cdot Q(t) \mathrm{mod} t^2</tex>. Чтобы получить ответ, требуется найти всего лишь <tex>p_0</tex> и <tex>p_1</tex>.
| |
| − |
| |
| − | <tex>p_0 = f_0 \cdot q_0 = 1 \cdot 1 = 1</tex>,
| |
| − | <tex>p_1 = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 0</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) < 1</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 \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) < 2</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 = f_0 \cdot q_0 = 1 \cdot 1 = 1</tex>, а <tex>A = 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>-------------------->
| |
