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

Определения

Определение:

Рекуррентная формула — формула вида [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].

Во многих задачах полезно знать, есть ли у рекурсивной функции нерекурсивная или как еще говорят «замкнутая» форма, т.е. получение [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 = \frac{n(n+1)}{2}[/math]. Для этого можно использовать метод производящих функций.

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

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

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен [math]k[/math]):
   [math]a_{0} = ..., \\ a_{1} = ..., \\ a_{k-1} = ..., \\ a_{n} = ..., n≥k[/math]
2. Домножить каждую строчку на [math]z[/math] в соответствующей степени и просуммировать строчки для всех [math]n≥0[/math].
3. В полученном уравнениипривести все суммы [math]∑[/math] к замкнутому виду. Получить уравнение для производящей функции.
4. Выразить [math]G(z)[/math] в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням [math]z[/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{tabular}{\vert c\vert c\vert c\vert c\vert c\vert c... ...& 2 & 3 & 5 & 8 & 13 & 21 & 34 \\ \hline \end{tabular} [/math]
Эти числа очень быстро растут, например, f10=55, f20=6765, f30=832040, f100=354224848179261915075.

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

[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 + \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. [/math]
Третий шаг алгоритма требует привести все суммы к замкнутому виду:

[math]\begin{array}{rcl} G(z) &{}={}& \displaystyle z + z\sum_{n=z} &{}={}& \displaystyle z + zG(z)+z^2G(z),\\ \end{array} [/math]
откуда получаем замкнутое выражение для производящей функции:

[math] G(z) = \frac{z}{1-z-z^2}. [/math]
Осталось «всего лишь» разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:

[math]\displaylines{ 1-z-z^2 = 0 \cr z_1=-\frac{1-\sqrt{5}}{2}, z_2=-\frac{1+\sqrt{5}}{2}. } [/math]
Таким образом (проверьте),

[math] 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}. [/math]
Как теперь поступить с этими выражениями? Ведь пока нам известно разложение только одной рациональной функции:

[math] \frac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots. [/math]
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на z1:

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

[math] \frac{z_2/(z_2-z_1)}{z_2-z} = \frac1{z_2-z_1}\frac1{1-\frac{z}{z_2}} = \frac1{z_2-z_1}\sum_{n=0}^{\infty}\frac{z^n}{z_2^n}. [/math]
Таким образом,

[math] 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, [/math]
и, следовательно,

[math] f_n = \frac1{z_1-z_2}\frac{1}{z_1^n} + \frac1{z_2-z_1}\frac{1}{z_2^n}. [/math]
Данное выражение можно «причесать», если обратить внимание на то, что 1/z1=-z2, 1/z2=-z1 и z1-z2=√5 (корень из 5):

[math] f_n=\frac{1}{\sqrt{5}}\left( \biggl( \frac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \frac{1-\sqrt{5}}{2} \biggr)^n \right). [/math]