Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности

Определение:

Производящая функция [math]F(t)[/math] называется дробно-рациональной, если она представима в виде отношения двух многочленов, то есть [math]F(t) = \frac{P(t)}{Q(t)}[/math], где [math]P(t), Q(t)[/math] - многочлены конечной степени

Отметим, что если [math]p_0 = 0[/math] и [math]q_0 = 0[/math], то оба многочлена могут быть разделены на [math]t[/math]. В таком случае необходимо разделить оба многочлена на [math]t^k[/math], чтобы [math]q_0[/math] стало не равным нулю.

Ситуация, при которой [math]q_0 = 0[/math], а [math]p_0 \neq 0[/math] невозможна, по правилам деления формальных степенных рядов.

Остаётся ситуация, при которой [math]q_0 \neq 0[/math]. Тогда необходимо разделить [math]P(t), Q(t)[/math] на [math]q_0[/math], чтобы [math]q_0[/math] стало равным [math]1[/math]. В дальнейшем, без ограничения общности, полагаем [math]q_0 = 1[/math]

Определение:

Последовательность [math]a_0, a_1, ..., a_n, ... [/math] называется заданной линейной рекуррентой, если её члены [math]a_0 ... a_{k - 1} [/math] заданы, а [math]\forall n \geqslant k [/math] выполняется [math] a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}[/math]

Теорема:

[math]a_0, a_1, ..., a_n, ... [/math] задана линейной рекуррентой с [math]k[/math] первыми заданными членами [math]\Leftrightarrow[/math] её производящая функция [math]A(t)[/math] является дробно-рациональной, причём она представима в виде [math]A(t) = \frac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) \lt k[/math]

Доказательство:

[math]\triangleright[/math]

[math]\Leftarrow)[/math]. Пусть [math]A(t) = \frac{P(t)}{Q(t)}, deg Q(t) = k, deg P(t) \lt k[/math]. Тогда [math]A(t) \cdot Q(t) = P(t)[/math]. Пусть [math]Q(t)[/math] имеет вид [math]Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k[/math]. Так как [math]deg P(t) \lt k, \forall n \geqslant k p_n = 0[/math]. Расписывая [math]p_n[/math] по определению произведения степенных рядов, получаем [math]\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0[/math] Тогда [math]a_n \cdot q_0 + a_{n - 1} \cdot q_1 + ... + a_{n - k} \cdot q_k + a_{n - k - 1} \cdot 0 + a_{n - k - 2} \cdot 0 + ... + a_{0} \cdot 0 = 0[/math] (так как [math]deg Q(t) = k[/math]) Так как [math]q_0 = 1[/math], а [math]\forall i: 1 \leqslant i \leqslant k: q_i = -c_i[/math] [math]a_n - c_1 \cdot a_{n - 1} - ... -c_k \cdot a_{n - k} = 0[/math] Тогда [math]a_n = c_1 \cdot a_{n - 1} + ... + c_k \cdot a_{n - k}[/math] [math]\Rightarrow)[/math] Напишем друг под другом несколько производящих функций: [math]\:[/math] [math]A(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + ... + a_k \cdot t^k + ... + a_n \cdot t^n + ...[/math] [math]-c_1 \cdot t \cdot A(t) = 0 - c_1 \cdot a_0 \cdot t - c_1 \cdot a_1 \cdot t^2 - ... - c_1 \cdot a_{k - 1} \cdot t^k - ... - c_1 \cdot a_{n - 1} \cdot t^n - ...[/math] [math]-c_2 \cdot t^2 \cdot A(t) = 0 + 0 - c_2 \cdot a_0 \cdot t^2 - ... - c_2 \cdot a_{k - 2} \cdot t^k - ... - c_2 \cdot a_{n - 2} \cdot t^n - ...[/math] [math]\cdots[/math] [math]-c_k \cdot t^k \cdot A(t) = 0 + 0 + 0 + ... - c_k \cdot a_0 \cdot t^k - ... - c_k \cdot a_{n - k} \cdot t^n + ...[/math] Почленно складывая эти формальные степенные ряды, получаем [math]A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - 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 + \\ + ... + (a_k - \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 + ... + (a_n - \sum\limits_{i = 1}^n c_i \cdot a_{n - i}) \cdot t^n + ...[/math] Так как [math]\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}[/math], то все коэффициенты старше [math]k[/math]-ой степени включительно обнулятся. Тогда [math]A(t) \cdot (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - 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 + \\ + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}[/math]. Обозначим [math]Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - ... - c_k \cdot t^k)[/math], а [math]P(t) = 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 + ... + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}[/math] Тогда [math]A(t) \cdot Q(t) = P(t), deg Q(t) = k, deg P(t) \lt k[/math]

[math]\triangleleft[/math]