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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показаны 22 промежуточные версии 5 участников)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|id=def_rational.  
 
|id=def_rational.  
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
+
 
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется '''дробно-рациональной'''(англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
+
|definition=[[Производящая функция#main|Производящая функция]] <tex>F(t)</tex> называется '''дробно-рациональной''' (англ. ''rational''), если она представима в виде отношения двух многочленов, то есть <tex>F(t) = \dfrac{P(t)}{Q(t)}</tex>, где <tex>P(t), Q(t)</tex> {{---}} многочлены конечной степени
 
}}
 
}}
  
Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. В таком случае необходимо разделить оба многочлена на <tex>t^k</tex>, чтобы <tex>q_0</tex> стало не равным нулю.
+
Отметим, что если <tex>p_0 = 0</tex> и <tex>q_0 = 0</tex>, то оба многочлена могут быть разделены на <tex>t</tex>. Разделим оба многочлена на <tex>t</tex>. Если после деления <tex>p_0</tex> и <tex>q_0</tex> остаются равными нулю, то разделим на <tex>t</tex> ещё раз. Делить будем до тех пор, пока <tex>q_0</tex> и <tex>p_0</tex> будут оставаться равными нулю.
  
Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex> невозможна, по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].
+
Ситуация, при которой <tex>q_0 = 0</tex>, а <tex>p_0 \neq 0</tex>, невозможна по [[Арифметические действия с формальными степенными рядами#div| правилам деления формальных степенных рядов]].
  
 
Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>
 
Остаётся ситуация, при которой <tex>q_0 \neq 0</tex>. Тогда необходимо разделить <tex>P(t), Q(t)</tex> на <tex>q_0</tex>, чтобы <tex>q_0</tex> стало равным <tex>1</tex>. В дальнейшем, без ограничения общности, полагаем <tex>q_0 = 1</tex>
Строка 15: Строка 15:
 
{{Определение
 
{{Определение
 
|id=def_linear.  
 
|id=def_linear.  
|neat = 1 - параметр нужен для того, чтобы определение не растягивалось на всю страницу(не обязательно)
+
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется '''линейной рекуррентной последовательностью''' (англ. ''constant-recursive sequence''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
|definition=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> называется '''заданной линейной рекуррентой''' (англ. ''constant-recursive''), если её члены <tex>a_0 \ldots a_{k - 1} </tex> заданы, а <tex>\forall n \geqslant k </tex> выполняется <tex> a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}</tex>
 
 
}}
 
}}
  
 +
== Условные обозначения ==
  
 +
В дальнейшем будем придерживаться следующих условных обозначений:
  
 +
Будем обозначать <tex>[t^n]X(t)</tex> коэффициент при <tex>t^n</tex> в <tex>X(t)</tex>
  
 +
<tex>[t^n]A(t) = a_n</tex>
  
 +
<tex>[t^n]Q(t) = q_n</tex>
  
 +
<tex>[t^n]P(t) = p_n</tex>
  
 +
<tex>[t^n]F(t) = f_n</tex>
  
 
== Теорема о связи этих понятий ==
 
== Теорема о связи этих понятий ==
Строка 30: Строка 36:
 
{{Теорема
 
{{Теорема
 
|id=th_main.
 
|id=th_main.
|statement=Последовательность <tex>a_0, a_1, \ldots, a_n, \ldots </tex> задана линейной рекуррентой с <tex>k</tex> первыми заданными членами <tex>\Leftrightarrow</tex> её производящая функция <tex>A(t)</tex> является дробно-рациональной, причём она представима в виде <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(P) < k</tex>
+
|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=
 
|proof=
  
<tex>\Leftarrow)</tex>. Пусть <tex>A(t) = \dfrac{P(t)}{Q(t)}, deg(Q) = k, deg(Q) < k</tex>. Тогда <tex>A(t) \cdot Q(t) = P(t)</tex>. Пусть <tex>Q(t)</tex> имеет вид <tex>Q(t) = 1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k</tex>.
+
<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>deg(P) < k, \forall n \geqslant k </tex> выполнено <tex>p_n = 0</tex>. Расписывая <tex>p_n</tex> по определению [[Арифметические действия с формальными степенными рядами#def_mul| произведения степенных рядов]], получаем <tex>\sum\limits_{i = 0}^n a_i \cdot q_{n - i} = 0</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>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>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>n \geqslant k</tex> выполняется равенство <tex>a_n = \sum\limits_{i = 1}^k c_i \cdot a_{n - i}</tex>, поэтому в правой части все коэффициенты при степенях, начиная с <tex>k</tex>, обнулятся, а равенство будет выглядеть следующим образом:
  
Тогда <tex>a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - 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>\Rightarrow)</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>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>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>-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>\Leftarrow</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>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>\cdots</tex>
+
Перепишем первое равенство, выразив <tex>P(t)</tex> через <tex>A(t)</tex> и <tex>Q(t)</tex>: <tex>P(t) = A(t) \cdot Q(t)</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>
+
Так как <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>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</tex>  
+
:<tex> q_0 = 1</tex>,
 +
:<tex> q_i = -c_i</tex> для всех <tex> i</tex> за исключением нуля.
  
Так как <tex>\forall n \geqslant k: a_n = \sum\limits_{i = 1}^n c_i \cdot a_{n - i}</tex>, то все коэффициенты старше <tex>k</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>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 - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>.
+
Развернём выражение для <tex>p_n</tex>:
  
Обозначим <tex>Q(t) = (1 - c_1 \cdot t - c_2 \cdot t^2 - \ldots - c_k \cdot t^k)</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>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 + \ldots + (a_k - \sum\limits_{i = 1}^{k - 1} c_i \cdot a_{k - 1 - i}) \cdot t^{k - 1}</tex>
+
Перенесём все слагаемые, кроме <tex>a_n</tex>, вправо:
  
Тогда <tex>A(t) \cdot Q(t) = P(t), deg(Q) = k, deg(P) < k</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>a_0 = 1, a_n = k \cdot a_{n - 1}</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(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},\ n \geq 2</tex>.
 +
 +
Здесь <tex>k=2</tex> и <tex>c_1 = c_2 = 1</tex>, следовательно <tex>Q(t) = 1 - t - 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>F(t) = \dfrac{1}{1 - t - t^2}</tex>.
 +
=== Вычисление коэффициентов ряда <tex>\dfrac{1}{(1-t)^2}</tex> с помощью теоремы о связи рекуррентности и рациональности ===
 +
<!---Известно, что <tex>\dfrac{1}{(1-t)^2} = \sum\limits_{n=0}^{\infty}{(n+1)\cdot t^n}</tex>.--->Найдём коэффициенты ряда <tex>\dfrac{1}{(1-t)^2}</tex> через построение рекуррентного соотношения.
 +
 +
Имеем
 +
:<tex>P(t)=1</tex>,
 +
:<tex>Q(t)=(1-t)^2 = 1 - 2t + t^2</tex>.
 +
Второе равенство позволяет найти <tex>k</tex> и коэффициенты <tex>c_1, c_2 \ldots c_k</tex>. В нашем примере <tex>k=2</tex>, <tex>c_1=2</tex>, <tex>c_2=-1</tex>.
 +
 +
Зная, что <tex>P(t)=A(t)\cdot Q(t) \mathrm{\ mod\ }t^2</tex>, найдём первые два коэффициента ряда, соответствующего функции <tex>A(t)</tex>. Подставим в равенство известные значения:
 +
:<tex>1 = (a_0 + a_1t)\cdot(1 - 2t)</tex>. Отсюда <tex>a_0=1</tex>, <tex>a_1=2</tex>.
 +
 +
Итак, коэффициенты <tex>A(t)</tex> задаются соотношением
 +
:<tex>a_0=1</tex>, <tex>a_1=2</tex>,
 +
:<tex>a_n=2\cdot a_{n-1} - a_{n-2},\ n\geqslant 2</tex>.
 +
 +
Известно, что <tex>\dfrac{1}{(1-t)^2} = \sum\limits_{n=0}^{\infty}{(n+1)\cdot t^n}</tex>. Такой результат можно получить, например, продифференцировав ряд функции <tex>\dfrac{1}{1-t}</tex>. Проверим, что нахождение рекуррентного соотношения для исходной дроби даёт такой же результат, то есть для всех <tex>n</tex> выполняется <tex>a_{n}=n+1</tex>.
 +
* Для начальных значений равенства выполнены: <tex>a_0=1=0+1</tex>, <tex>a_1=2=1+1</tex>;
 +
<!------*: Чтобы узнать, работает ли формула для <tex>n</tex>, больших <tex>2</tex> найдём <tex>a_2</tex>: <tex>a_2 = 2a_1 - a_0 = 2\cdot 2 - 1 = 3 = 2+1</tex>.-------->
 +
* Будем считать предыдущие равенства базой индукции. То есть существует такое число <tex>n\geqslant 1</tex>, что до него проверяемая формула работала. Для следующего числа <tex>n+1</tex> верно <tex>a_{n+1}=2\cdot a_{n} - a_{n-1}</tex>. Предыдущие значения известны. Они подчинялись равенству <tex>a_{n}=n+1</tex>. Раскроем формулу:
 +
*: <tex>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</tex>.
 +
: Методом математической индукции показали, что нет такого <tex>n</tex>, на котором действие формулы <tex>a_{n}=n+1</tex> заканчивается, и установили, что результаты нахождения коэффициентов <tex>A(t)</tex> методами дифференцирования и выражения через рекуррентную связь совпали.
 +
<!--------------
 
* Вычислим производящую функцию последовательности <tex>a_0 = 1, a_n = k \cdot a_{n - 1}</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) < 2</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) = \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>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>
Строка 81: Строка 155:
 
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
 
*: <tex> C = a_0 \cdot 1 = 1 \cdot 1 = 1</tex>
 
*: Следовательно, <tex> F(t) = \dfrac{1}{1 - k \cdot t}</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^n \cdot t^n = \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>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_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) < 3</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) = \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>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 = p_0 = f_0 \cdot q_0 = 1 \cdot 1 = 1</tex>, а <tex>A = p_1 = f_0 \cdot q_1 + f_1 \cdot q_0 = 1 \cdot (-1) + 1 \cdot 1 = 1 - 1 = 0</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>
+
*: Таким образом, <tex>F(t) = \dfrac{1}{1 - t - t^2}</tex>-------------------->
  
 
==См. также==
 
==См. также==
Строка 96: Строка 170:
  
 
== Источники информации ==
 
== Источники информации ==
С. А. Ландо {{---}} Лекции о производящих функциях, стр 24
+
* С. А. Ландо {{---}} Лекции о производящих функциях, стр 24
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Комбинаторика]]
 
[[Категория: Производящие функции]]
 
[[Категория: Производящие функции]]

Текущая версия на 19:23, 4 сентября 2022

Необходимые определения

Определение:
Производящая функция [math]F(t)[/math] называется дробно-рациональной (англ. rational), если она представима в виде отношения двух многочленов, то есть [math]F(t) = \dfrac{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[/math]. Если после деления [math]p_0[/math] и [math]q_0[/math] остаются равными нулю, то разделим на [math]t[/math] ещё раз. Делить будем до тех пор, пока [math]q_0[/math] и [math]p_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, \ldots, a_n, \ldots [/math] называется линейной рекуррентной последовательностью (англ. constant-recursive sequence), если её члены [math]a_0 \ldots a_{k - 1} [/math] заданы, а [math]\forall n \geqslant k [/math] выполняется [math] a_n = c_1 \cdot a_{n - 1} + \ldots + c_k \cdot a_{n - k}[/math]


Условные обозначения

В дальнейшем будем придерживаться следующих условных обозначений:

Будем обозначать [math][t^n]X(t)[/math] коэффициент при [math]t^n[/math] в [math]X(t)[/math]

[math][t^n]A(t) = a_n[/math]

[math][t^n]Q(t) = q_n[/math]

[math][t^n]P(t) = p_n[/math]

[math][t^n]F(t) = f_n[/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]a_0 = 1, a_n = k \cdot a_{n - 1}[/math]

Вычислим производящую функцию последовательности [math]a_0 = 1, a_n = k \cdot a_{n - 1}[/math]

  • Так как последовательность является линейно рекуррентной, её производящая функция, согласно теореме, имеет вид [math]F(t) = \dfrac{P(t)}{Q(t)}[/math], где [math]Q(t) = 1 - k \cdot t[/math] (так как [math]c_1 = k[/math]), а [math]deg(P) \lt 1[/math].
    Будем искать производящую функцию в виде [math]F(t) = \dfrac{C}{1 - k \cdot t}, C \in \mathbb{R}[/math]
    Пусть [math]F(t) = a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots [/math], тогда [math]a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots = \dfrac{C}{1 - k \cdot t}[/math], следовательно [math](a_0 + a_1 \cdot t + a_2 \cdot t^2 + \ldots a_n \cdot t^n + \ldots) \cdot (1 - k \cdot t) = C[/math]
    Пользуясь правилом перемножения формальных степенных рядов, получаем
    [math] C = a_0 \cdot 1 = 1 \cdot 1 = 1[/math]
    Следовательно, [math] F(t) = \dfrac{1}{1 - k \cdot t}[/math]
    Таким образом, [math] 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}[/math]
    Частным случаем этой формулы являются соотношения [math]1 + t + t^2 + \ldots t^n + \cdots = \sum\limits_{n = 0}^{\infty}t^n =\dfrac{1}{1 - t}[/math] и [math]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}[/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\geqslant 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\geqslant 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] методами дифференцирования и выражения через рекуррентную связь совпали.

См. также

Источники информации

  • С. А. Ландо — Лекции о производящих функциях, стр 24