Решение рекуррентных соотношений — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «==Определения== {{Определение |definition= '''Рекуррентная формула''' — формула вида <math>a_n=f(n, a_{n-1}…»)
 
м (rollbackEdits.php mass rollback)
 
(не показана 71 промежуточная версия 6 участников)
Строка 2: Строка 2:
 
{{Определение  
 
{{Определение  
 
|definition=
 
|definition=
'''Рекуррентная формула''' — формула вида <math>a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) </math>, выражающая каждый член последовательности <math>a_n</math> через <math>p</math> предыдущих членов и возможно номер члена последовательности <math>n</math>.
+
'''Рекуррентная формула''' (англ. ''recurrence relation'') — формула вида <tex>a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) </tex>, выражающая каждый следующий член последовательности <tex>a_n</tex> через <tex>p</tex> предыдущих членов и номер члена последовательности <tex>n</tex>, вместе с заданными первыми p членами, где  <tex>p</tex> — порядок рекуррентного соотношения.
 
}}
 
}}
 +
Для рекуррентного соотношения, которому удовлетворяет последовательность <tex> \{ a_n \} </tex> мы часто хотим получить выражение для <tex>a_n</tex>. Например, для рекуррентного соотношения, задающего числа Фибоначчи:
  
Во многих задачах полезно знать, есть ли у рекурсивной функции нерекурсивная или как еще говорят «замкнутая» форма, т.е. получение <math>f(n)</math> в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:
+
<tex>
 +
F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2, \quad n\in Z</tex>
  
<math> f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n > 0 \end{cases}</math>
+
<tex>a_n</tex> член может быть записан следующим образом:  <tex>a_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).</tex>
  
может быть переведена в замкнутую форму: <math>f = \frac{n(n+1)}{2}</math>. Для этого можно использовать метод производящих функций.
+
Для этого можно использовать метод производящих функций (англ. ''generating function method'').
  
 
==Метод производящих функций==
 
==Метод производящих функций==
..алгоритм
+
Алгоритм получения выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex> шагов.
 +
#Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>):
 +
#:<tex>a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ … \\ a_{n} = …, n\geqslant k</tex>
 +
#Домножить каждую строчку на <tex>z</tex> в соответствующей степени (<tex>z^{k} \cdot a_{k} = … \cdot z^{k}</tex>) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где <tex>n \in [k, +\infty)</tex>. В левой части получится сумма <tex>\displaystyle\sum_{n=0}^{\infty} a_nz^n</tex> — это производящая функция, назовем ее <tex>G(z)</tex>. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее <tex>G(z)</tex>.
 +
#Решить полученное уравнение, получив для <tex>G(z)</tex> выражение в замкнутом виде.
 +
#Разложить <tex>G(z)</tex> в степенной ряд, коэффициент при <tex>z_n</tex> будет искомым выражением для <tex>a_n</tex>.
  
==Доказательство==
+
==Примеры==
по построению
+
===<tex>1</tex> пример===
 +
[[Производящая_функция| Производящие функции]] позволяют решать рекуррентные соотношение механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.
 +
 
 +
Задано линейное однородное рекуррентное соотношение порядка <tex>2</tex> с постоянными коэффициентами:
 +
<br><tex>\begin{array}{rcl}
 +
a_0&{}={}&0,\\
 +
a_1&{}={}&1,\\
 +
a_n&{}={}&5a_{n-1}-6a_{n-2}, \quad n\geqslant2.\\
 +
\end{array}
 +
</tex><br>
 +
 
 +
Порядок соотношения — это его «глубина», то есть количество предшествующих элементов, требуемых для вычисления элемента с номером <tex>n</tex>. В данном случае порядок равен <tex>2</tex>, так как для вычисления <tex>a_n</tex> требуется знать <tex>a_{n-1}</tex> и <tex>a_{n-2}</tex>.
 +
 
 +
Будем искать производящую функцию последовательности в виде
 +
<br><tex>
 +
G(z)=\displaystyle\sum_{n=0}^{\infty} a_nz^n = a_0+a_1z+a_2z^2+\cdots,
 +
</tex><br>
 +
 
 +
с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на <tex>z^0</tex>, следующую — на <tex>z^1</tex> и последнюю — на <tex>z^n</tex>:
 +
<br><tex>\begin{array}{rcl}
 +
1\cdot a_0&{}={}&0\cdot 1,\\
 +
z\cdot a_1&{}={}&1\cdot z,\\
 +
z^n\cdot a_n&{}={}&(5a_{n-1}-6a_{n-2})\cdot z^n, \quad n\geqslant2.\\
 +
\end{array}
 +
</tex><br>
 +
 
 +
Теперь сложим все уравнения для всех значений <tex>n</tex>:
 +
<br><tex>
 +
\underbrace{a_0 + a_1 z + \displaystyle\sum_{n=2}^{\infty}a_nz^n}_{G(z)} {=} z+5\displaystyle\sum_{n=2}^{\infty}a_{n-1}z^n-6\displaystyle\sum_{n=2}^{\infty}a_{n-2}z^n.
 +
</tex><br>
 +
 
 +
Левая часть уравнения в точности равна <tex>G(z)</tex>, а в правой части есть суммы, очень похожие на функцию <tex>G(z)</tex>, но не равные ей. Эти суммы нужно привести к виду <tex>G(z)</tex>. Начнём с первой:
 +
<br><tex>
 +
\displaystyle\sum_{n=2}^{\infty}a_{n-1}z^n \stackrel{(1)}{=}z\displaystyle\sum_{n=2}^{\infty}a_{n-1}z^{n-1} \stackrel{(2)}{=}
 +
z\displaystyle\sum_{n=1}^{\infty}a_{n}z^n \stackrel{(3)}{=}
 +
z\biggr( \underbrace{ \displaystyle\sum_{n=1}^{\infty}a_{n}z^n+a_0}_{G(z)} - a_0\biggr)=z(G(z)-a_0) \stackrel{(4)}{=} z G(z).
 +
</tex><br>
 +
 
 +
Равенство <tex>(1)</tex> получатся вынесением <tex>z</tex> в первой степени за знак суммы, это необходимо, чтобы уровнять степень переменной <tex>z</tex> и индекс переменной a внутри суммы. Действие <tex>(2)</tex> — изменение индекса суммирования, которое позволяет избавиться от <tex>n-1</tex>. Равенство <tex>(3)</tex> получается, если прибавить и снова отнять значение <tex>a_0</tex>, чтобы получить полную сумму от <tex>n=0</tex> до <tex>∞</tex>. Равенство <tex>(4)</tex> справедливо в силу того, что <tex>a_0=0</tex>.
 +
 
 +
Аналогичные манипуляции со второй суммой дают нам выражение
 +
<br><tex>
 +
\displaystyle\sum_{n=2}^{\infty}a_{n-2}z^n = z^2\displaystyle\sum_{n=2}^{\infty}a_{n-2}z^{n-2}
 +
= z^2\displaystyle\sum_{n=0}^{\infty}a_{n}z^{n}=z^2G(z).
 +
</tex><br>
 +
 
 +
Теперь наше исходное уравнение для производящей функции принимает вид:
 +
<br><tex>
 +
G(z) = z + 5zG(z) -6z^2G(z),
 +
</tex><br>
 +
 
 +
откуда получаем производящую функцию последовательности в замкнутом виде:
 +
<br><tex>
 +
G(z) = \dfrac{z}{1-5z+6z^2}.
 +
</tex><br>
 +
 
 +
Отыскав производящую функцию в замкнутом виде, её нужно снова разложить в ряд. Это можно сделать разными способами, но самый простой из них — разбить всю дробь на простые дроби и применить формулу для разложения <tex>\dfrac{1}{1-z}</tex>. Итак, разложим знаменатель функции на множители:
 +
<br><tex>
 +
G(z) = \dfrac{z}{1-5z+6z^2} = \dfrac{z}{(1-3z)(1-2z)}.
 +
</tex><br>
 +
 
 +
Теперь разобьём дробь на сумму простых дробей:
 +
<br><tex>
 +
\dfrac{z}{(1-3z)(1-2z)} = \dfrac{1}{1-3z} - \dfrac{1}{1-2z}.
 +
</tex><br>
 +
 
 +
Вспомним [[Производящая_функция#Приложения | разложение для простейшей рациональной функции]]:
 +
<br><tex>
 +
\dfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
 +
</tex><br>
 +
 
 +
Из этого разложения следует, что
 +
<br><tex>
 +
\dfrac{1}{1-3z}= \displaystyle\sum_{n=0}^{\infty}(3z)^n \quad\mbox{ и }\quad \dfrac{1}{1-2z}= \displaystyle\sum_{n=0}^{\infty}(2z)^n.
 +
</tex><br>
 +
 
 +
Таким образом,
 +
<br><tex>
 +
G(z) = \displaystyle\sum_{n=0}^{\infty}3^nz^n - \displaystyle\sum_{n=0}^{\infty}2^nz^n = \displaystyle\sum_{n=0}^{\infty}(3^n-2^n)z^n.
 +
</tex><br>
 +
 
 +
С другой стороны, мы искали <tex>G(z)</tex> в виде
 +
<br><tex>
 +
G(z)=\displaystyle\sum_{n=0}^{\infty} a_nz^n,
 +
</tex><br>
 +
поэтому, в силу равенства рядов, <tex>a_n=3^n-2^n</tex> (для <tex>n\geqslant 0</tex>).
 +
 
 +
===<tex>2</tex> пример: числа Фибоначчи===
 +
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
 +
<br><tex>\begin{array}{rcl}
 +
f_0&{}={}&0,\\
 +
f_1&{}={}&1,\\
 +
f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geqslant2.\\
 +
\end{array}
 +
</tex><br>
 +
 
 +
Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
 +
<br><tex>\begin{array}{rcl}
 +
1\cdot f_0&{}={}&0\cdot 1,\\
 +
z\cdot f_1&{}={}&1\cdot z,\\
 +
z^n\cdot f_n&{}={}&(f_{n-1}+f_{n-2})\cdot z^n, \quad n\geqslant2.\\
 +
\end{array}
 +
</tex><br>
 +
 
 +
Складываем все строчки:
 +
<br><tex>
 +
f_0 + f_1 z + \displaystyle\sum_{n=2}^{\infty}f_nz^n =
 +
z + \displaystyle\sum_{n=2}^{\infty}f_{n-1}z^n+\displaystyle\sum_{n=2}^{\infty}f_{n-2}z^n.
 +
</tex><br>
 +
 
 +
Третий шаг алгоритма требует привести все суммы к замкнутому виду:
 +
<br><tex>\begin{array}{rcl}
 +
G(z) &{}={}& z + z\displaystyle\sum_{n=2}^{\infty}f_{n-1}z^{n-1}+z^2\displaystyle\sum_{n=2}^{\infty}f_{n-2}z^{n-2}, \\
 +
G(z) &{}={}& z + z\displaystyle\sum_{n=1}^{\infty}f_{n}z^n+z^2\displaystyle\sum_{n=0}^{\infty}f_{n}z^n, \\
 +
G(z)&{}={}& \displaystyle z + z(G(z)-f_0)+z^2G(z),\\
 +
G(z)&{}={}& \displaystyle z + zG(z)+z^2G(z),\\
 +
\end{array}
 +
</tex><br>
 +
 
 +
откуда получаем замкнутое выражение для производящей функции:
 +
<br><tex>
 +
G(z) = \dfrac{z}{1-z-z^2}.
 +
</tex><br>
 +
 
 +
Осталось разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
 +
<br><tex>\displaylines{
 +
1-z-z^2 = 0 \cr
 +
z_1=-\dfrac{1-\sqrt{5}}{2}, z_2=-\dfrac{1+\sqrt{5}}{2}.
 +
}
 +
</tex><br>
 +
 
 +
Таким образом,
 +
<br><tex>
 +
G(z) = \dfrac{z}{1-z-z^2}=\dfrac{-z}{(z_1-z)(z_2-z)}
 +
=
 +
\dfrac{z_1/(z_1-z_2)}{z_1-z} + \dfrac{z_2/(z_2-z_1)}{z_2-z}.
 +
</tex><br>
 +
 
 +
Нам известно разложение следующей рациональной функции:
 +
<br><tex>
 +
\dfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
 +
</tex><br>
 +
 
 +
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <tex>z_1</tex>:
 +
<br><tex>
 +
\dfrac{z_1/(z_1-z_2)}{z_1-z} = \dfrac1{z_1-z_2}\dfrac{1}{1-\dfrac{z}{z_1}} =
 +
\dfrac1{z_1-z_2}\displaystyle\sum_{n=0}^{\infty}\dfrac{z^n}{z_1^n}.
 +
</tex><br>
 +
 
 +
Аналогично (но с делением на <tex>z_2</tex>) поступим со второй дробью:
 +
<br><tex>
 +
\dfrac{z_2/(z_2-z_1)}{z_2-z} = \dfrac1{z_2-z_1}\dfrac1{1-\dfrac{z}{z_2}} =
 +
\dfrac1{z_2-z_1}\displaystyle\sum_{n=0}^{\infty}\dfrac{z^n}{z_2^n}.
 +
</tex><br>
 +
 
 +
Таким образом,
 +
<br><tex>
 +
G(z)=\displaystyle\sum_{n=0}^{\infty} f_nz^n =
 +
\displaystyle\sum_{n=0}^{\infty}\biggr(\dfrac{1}{z_1-z_2}\dfrac{1}{z_1^n} + \dfrac{1}{z_2-z_1}\dfrac{1}{z_2^n} \biggr)z^n,
 +
</tex><br>
  
==Примеры==
+
и, следовательно,
 +
<br><tex>
 +
f_n = \dfrac1{z_1-z_2}\dfrac{1}{z_1^n} + \dfrac1{z_2-z_1}\dfrac{1}{z_2^n}.
 +
</tex><br>
 +
 
 +
Данное выражение можно упростить, если обратить внимание на то, что <tex>1/z_1=-z_2</tex>, <tex>1/z_2=-z_1</tex> и <tex>z_1-z_2=√5</tex>. Подставим <tex>z_1</tex> и <tex>z_2</tex> в предыдущее выражение:
 +
<br><tex>
 +
f_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).
 +
</tex><br>
 +
 
 +
===<tex>3</tex> пример===
 +
Найдём производящую функцию для последовательности квадратов чисел Фибоначчи: $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$.
 +
 
 +
По определению последовательности Фибоначчи выполняется:
 +
<br><tex>
 +
\left\{ \begin{array}{ll}
 +
f_{n+2} = f_{n+1} + f_n \\
 +
f_{n-1} = f_{n+1} - f_n
 +
  \end{array} \right.
 +
</tex><br>
 +
Возведя в квадрат и сложив, получим:
 +
<br><tex>
 +
\begin{array}{rcl}
 +
f_{n+2}^2 + f_{n-1}^2 = 2f_{n+1}^2 + 2f_n^2, \\
 +
f_{n+2}^2 = 2f_{n+1}^2 + 2f_n^2 - f_{n-1}^2, \\
 +
f_{n}^2 = 2f_{n-1}^2 + 2f_{n-2}^2 - f_{n-3}^2.\\
 +
\end{array}
 +
</tex><br>
 +
Обозначим рассматриваемую последовательность <tex>A</tex>, а её члены <tex>a_n</tex>, тогда:
 +
<br><tex>a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3}</tex><br>
 +
 
 +
Рекуррентное соотношение:
 +
<br><tex>
 +
\begin{array}{ll}
 +
a_0 = f_0^2 = 1 \\
 +
a_1 = f_1^2 = 1 \\
 +
a_2 = f_2^2 = 4 \\
 +
a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3}, \quad n\geqslant3.\\
 +
\end{array}
 +
</tex><br>
 +
 
 +
Приведём суммы к замкнутому виду:
 +
<br><tex>
 +
\begin{array}{ll}
 +
A(z) = \displaystyle\sum_{n=0}^{\infty}a_nz^n = 1 + z + 4z^2 + \displaystyle\sum_{n=3}^{\infty}(2a_{n-1} + 2a_{n-2} - a_{n-3})z^n, \\
 +
A(z) = 1 + z + 4z^2 + 2\displaystyle\sum_{n=3}^{\infty}a_{n-1}z^n + 2\displaystyle\sum_{n=3}^{\infty}a_{n-2}z^n - \displaystyle\sum_{n=3}^{\infty}a_{n-3}z^n, \\
 +
A(z) = 1 + z + 4z^2 + 2z\displaystyle\sum_{n=2}^{\infty}a_nz^n + 2z^2\displaystyle\sum_{n=1}^{\infty}a_nz^n - z^3\displaystyle\sum_{n=0}^{\infty}a_nz^n, \\
 +
A(z) = 1 + z + 4z^2 + 2z(A(z) - 1 - z) + 2z^2(A(z) - 1) - z^3A(z), \\
 +
A(z) = 1 + z + 4z^2 + 2zA(z) - 2z - 2z^2 + 2z^2A(z) - 2z^2 - z^3A(z), \\
 +
A(z)(1 - 2z - 2z^2 + z^3) = 1 + z + 4z^2 - 2z - 2z^2 - 2z^2 = 1 - z, \\
 +
\end{array}
 +
</tex><br>
 +
откуда получаем замкнутое выражение для производящей функции:
 +
<br><tex>G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.</tex><br>
 +
 
 +
===<tex>4</tex> пример===
 +
Рассмотрим следующее рекуррентное соотношение:
 +
<br><tex>\begin{array}{rcl}
 +
a_0&{}={}&1,\\
 +
a_1&{}={}&2,\\
 +
a_n&{}={}&6a_{n-1}-8a_{n-2}+n, \quad n\geqslant2.\\
 +
\end{array}
 +
</tex><br>
 +
 
 +
Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:
 +
<br><tex>\begin{array}{rcl}
 +
\displaystyle a_0 + a_1 z + \displaystyle\sum_{n=2}^{\infty}{a_n}{z^n} &{}={}& 1+2z+6\displaystyle\sum_{n=2}^{\infty}{a_{n-1}}{z^n}-8\displaystyle\sum_{n=2}^{\infty}{a_{n-2}}{z^n}+\displaystyle\sum_{n=2}^{\infty}nz^n, \\
 +
G(z) &{}={}& 1+2z+6z\displaystyle\sum_{n=2}^{\infty}{a_{n-1}}{z^{n-1}}-8z^2\displaystyle\sum_{n=2}^{\infty}{a_{n-2}}{z^{n-2}}+\displaystyle\sum_{n=2}^{\infty}nz^n, \\
 +
G(z) &{}={}& 1+2z+6z\displaystyle\sum_{n=1}^{\infty}{a_{n}}{z^{n}}-8z^2\displaystyle\sum_{n=0}^{\infty}{a_{n}}{z^{n}}+\displaystyle\sum_{n=2}^{\infty}nz^n, \\
 +
G(z) &{}={} & 1+ 2z + 6z(G(z)-a_0)-8z^2G(z) + \displaystyle\sum_{n=2}^{\infty}nz^n.\\
 +
G(z) &{}={} & 1 - 4z + 6zG(z)-8z^2G(z) + \displaystyle\sum_{n=2}^{\infty}nz^n.\\
 +
\end{array}
 +
</tex><br>
 +
 
 +
Вспомним, что
 +
<br><tex>
 +
(z^n)' = nz^{n-1},
 +
</tex><br>
 +
 
 +
поэтому
 +
<br><tex>
 +
\displaystyle\sum_{n=2}^{\infty}nz^n=z\displaystyle\sum_{n=2}^{\infty}nz^{n-1}=z\displaystyle\sum_{n=2}^{\infty}(z^n)'=z\biggl(\displaystyle\sum_{n=2}^{\infty}z^n\biggr)'.
 +
</tex><br>
 +
 
 +
Последняя сумма может быть свёрнута:
 +
<br><tex>
 +
\displaystyle\sum_{n=2}^{\infty}z^n=\displaystyle\sum_{n=0}^{\infty}z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}.
 +
</tex><br>
 +
 
 +
Подставив свёрнутое выражение обратно, имеем,
 +
<br><tex>
 +
z\biggl(\displaystyle\sum_{n=2}^{\infty}z^n\biggr)' = z \biggl(\dfrac{z^2}{1-z}\biggr)'=\dfrac{z^2(2-z)}{(1-z)^2}.
 +
</tex><br>
 +
 
 +
Таким образом, наше последнее уравнение примет вид
 +
<br><tex>
 +
G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \dfrac{z^2(2-z)}{(1-z)^2}.\\
 +
</tex><br>
 +
 
 +
Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:
 +
<br><tex>
 +
G(z) = \dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}.
 +
</tex><br>
 +
 
 +
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
 +
<br><tex>
 +
G(z) = \dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}.
 +
</tex><br>
 +
 
 +
Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
 +
<br><tex>
 +
\dfrac{1}{(1-z)^2} =(1-z)^{-2} =\displaystyle\sum_{n=0}^{\infty}\binom{-2}{n}(-z)^n=\displaystyle\sum_{n=0}^{\infty}(-1)^n\binom{n+1}{1}(-z)^n =\displaystyle\sum_{n=0}^{\infty}(n+1)z^n.
 +
</tex><br>
 +
 
 +
Теперь соберём ответ:
 +
<br><tex>
 +
G(z) = \dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=\dfrac{1}{3}\displaystyle\sum_{n=0}^{\infty}(n+1)z^n+
 +
\dfrac{7}{9}\displaystyle\sum_{n=0}^{\infty}z^n-\dfrac{1}{2}\displaystyle\sum_{n=0}^{\infty}2^nz^n+\dfrac{7}{18}\displaystyle\sum_{n=0}^{\infty}4^nz^n.
 +
</tex><br>
 +
 
 +
Значит,
 +
<br><tex>
 +
a_n=
 +
\dfrac{n+1}{3}
 +
+\dfrac{7}{9}
 +
-\dfrac{2^n}{2}
 +
+\dfrac{7\cdot4^n}{18}=
 +
\dfrac{7\cdot4^n+6n+20}{18} - 2^{n-1}.
 +
</tex><br>
 +
 
 +
 
 +
==См. также==
 +
* [[Производящая функция]]
 +
* [[Арифметические действия с формальными степенными рядами]]
 +
 
 +
== Источники информации ==
 +
* [http://www.genfunc.ru/theory/rsol/ Решение рекуррентных соотношений]
 +
 
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Производящая функция]]

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

Определения

Определение:
Рекуррентная формула (англ. recurrence relation) — формула вида [math]a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) [/math], выражающая каждый следующий член последовательности [math]a_n[/math] через [math]p[/math] предыдущих членов и номер члена последовательности [math]n[/math], вместе с заданными первыми p членами, где [math]p[/math] — порядок рекуррентного соотношения.

Для рекуррентного соотношения, которому удовлетворяет последовательность [math] \{ a_n \} [/math] мы часто хотим получить выражение для [math]a_n[/math]. Например, для рекуррентного соотношения, задающего числа Фибоначчи:

[math] F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2, \quad n\in Z[/math]

[math]a_n[/math] член может быть записан следующим образом: [math]a_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).[/math]

Для этого можно использовать метод производящих функций (англ. generating function method).

Метод производящих функций

Алгоритм получения выражения для чисел [math]a_{n}[/math], удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из [math]4[/math] шагов.

  1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен [math]k[/math]):
    [math]a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ … \\ a_{n} = …, n\geqslant k[/math]
  2. Домножить каждую строчку на [math]z[/math] в соответствующей степени ([math]z^{k} \cdot a_{k} = … \cdot z^{k}[/math]) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где [math]n \in [k, +\infty)[/math]. В левой части получится сумма [math]\displaystyle\sum_{n=0}^{\infty} a_nz^n[/math] — это производящая функция, назовем ее [math]G(z)[/math]. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее [math]G(z)[/math].
  3. Решить полученное уравнение, получив для [math]G(z)[/math] выражение в замкнутом виде.
  4. Разложить [math]G(z)[/math] в степенной ряд, коэффициент при [math]z_n[/math] будет искомым выражением для [math]a_n[/math].

Примеры

[math]1[/math] пример

Производящие функции позволяют решать рекуррентные соотношение механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.

Задано линейное однородное рекуррентное соотношение порядка [math]2[/math] с постоянными коэффициентами:
[math]\begin{array}{rcl} a_0&{}={}&0,\\ a_1&{}={}&1,\\ a_n&{}={}&5a_{n-1}-6a_{n-2}, \quad n\geqslant2.\\ \end{array} [/math]

Порядок соотношения — это его «глубина», то есть количество предшествующих элементов, требуемых для вычисления элемента с номером [math]n[/math]. В данном случае порядок равен [math]2[/math], так как для вычисления [math]a_n[/math] требуется знать [math]a_{n-1}[/math] и [math]a_{n-2}[/math].

Будем искать производящую функцию последовательности в виде
[math] G(z)=\displaystyle\sum_{n=0}^{\infty} a_nz^n = a_0+a_1z+a_2z^2+\cdots, [/math]

с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на [math]z^0[/math], следующую — на [math]z^1[/math] и последнюю — на [math]z^n[/math]:
[math]\begin{array}{rcl} 1\cdot a_0&{}={}&0\cdot 1,\\ z\cdot a_1&{}={}&1\cdot z,\\ z^n\cdot a_n&{}={}&(5a_{n-1}-6a_{n-2})\cdot z^n, \quad n\geqslant2.\\ \end{array} [/math]

Теперь сложим все уравнения для всех значений [math]n[/math]:
[math] \underbrace{a_0 + a_1 z + \displaystyle\sum_{n=2}^{\infty}a_nz^n}_{G(z)} {=} z+5\displaystyle\sum_{n=2}^{\infty}a_{n-1}z^n-6\displaystyle\sum_{n=2}^{\infty}a_{n-2}z^n. [/math]

Левая часть уравнения в точности равна [math]G(z)[/math], а в правой части есть суммы, очень похожие на функцию [math]G(z)[/math], но не равные ей. Эти суммы нужно привести к виду [math]G(z)[/math]. Начнём с первой:
[math] \displaystyle\sum_{n=2}^{\infty}a_{n-1}z^n \stackrel{(1)}{=}z\displaystyle\sum_{n=2}^{\infty}a_{n-1}z^{n-1} \stackrel{(2)}{=} z\displaystyle\sum_{n=1}^{\infty}a_{n}z^n \stackrel{(3)}{=} z\biggr( \underbrace{ \displaystyle\sum_{n=1}^{\infty}a_{n}z^n+a_0}_{G(z)} - a_0\biggr)=z(G(z)-a_0) \stackrel{(4)}{=} z G(z). [/math]

Равенство [math](1)[/math] получатся вынесением [math]z[/math] в первой степени за знак суммы, это необходимо, чтобы уровнять степень переменной [math]z[/math] и индекс переменной a внутри суммы. Действие [math](2)[/math] — изменение индекса суммирования, которое позволяет избавиться от [math]n-1[/math]. Равенство [math](3)[/math] получается, если прибавить и снова отнять значение [math]a_0[/math], чтобы получить полную сумму от [math]n=0[/math] до [math]∞[/math]. Равенство [math](4)[/math] справедливо в силу того, что [math]a_0=0[/math].

Аналогичные манипуляции со второй суммой дают нам выражение
[math] \displaystyle\sum_{n=2}^{\infty}a_{n-2}z^n = z^2\displaystyle\sum_{n=2}^{\infty}a_{n-2}z^{n-2} = z^2\displaystyle\sum_{n=0}^{\infty}a_{n}z^{n}=z^2G(z). [/math]

Теперь наше исходное уравнение для производящей функции принимает вид:
[math] G(z) = z + 5zG(z) -6z^2G(z), [/math]

откуда получаем производящую функцию последовательности в замкнутом виде:
[math] G(z) = \dfrac{z}{1-5z+6z^2}. [/math]

Отыскав производящую функцию в замкнутом виде, её нужно снова разложить в ряд. Это можно сделать разными способами, но самый простой из них — разбить всю дробь на простые дроби и применить формулу для разложения [math]\dfrac{1}{1-z}[/math]. Итак, разложим знаменатель функции на множители:
[math] G(z) = \dfrac{z}{1-5z+6z^2} = \dfrac{z}{(1-3z)(1-2z)}. [/math]

Теперь разобьём дробь на сумму простых дробей:
[math] \dfrac{z}{(1-3z)(1-2z)} = \dfrac{1}{1-3z} - \dfrac{1}{1-2z}. [/math]

Вспомним разложение для простейшей рациональной функции:
[math] \dfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots. [/math]

Из этого разложения следует, что
[math] \dfrac{1}{1-3z}= \displaystyle\sum_{n=0}^{\infty}(3z)^n \quad\mbox{ и }\quad \dfrac{1}{1-2z}= \displaystyle\sum_{n=0}^{\infty}(2z)^n. [/math]

Таким образом,
[math] G(z) = \displaystyle\sum_{n=0}^{\infty}3^nz^n - \displaystyle\sum_{n=0}^{\infty}2^nz^n = \displaystyle\sum_{n=0}^{\infty}(3^n-2^n)z^n. [/math]

С другой стороны, мы искали [math]G(z)[/math] в виде
[math] G(z)=\displaystyle\sum_{n=0}^{\infty} a_nz^n, [/math]
поэтому, в силу равенства рядов, [math]a_n=3^n-2^n[/math] (для [math]n\geqslant 0[/math]).

[math]2[/math] пример: числа Фибоначчи

Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
[math]\begin{array}{rcl} f_0&{}={}&0,\\ f_1&{}={}&1,\\ f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geqslant2.\\ \end{array} [/math]

Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
[math]\begin{array}{rcl} 1\cdot f_0&{}={}&0\cdot 1,\\ z\cdot f_1&{}={}&1\cdot z,\\ z^n\cdot f_n&{}={}&(f_{n-1}+f_{n-2})\cdot z^n, \quad n\geqslant2.\\ \end{array} [/math]

Складываем все строчки:
[math] f_0 + f_1 z + \displaystyle\sum_{n=2}^{\infty}f_nz^n = z + \displaystyle\sum_{n=2}^{\infty}f_{n-1}z^n+\displaystyle\sum_{n=2}^{\infty}f_{n-2}z^n. [/math]

Третий шаг алгоритма требует привести все суммы к замкнутому виду:
[math]\begin{array}{rcl} G(z) &{}={}& z + z\displaystyle\sum_{n=2}^{\infty}f_{n-1}z^{n-1}+z^2\displaystyle\sum_{n=2}^{\infty}f_{n-2}z^{n-2}, \\ G(z) &{}={}& z + z\displaystyle\sum_{n=1}^{\infty}f_{n}z^n+z^2\displaystyle\sum_{n=0}^{\infty}f_{n}z^n, \\ G(z)&{}={}& \displaystyle z + z(G(z)-f_0)+z^2G(z),\\ G(z)&{}={}& \displaystyle z + zG(z)+z^2G(z),\\ \end{array} [/math]

откуда получаем замкнутое выражение для производящей функции:
[math] G(z) = \dfrac{z}{1-z-z^2}. [/math]

Осталось разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
[math]\displaylines{ 1-z-z^2 = 0 \cr z_1=-\dfrac{1-\sqrt{5}}{2}, z_2=-\dfrac{1+\sqrt{5}}{2}. } [/math]

Таким образом,
[math] G(z) = \dfrac{z}{1-z-z^2}=\dfrac{-z}{(z_1-z)(z_2-z)} = \dfrac{z_1/(z_1-z_2)}{z_1-z} + \dfrac{z_2/(z_2-z_1)}{z_2-z}. [/math]

Нам известно разложение следующей рациональной функции:
[math] \dfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots. [/math]

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на [math]z_1[/math]:
[math] \dfrac{z_1/(z_1-z_2)}{z_1-z} = \dfrac1{z_1-z_2}\dfrac{1}{1-\dfrac{z}{z_1}} = \dfrac1{z_1-z_2}\displaystyle\sum_{n=0}^{\infty}\dfrac{z^n}{z_1^n}. [/math]

Аналогично (но с делением на [math]z_2[/math]) поступим со второй дробью:
[math] \dfrac{z_2/(z_2-z_1)}{z_2-z} = \dfrac1{z_2-z_1}\dfrac1{1-\dfrac{z}{z_2}} = \dfrac1{z_2-z_1}\displaystyle\sum_{n=0}^{\infty}\dfrac{z^n}{z_2^n}. [/math]

Таким образом,
[math] G(z)=\displaystyle\sum_{n=0}^{\infty} f_nz^n = \displaystyle\sum_{n=0}^{\infty}\biggr(\dfrac{1}{z_1-z_2}\dfrac{1}{z_1^n} + \dfrac{1}{z_2-z_1}\dfrac{1}{z_2^n} \biggr)z^n, [/math]

и, следовательно,
[math] f_n = \dfrac1{z_1-z_2}\dfrac{1}{z_1^n} + \dfrac1{z_2-z_1}\dfrac{1}{z_2^n}. [/math]

Данное выражение можно упростить, если обратить внимание на то, что [math]1/z_1=-z_2[/math], [math]1/z_2=-z_1[/math] и [math]z_1-z_2=√5[/math]. Подставим [math]z_1[/math] и [math]z_2[/math] в предыдущее выражение:
[math] f_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right). [/math]

[math]3[/math] пример

Найдём производящую функцию для последовательности квадратов чисел Фибоначчи: $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$.

По определению последовательности Фибоначчи выполняется:
[math] \left\{ \begin{array}{ll} f_{n+2} = f_{n+1} + f_n \\ f_{n-1} = f_{n+1} - f_n \end{array} \right. [/math]
Возведя в квадрат и сложив, получим:
[math] \begin{array}{rcl} f_{n+2}^2 + f_{n-1}^2 = 2f_{n+1}^2 + 2f_n^2, \\ f_{n+2}^2 = 2f_{n+1}^2 + 2f_n^2 - f_{n-1}^2, \\ f_{n}^2 = 2f_{n-1}^2 + 2f_{n-2}^2 - f_{n-3}^2.\\ \end{array} [/math]
Обозначим рассматриваемую последовательность [math]A[/math], а её члены [math]a_n[/math], тогда:
[math]a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3}[/math]

Рекуррентное соотношение:
[math] \begin{array}{ll} a_0 = f_0^2 = 1 \\ a_1 = f_1^2 = 1 \\ a_2 = f_2^2 = 4 \\ a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3}, \quad n\geqslant3.\\ \end{array} [/math]

Приведём суммы к замкнутому виду:
[math] \begin{array}{ll} A(z) = \displaystyle\sum_{n=0}^{\infty}a_nz^n = 1 + z + 4z^2 + \displaystyle\sum_{n=3}^{\infty}(2a_{n-1} + 2a_{n-2} - a_{n-3})z^n, \\ A(z) = 1 + z + 4z^2 + 2\displaystyle\sum_{n=3}^{\infty}a_{n-1}z^n + 2\displaystyle\sum_{n=3}^{\infty}a_{n-2}z^n - \displaystyle\sum_{n=3}^{\infty}a_{n-3}z^n, \\ A(z) = 1 + z + 4z^2 + 2z\displaystyle\sum_{n=2}^{\infty}a_nz^n + 2z^2\displaystyle\sum_{n=1}^{\infty}a_nz^n - z^3\displaystyle\sum_{n=0}^{\infty}a_nz^n, \\ A(z) = 1 + z + 4z^2 + 2z(A(z) - 1 - z) + 2z^2(A(z) - 1) - z^3A(z), \\ A(z) = 1 + z + 4z^2 + 2zA(z) - 2z - 2z^2 + 2z^2A(z) - 2z^2 - z^3A(z), \\ A(z)(1 - 2z - 2z^2 + z^3) = 1 + z + 4z^2 - 2z - 2z^2 - 2z^2 = 1 - z, \\ \end{array} [/math]
откуда получаем замкнутое выражение для производящей функции:
[math]G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.[/math]

[math]4[/math] пример

Рассмотрим следующее рекуррентное соотношение:
[math]\begin{array}{rcl} a_0&{}={}&1,\\ a_1&{}={}&2,\\ a_n&{}={}&6a_{n-1}-8a_{n-2}+n, \quad n\geqslant2.\\ \end{array} [/math]

Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:
[math]\begin{array}{rcl} \displaystyle a_0 + a_1 z + \displaystyle\sum_{n=2}^{\infty}{a_n}{z^n} &{}={}& 1+2z+6\displaystyle\sum_{n=2}^{\infty}{a_{n-1}}{z^n}-8\displaystyle\sum_{n=2}^{\infty}{a_{n-2}}{z^n}+\displaystyle\sum_{n=2}^{\infty}nz^n, \\ G(z) &{}={}& 1+2z+6z\displaystyle\sum_{n=2}^{\infty}{a_{n-1}}{z^{n-1}}-8z^2\displaystyle\sum_{n=2}^{\infty}{a_{n-2}}{z^{n-2}}+\displaystyle\sum_{n=2}^{\infty}nz^n, \\ G(z) &{}={}& 1+2z+6z\displaystyle\sum_{n=1}^{\infty}{a_{n}}{z^{n}}-8z^2\displaystyle\sum_{n=0}^{\infty}{a_{n}}{z^{n}}+\displaystyle\sum_{n=2}^{\infty}nz^n, \\ G(z) &{}={} & 1+ 2z + 6z(G(z)-a_0)-8z^2G(z) + \displaystyle\sum_{n=2}^{\infty}nz^n.\\ G(z) &{}={} & 1 - 4z + 6zG(z)-8z^2G(z) + \displaystyle\sum_{n=2}^{\infty}nz^n.\\ \end{array} [/math]

Вспомним, что
[math] (z^n)' = nz^{n-1}, [/math]

поэтому
[math] \displaystyle\sum_{n=2}^{\infty}nz^n=z\displaystyle\sum_{n=2}^{\infty}nz^{n-1}=z\displaystyle\sum_{n=2}^{\infty}(z^n)'=z\biggl(\displaystyle\sum_{n=2}^{\infty}z^n\biggr)'. [/math]

Последняя сумма может быть свёрнута:
[math] \displaystyle\sum_{n=2}^{\infty}z^n=\displaystyle\sum_{n=0}^{\infty}z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}. [/math]

Подставив свёрнутое выражение обратно, имеем,
[math] z\biggl(\displaystyle\sum_{n=2}^{\infty}z^n\biggr)' = z \biggl(\dfrac{z^2}{1-z}\biggr)'=\dfrac{z^2(2-z)}{(1-z)^2}. [/math]

Таким образом, наше последнее уравнение примет вид
[math] G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \dfrac{z^2(2-z)}{(1-z)^2}.\\ [/math]

Это уравнение для производящей функции. Из него выражаем [math]G(z)[/math]:
[math] G(z) = \dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}. [/math]

Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
[math] G(z) = \dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}. [/math]

Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
[math] \dfrac{1}{(1-z)^2} =(1-z)^{-2} =\displaystyle\sum_{n=0}^{\infty}\binom{-2}{n}(-z)^n=\displaystyle\sum_{n=0}^{\infty}(-1)^n\binom{n+1}{1}(-z)^n =\displaystyle\sum_{n=0}^{\infty}(n+1)z^n. [/math]

Теперь соберём ответ:
[math] G(z) = \dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=\dfrac{1}{3}\displaystyle\sum_{n=0}^{\infty}(n+1)z^n+ \dfrac{7}{9}\displaystyle\sum_{n=0}^{\infty}z^n-\dfrac{1}{2}\displaystyle\sum_{n=0}^{\infty}2^nz^n+\dfrac{7}{18}\displaystyle\sum_{n=0}^{\infty}4^nz^n. [/math]

Значит,
[math] a_n= \dfrac{n+1}{3} +\dfrac{7}{9} -\dfrac{2^n}{2} +\dfrac{7\cdot4^n}{18}= \dfrac{7\cdot4^n+6n+20}{18} - 2^{n-1}. [/math]


См. также

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