Решение рекуррентных соотношений

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

Общая схема

Пусть последовательность (a0, a1, a2, ...) удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для an (при n≥0) в замкнутом виде (если это возможно). Производящие функции позволяют делать эту работу почти механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.

Задано линейное однородное рекуррентное соотношение порядка 2 с постоянными коэффициентами:

\begin{displaymath}\begin{array}{rcl}
a_0&{}={}&0,\\
a_1&{}={}&1,\\
a_n&{}={}&5a_{n-1}-6a_{n-2}, \quad n\geq2.\\
\end{array}
\end{displaymath}

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

Попытаемся для начала «угадать» ответ:

\begin{displaymath}
\begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert c...
...
$a_n$ & 0 & 1 & 5 & 19 & 65 \\
\hline
\end{tabular}
\end{displaymath}

по данной таблице трудно что-либо сказать сразу, если вы, конечно, не видели этой последовательности раньше и не обладаете достаточным опытом разгадывания такого рода комбинаций. Значит самое время воспользоваться техникой производящий функций.

Будем искать производящую функцию последовательности в виде

\begin{displaymath}
G(z)=\sum_{n=0}^{\infty} a_nz^n = a_0+a_1z+a_2z^2+\cdots,
\end{displaymath}

с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на z0, следующую — на z1 и последнюю — на zn:

\begin{displaymath}\begin{array}{rcl}
1\cdot a_0&{}={}&0\cdot 1,\\
z\cdot a...
...(5a_{n-1}-6a_{n-2})\cdot z^n, \quad n\geq2.\\
\end{array}
\end{displaymath}

Теперь сложим все уравнения для всех значений n:

\begin{displaymath}
\underbrace{a_0 + a_1 z + \sum_{n=2}^{\infty}a_nz^n}_{g(z)...
...sum_{n=2}^{\infty}a_{n-1}z^n-6\sum_{n=2}^{\infty}a_{n-2}z^n.
\end{displaymath}

Левая часть уравнения в точности равна G(z), а в правой части есть суммы, очень похожие на функцию G(z), но не равные ей. Эти суммы нужно любым законным способом (используя правила работы с алгебраическими выражениями) привести к виду G(z). Начнём с первой:

\begin{displaymath}
\sum_{n=2}^{\infty}a_{n-1}z^n \stackrel{(1)}{=}
z\sum_{...
..._{n}z^{n}+a_0}_{g(z)} - a_0\biggr)
\stackrel{(4)}{=}zg(z).
\end{displaymath}

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

Аналогичные манипуляции со второй суммой дают нам выражение

\begin{displaymath}
\sum_{n=2}^{\infty}a_{n-2}z^n = z^2\sum_{n=2}^{\infty}a_{n-2}z^{n-2}
= z^2\sum_{n=0}^{\infty}a_{n}z^{n}=z^2g(z).
\end{displaymath}

Теперь наше исходное уравнение для производящей функции принимает вид:

\begin{displaymath}
G(z) = z + 5zG(z) -6z^2G(z),
\end{displaymath}

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

\begin{displaymath}
G(z) = \frac{z}{1-5z+6z^2}.
\end{displaymath}

Отыскав производящую функцию в замкнутом виде, её нужно снова разложить в ряд. Это можно сделать разными способами, но самый простой из них — разбить всю дробь на простые дроби и применить формулу для разложения 1/(1-z). Итак, разложим знаменатель функции на множители:

\begin{displaymath}
G(z) = \frac{z}{1-5z+6z^2} = \frac{z}{(1-3z)(1-2z)}.
\end{displaymath}

Теперь разобьём дробь на сумму простых дробей:

\begin{displaymath}
\frac{z}{(1-3z)(1-2z)} = \frac{1}{1-3z} - \frac{1}{1-2z}.
\end{displaymath}

Вспомним разложение для простейшей рациональной функции:

\begin{displaymath}
\frac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
\end{displaymath}

Из этого разложения следует, что (см. также таблицу производящих функций)

\begin{displaymath}
\frac{1}{1-3z}= \sum_{n=0}^{\infty}(3z)^n \quad\mbox{ и }\quad \frac{1}{1-2z}= \sum_{n=0}^{\infty}(2z)^n.
\end{displaymath}

Таким образом,

\begin{displaymath}
G(z) = \sum_{n=0}^{\infty}3^nz^n - \sum_{n=0}^{\infty}2^nz^n = \sum_{n=0}^{\infty}(3^n-2^n)z^n.
\end{displaymath}

С другой стороны, мы искали G(z) в виде

\begin{displaymath}
G(z)=\sum_{n=0}^{\infty} a_nz^n,
\end{displaymath}

поэтому, в силу равенства рядов, an=3n-2n (для n≥0). Теперь скажите: как проверить правильность полученного ответа?

Алгоритм

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

  1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен k):
    \begin{displaymath}\begin{array}{rcl}
a_0&{}={}&...,\\
a_1&{}={}&...,\\
...
...={}&...,\\
a_n&{}={}&..., \quad n\geq k.\\
\end{array}
\end{displaymath}
  2. Домножить каждую строчку на z в соответствующей степени и просуммировать строчки для всех n≥0.
  3. В полученном уравнении привести все суммы к замкнутому виду. Получить уравнение для производящей функции.
  4. Выразить G(z) в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням z.

Числа Фибоначчи

Это классический пример, который приводят почти везде, где речь идет о решении рекуррентных соотношений. Рассмотрим рекуррентное соотношение для чисел Фибоначчи:

\begin{displaymath}\begin{array}{rcl}
f_0&{}={}&0,\\
f_1&{}={}&1,\\
f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2.\\
\end{array}
\end{displaymath}

Это хорошо известная последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

\begin{displaymath}
\begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert c...
...& 2 & 3 & 5 & 8 & 13 & 21 & 34 \\
\hline
\end{tabular}
\end{displaymath}

Эти числа очень быстро растут, например, f10=55, f20=6765, f30=832040, f100=354224848179261915075.

Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:

\begin{displaymath}\begin{array}{rcl}
1\cdot f_0&{}={}&0\cdot 1,\\
z\cdot f...
...}&(f_{n-1}+f_{n-2})\cdot z^n, \quad n\geq2.\\
\end{array}
\end{displaymath}

Складываем все строчки:

\begin{displaymath}
f_0 + f_1 z + \sum_{n=2}^{\infty}f_nz^n =
z + \sum_{n=2}^{\infty}f_{n-1}z^n+\sum_{n=2}^{\infty}f_{n-2}z^n.
\end{displaymath}

Третий шаг алгоритма требует привести все суммы к замкнутому виду:

\begin{displaymath}\begin{array}{rcl}
G(z) &{}={}& \displaystyle z + z\sum_{n=...
...z) &{}={}& \displaystyle z + zG(z)+z^2G(z),\\
\end{array}
\end{displaymath}

откуда получаем замкнутое выражение для производящей функции:

\begin{displaymath}
G(z) = \frac{z}{1-z-z^2}.
\end{displaymath}

Осталось «всего лишь» разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:

\begin{displaymath}\displaylines{
1-z-z^2 = 0 \cr
z_1=-\frac{1-\sqrt{5}}{2}, z_2=-\frac{1+\sqrt{5}}{2}.
}
\end{displaymath}

Таким образом (проверьте),

\begin{displaymath}
G(z) = \frac{z}{1-z-z^2}=\frac{-z}{(z_1-z)(z_2-z)}
=
\frac{z_1/(z_1-z_2)}{z_1-z} + \frac{z_2/(z_2-z_1)}{z_2-z}.
\end{displaymath}

Как теперь поступить с этими выражениями? Ведь пока нам известно разложение только одной рациональной функции:

\begin{displaymath}
\frac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
\end{displaymath}

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на z1:

\begin{displaymath}
\frac{z_1/(z_1-z_2)}{z_1-z} = \frac1{z_1-z_2}\frac{1}{1-\f...
...}} =
\frac1{z_1-z_2}\sum_{n=0}^{\infty}\frac{z^n}{z_1^n}.
\end{displaymath}

Аналогично (но с делением на z2) поступим со второй дробью:

\begin{displaymath}
\frac{z_2/(z_2-z_1)}{z_2-z} = \frac1{z_2-z_1}\frac1{1-\fra...
...}} =
\frac1{z_2-z_1}\sum_{n=0}^{\infty}\frac{z^n}{z_2^n}.
\end{displaymath}

Таким образом,

\begin{displaymath}
G(z)=\sum_{n=0}^{\infty} f_nz^n =
\sum_{n=0}^{\infty}\b...
...rac{1}{z_1^n} + \frac{1}{z_2-z_1}\frac{1}{z_2^n} \biggr)z^n,
\end{displaymath}

и, следовательно,

\begin{displaymath}
f_n = \frac1{z_1-z_2}\frac{1}{z_1^n} + \frac1{z_2-z_1}\frac{1}{z_2^n}.
\end{displaymath}

Данное выражение можно «причесать», если обратить внимание на то, что 1/z1=-z2, 1/z2=-z1 и z1-z2=√5 (корень из 5):

\begin{displaymath}
f_n=\frac{1}{\sqrt{5}}\left( \biggl( \frac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \frac{1-\sqrt{5}}{2} \biggr)^n \right).
\end{displaymath}

Если записывать формулу в терминах хорошо известного «золотого сечения»

\begin{displaymath}
\phi = \frac{1+\sqrt{5}}{2},
\end{displaymath}

то, обозначив $\hat{\phi}=1-\phi$, получим

\begin{displaymath}
f_n= \frac{1}{\sqrt{5}}\left( \phi^n - \hat\phi^n \right).
\end{displaymath}

Если «золотое сечение» не использовать, то лучше всего формула выглядит в следующем виде:

\begin{displaymath}
f_n = \frac1{2^n\sqrt{5}} \bigl( (1+\sqrt{5})^n - (1-\sqrt{5})^n \bigr),
\end{displaymath}

чего достаточно трудно было ожидать, глядя на красивое исходное рекуррентное соотношение.

Обязательно проверьте формулу хотя бы для n=0, 1, 2. Как изменится производящая функция и конечная формула, если положить f0=f1=1?

Более сложное соотношение

Рассмотрим довольно произвольное рекуррентное соотношение:

\begin{displaymath}\begin{array}{rcl}
a_0&{}={}&1,\\
a_1&{}={}&2,\\
a_n&{}={}&6a_{n-1}-8f_{n-2}+n, \quad n\geq2.\\
\end{array}
\end{displaymath}

Рассчитаем несколько первых элементов:

\begin{displaymath}
\begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert c...
...
$a_n$ & 1 & 2 & 6 & 23 & 94 \\
\hline
\end{tabular}
\end{displaymath}

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

\begin{displaymath}\begin{array}{rcl}
\displaystyle a_0 + a_1 z + \sum_{n=2}^{...
... 6zG(z)-8z^2G(z) + \sum_{n=2}^{\infty}nz^n.\\
\end{array}
\end{displaymath}

Пока непонятно, что делать с последней суммой. Как её «замкнуть»? На самом деле, очень просто, если вспомнить про производную (подробнее см. лекцию «Преобразование производящих функций: полиномиальный множитель и делитель»):

\begin{displaymath}
(z^n)' = nz^{n-1},
\end{displaymath}

поэтому

\begin{displaymath}
\sum_{n=2}^{\infty}nz^n=z\sum_{n=2}^{\infty}nz^{n-1}=
z\...
...2}^{\infty}(z^n)'=
z\biggl(\sum_{n=2}^{\infty}z^n\biggr)'.
\end{displaymath}

Обратите внимание, что мы вынесли производную за знак бесконечной суммы, не проверив, имеем ли мы на это право. Можно показать, что все сделано законно, но мы не будем этим заниматься сейчас. Последняя сумма может быть свёрнута:

\begin{displaymath}
\sum_{n=2}^{\infty}z^n=\sum_{n=0}^{\infty}z^n-1-z=\frac{1}{1-z}-1-z=\frac{z^2}{1-z}.
\end{displaymath}

Подставив свёрнутое выражение обратно, имеем,

\begin{displaymath}
z\biggl(\sum_{n=2}^{\infty}z^n\biggr)' = z \biggl(\frac{z^2}{1-z}\biggr)'=\frac{z^2(2-z)}{(1-z)^2}.
\end{displaymath}

Таким образом, наше последнее уравнение примет вид

\begin{displaymath}
G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \frac{z^2(2-z)}{(1-z)^2}.\\
\end{displaymath}

Это уравнение для производящей функции. Из него выражаем G(z):

\begin{displaymath}
G(z) = \frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}.
\end{displaymath}

Довольно страшное выражение, которое нам предстоит разложить в ряд, на самом деле только кажется таким. Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:

\begin{displaymath}
G(z) = \frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=
\frac...
...(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}.
\end{displaymath}

Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее (см. также «Расширенные биномиальные коэффициенты»):

\begin{displaymath}
\frac{1}{(1-z)^2} =
(1-z)^{-2} =
\sum_{n=0}^{\infty}\...
...}(-1)^n\binom{n+1}{1}(-z)^n =
\sum_{n=0}^{\infty}(n+1)z^n.
\end{displaymath}

Теперь соберём ответ:

\begin{displaymath}
G(z) = \frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z...
...=0}^{\infty}2^nz^n
+\frac{7}{18}\sum_{n=0}^{\infty}4^nz^n.
\end{displaymath}

Значит,

\begin{displaymath}
a_n=
\frac{n+1}{3}
+\frac{7}{9}
-\frac{2^n}{2}
+\frac{7\cdot4^n}{18}=
\frac{7\cdot4^n+6n+20}{18} - 2^{n-1}.
\end{displaymath}

Подстановка первых пяти значений совпадает с числами из таблицы, в которую мы их записали в начале.