Определения
| Определение: |
| Рекуррентная формула (англ. 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]. |
Во многих задачах полезно знать, есть ли у рекурсивной функции нерекурсивная или как еще говорят замкнутая форма (англ. Closed-form), то есть получение [math]f(n)[/math] в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:
[math] f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n \gt 0 \end{cases}[/math]
может быть переведена в замкнутую форму: [math]f = \dfrac{n(n+1)}{2}[/math]. Для этого можно использовать метод производящих функций (англ. Generating Function Method).
Общая схема
Пусть последовательность [math](a_0, a_1, a_2, … )[/math] удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для [math]a_n[/math] (при [math]n\geq 0[/math]) в замкнутом виде (если это возможно). Производящие функции позволяют делать эту работу почти механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.
Задано линейное однородное рекуррентное соотношение порядка [math]2[/math] с постоянными коэффициентами:
[math]\begin{array}{rcl}
a_0&{}={}&0,\\
a_1&{}={}&1,\\
a_n&{}={}&5a_{n-1}-6a_{n-2}, \quad n\geq2.\\
\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&{}={}&0\cdot 1,\\
z^n\cdot a_n&{}={}&5a_{n-1}-6a_{n-2}\cdot z^n, \quad n\geq2.\\
\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{ z\displaystyle\sum_{n=1}^{\infty}a_{n}z^n+a_0}_{G(z)} - a_0\biggr)\stackrel{(4)}{=}zG(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\geq 0[/math]).
Шаблон:Метод
Примеры
Числа Фибоначчи
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
[math]\begin{array}{rcl}
f_0&{}={}&0,\\
f_1&{}={}&1,\\
f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2.\\
\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\geq2.\\
\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 + \displaystyle\sum_{n=2}^{\infty}f_{n-1}z^{n-1}+\displaystyle\sum_{n=2}^{\infty}f_{n-2}z^{n-2}, \\
G(z) &{}={}& z + \displaystyle\sum_{n=1}^{\infty}f_{n}z^n+\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]
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]\begin{array}{rcl}
a_0&{}={}&1,\\
a_1&{}={}&2,\\
a_n&{}={}&6a_{n-1}-8f_{n-2}+n, \quad n\geq2.\\
\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]
См. также
Источники информации
