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

Материал из Викиконспекты
Версия от 12:28, 1 июня 2020; I am dark black (обсуждение | вклад) (Вычисление коэффициентов ряда \dfrac{1}{(1-t)^2} с помощью теоремы о связи рекуррентности и рациональности)
Перейти к: навигация, поиск

Примечание: в редактируемой статье указано, что достаточно рассматривать [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]k-1[/math] членов заданы, а для следующих справедливо соотношение [math]a_n = \sum\limits_{i = 1}^k c_i \cdot a_{n - i}[/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}^k c_i \cdot a_{n - i}) \cdot t^n + \ldots[/math]

Для всех [math]n \geqslant k[/math] выполняется равенство [math]a_n = \sum\limits_{i = 1}^k 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]Q(t)[/math], а степень правой части не превосходит [math]k-1[/math]. Получили требуемое построение.

Замечание. Многочлен [math]P(t)[/math] можно найти по формуле [math]A(t) \cdot Q(t)[/math] как числитель получившейся дроби. К результату можно применить взятие его по модулю [math]t^k[/math]. Это действие не испортит многочлен, так как его степень строго меньше [math]k[/math]. При этом мы сократим число операций при вычислении [math]P(t)[/math], поскольку достаточно найти только [math]k[/math] первых членов результирующего ряда, а для этого можно обойтись только первыми [math]k[/math] слагаемыми степенных рядов, соответствующих производящей функции [math]A(t)[/math] и столькими же для [math]Q(t)[/math].

Итак, [math]P(t) = A(t) \cdot Q(t) \mathrm{\ mod\ } t^k[/math].

[math]\Leftarrow[/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]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] Q(t)[/math] известно, можем определить, чему равны эти суммы. Для первой выполняются равенства:

[math] q_0 = 1[/math],
[math] q_i = -c_i[/math] для всех [math] i[/math] за исключением нуля.

Вторая же компонента равна нулю, поскольку [math]deg(Q) = k[/math]. Тогда [math]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[/math].

Развернём выражение для [math]p_n[/math]:

[math] 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[/math].

Перенесём все слагаемые, кроме [math]a_n[/math], вправо:

[math] a_n = a_{n-1} \cdot c_1 + a_{n-2} \cdot c_2 + \ldots + a_{n-k} \cdot c_k[/math].
Видим, что [math]a_n[/math] — член линейной рекуррентной последовательности, заданной коэффициентами [math]c_1, c_2, \ldots, c_k[/math], причём это выполнено для всех [math]n \geqslant k [/math], так как индекс [math]n[/math], удовлетворяющий данному условию, выбирался произвольно.
[math]\triangleleft[/math]

Примеры

Представление в виде отношения многочленов производящей функции для последовательности чисел Фибоначчи

Введём обозначения:

[math]F(t)[/math] — производящая функция для чисел Фибоначчи,
[math]f_n = [t^n]F(t)[/math].

Последовательность задаётся следующим образом:

[math]f_0 = f_1 = 1[/math],
[math]f_n = f_{n-1} + f_{n-2},\ n \geq 2[/math].

Здесь [math]k=2[/math] и [math]c_1 = c_2 = 1[/math], следовательно [math]Q(t) = 1 - t - t^2[/math].

К числителю применим формулу [math]P(t) = F(t) \cdot Q(t) \mathrm{\ mod\ } t^2[/math]. Чтобы получить ответ, требуется всего лишь найти [math]p_0[/math] и [math]p_1[/math].

[math]p_0 = f_0 \cdot q_0 = 1 \cdot 1 = 1[/math],
[math]p_1 = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 0[/math].

Таким образом, [math]F(t) = \dfrac{1}{1 - t - t^2}[/math].

Вычисление коэффициентов ряда [math]\dfrac{1}{(1-t)^2}[/math] с помощью теоремы о связи рекуррентности и рациональности

Найдём коэффициенты ряда [math]\dfrac{1}{(1-t)^2}[/math] через построение рекуррентного соотношения.

Имеем

[math]P(t)=1[/math],
[math]Q(t)=(1-t)^2 = 1 - 2t + t^2[/math].

Второе равенство позволяет найти [math]k[/math] и коэффициенты [math]c_1, c_2 \ldots c_k[/math]. В нашем примере [math]k=2[/math], [math]c_1=2[/math], [math]c_2=-1[/math].

Зная, что [math]P(t)=A(t)\cdot Q(t) \mathrm{\ mod\ }t^2[/math], найдём первые два коэффициента ряда, соответствующего функции [math]A(t)[/math]. Подставим в равенство известные значения:

[math]1 = (a_0 + a_1t)\cdot(1 - 2t)[/math]. Отсюда [math]a_0=1[/math], [math]a_1=2[/math].

Итак, коэффициенты [math]A(t)[/math] задаются соотношением

[math]a_0=1[/math], [math]a_1=2[/math],
[math]a_n=2\cdot a_{n-1} - a_{n-2},\ n\geq 2[/math].

Известно, что [math]\dfrac{1}{(1-t)^2} = \sum\limits_{n=0}^{\infty}{(n+1)\cdot t^n}[/math]. Такой результат можно получить, например, продифференцировав ряд функции [math]\dfrac{1}{1-t}[/math]. Проверим, что нахождение рекуррентного соотношения для исходной дроби даёт такой же результат, то есть для всех [math]n[/math] выполняется [math]a_{n}=n+1[/math].

  • Для начальных значений равенства выполнены: [math]a_0=1=0+1[/math], [math]a_1=2=1+1[/math];
  • Будем считать предыдущие утверждения (не нравится мне это слово, выкладки тоже) базой индукции. То есть существует такое число [math]n\geq 1[/math], что до него проверяемая формула работала. Для следующего числа [math]n+1[/math] верно [math]a_{n+1}=2\cdot a_{n} - a_{n-1}[/math]. Предыдущие значения известны. Они подчинялись равенству [math]a_{n}=n+1[/math]. Раскроем формулу:
    [math]a_{n+1}=2\cdot a_{n} - a_{n-1} = 2\cdot (n+1) - n = 2\cdot n + 2 - n = n+2 = (n+1) + 1[/math].
Методом математической индукции показали, что нет такого [math]n[/math], на котором действие формулы [math]a_{n}=n+1[/math] заканчивается, и установили, что результаты нахождения коэффициентов [math]A(t)[/math] методами дифференцирования и выражения через рекуррентную связь совпали.