Карлукова M32342 временная статья

Примечание: в редактируемой статье указано, что достаточно рассматривать [math]q_0=1[/math]. :)

Теорема о связи этих понятий

Теорема:

Последовательность [math]a_0, a_1, \ldots, a_n, \ldots [/math] является линейной рекуррентной последовательностью с [math]k[/math] первыми заданными членами, определяемыми коэффициентами [math]c_1, c_2, \ldots, c_k[/math] [math]\Leftrightarrow[/math] её производящая функция [math]A(t)[/math] является дробно-рациональной, причём представимой в виде [math]A(t) = \dfrac{P(t)}{Q(t)}[/math], [math]Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k[/math], [math]deg(P) \lt k[/math].

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]