Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности — различия между версиями
(→Необходимые определения) |
|||
Строка 32: | Строка 32: | ||
Тогда <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_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>q_0 = 1</tex>, а <tex>q_i = -c_i</tex> | + | Так как <tex>q_0 = 1</tex>, а <tex>q_i = -c_i</tex>, то <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex> |
− | |||
− | <tex>a_n - c_1 \cdot a_{n - 1} - \ldots -c_k \cdot a_{n - k} = 0</tex> | ||
Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex> | Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex> | ||
Строка 41: | Строка 39: | ||
Напишем друг под другом несколько производящих функций: | Напишем друг под другом несколько производящих функций: | ||
− | |||
− | |||
<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>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> | ||
Строка 53: | Строка 49: | ||
<tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex> | <tex>-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + \ldots - c_k \cdot a_0 \cdot t^k - \ldots - c_k \cdot a_{n - k} \cdot t^n + \ldots</tex> | ||
− | |||
Почленно складывая эти формальные степенные ряды, получаем | Почленно складывая эти формальные степенные ряды, получаем |
Версия 19:49, 4 марта 2018
Необходимые определения
Определение:
Производящая функция называется дробно-рациональной(англ. rational), если она представима в виде отношения двух многочленов, то есть , где — многочлены конечной степени
Отметим, что если и , то оба многочлена могут быть разделены на . В таком случае необходимо разделить оба многочлена на , чтобы стало не равным нулю.
Ситуация, при которой правилам деления формальных степенных рядов.
, а невозможна, поОстаётся ситуация, при которой
. Тогда необходимо разделить на , чтобы стало равным . В дальнейшем, без ограничения общности, полагаем
Определение:
Последовательность
называется заданной линейной рекуррентой (англ. constant-recursive), если её члены заданы, а выполняется
Теорема о связи
Теорема: |
Последовательность задана линейной рекуррентой с первыми заданными членами её производящая функция является дробно-рациональной, причём она представима в виде |
Доказательство: |
. Пусть . Тогда . Пусть имеет вид . Так как произведения степенных рядов, получаем выполнено . Расписывая по определениюТогда (так как )Так как , а , тоТогда
Напишем друг под другом несколько производящих функций:
Почленно складывая эти формальные степенные ряды, получаем
Так как , то все коэффициенты старше -ой степени включительно обнулятся.Тогда .Обозначим ,а Тогда |
См. также
Источники информации
С. А. Ландо — Лекции о производящих функциях, стр 24