302
правки
Изменения
Нет описания правки
{{Определение
|definition=
'''Рекуррентная формула''' — формула вида <mathtex>a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) </mathtex>, выражающая каждый член последовательности <mathtex>a_n</mathtex> через <mathtex>p</mathtex> предыдущих членов и возможно номер члена последовательности <mathtex>n</mathtex>.
}}
Во многих задачах полезно знать, есть ли у рекурсивной функции нерекурсивная или как еще говорят «замкнутая» форма, т.е. получение <mathtex>f(n)</mathtex> в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:
<mathtex> f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n > 0 \end{cases}</mathtex>
может быть переведена в замкнутую форму: <mathtex>f = \frac{n(n+1)}{2}</mathtex>. Для этого можно использовать метод производящих функций.
==Метод производящих функций==
Алгоритм получения замкнутого выражения для чисел <mathtex>a_{n}</mathtex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4 </tex> шагов.
<ol>
<li>Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <mathtex>k</mathtex>):<br><mathtex>a_{0} = ...…, \\ a_{1} = ...…, \\ a_{k-1} = ...…, \\ a_{n} = ...…, n≥k\geqk</mathtex>
</li>
<li>Домножить каждую строчку на <mathtex>z</mathtex> в соответствующей степени и просуммировать строчки для всех <mathtex>n≥0\geq0</mathtex>.</li><li>В полученном уравнении привести все суммы <mathtex>∑</mathtex> к замкнутому виду. Получить уравнение для производящей функции.</li><li>Выразить <mathtex>G(z)</mathtex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <mathtex>z</mathtex>.</li>
</ol>
====Числа Фибоначчи====
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
<br><mathtex>\begin{array}{rcl}
f_0&{}={}&0,\\
f_1&{}={}&1,\\
f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2.\\
\end{array}
</mathtex><br>
Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
<br><mathtex>\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}
</mathtex><br>
Складываем все строчки:
<br><mathtex>
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.
</mathtex><br>
Третий шаг алгоритма требует привести все суммы к замкнутому виду:
<br><mathtex>\begin{array}{rcl}
G(z) &{}={}& z + \sum_{n=2}^{\infty}f_{n-1}z^{n-1}+\sum_{n=2}^{\infty}f_{n-2}z^{n-2}, \\
G(z) &{}={}& z + \sum_{n=1}^{\infty}f_{n}z^n+\sum_{n=0}^{\infty}f_{n}z^n, \\
G(z)&{}={}& \displaystyle z + zG(z)+z^2G(z),\\
\end{array}
</mathtex><br>
откуда получаем замкнутое выражение для производящей функции:
<br><mathtex>
G(z) = \frac{z}{1-z-z^2}.
</mathtex><br>
Осталось разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
<br><mathtex>\displaylines{
1-z-z^2 = 0 \cr
z_1=-\frac{1-\sqrt{5}}{2}, z_2=-\frac{1+\sqrt{5}}{2}.
}
</mathtex><br>
Таким образом,
<br><mathtex>
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}.
</mathtex><br>
Нам известно разложение следующей рациональной функции:
<br><mathtex>
\frac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
</mathtex><br>
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <mathtex>z_1</mathtex>:<br><mathtex>
\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}.
</mathtex><br>
Аналогично (но с делением на <mathtex>z_2</mathtex>) поступим со второй дробью:<br><mathtex>
\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}.
</mathtex><br>
Таким образом,
<br><mathtex>
G(z)=\sum_{n=0}^{\infty} f_nz^n =
\sum_{n=0}^{\infty}\biggr(\frac{1}{z_1-z_2}\frac{1}{z_1^n} + \frac{1}{z_2-z_1}\frac{1}{z_2^n} \biggr)z^n,
</mathtex><br>
и, следовательно,
<br><mathtex>
f_n = \frac1{z_1-z_2}\frac{1}{z_1^n} + \frac1{z_2-z_1}\frac{1}{z_2^n}.
</mathtex><br>
Данное выражение можно упростить, если обратить внимание на то, что <mathtex>1/z_1=-z_2</mathtex>, <mathtex>1/z_2=-z_1</mathtex> и <mathtex>z_1-z_2=√5</mathtex>:<br><mathtex>
f_n=\frac{1}{\sqrt{5}}\left( \biggl( \frac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \frac{1-\sqrt{5}}{2} \biggr)^n \right).
</mathtex><br>
====Произвольное соотношение====
Рассмотрим следующее рекуррентное соотношение:
<br><mathtex>\begin{array}{rcl}
a_0&{}={}&1,\\
a_1&{}={}&2,\\
a_n&{}={}&6a_{n-1}-8f_{n-2}+n, \quad n\geq2.\\
\end{array}
</mathtex><br>
Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:
<br><mathtex>\begin{array}{rcl}
\displaystyle a_0 + a_1 z + \sum_{n=2}^{\infty}{a_n}{z^n} &{}={}& 1+2z+6\sum_{n=2}^{\infty}{a_{n-1}}{z^n}-8\sum_{n=2}^{\infty}{a_{n-2}}{z^n}+\sum_{n=2}^{\infty}nz^n, \\
G(z) &{}={}& 1+2z+6z\sum_{n=2}^{\infty}{a_{n-1}}{z^{n-1}}-8z^2\sum_{n=2}^{\infty}{a_{n-2}}{z^{n-2}}+\sum_{n=2}^{\infty}nz^n, \\
G(z) &{}={} & 1 - 4z + 6zG(z)-8z^2G(z) + \sum_{n=2}^{\infty}nz^n.\\
\end{array}
</mathtex><br>
Вспомним, что
<br><mathtex>
(z^n)' = nz^{n-1},
</mathtex><br>
поэтому
<br><mathtex>
\sum_{n=2}^{\infty}nz^n=z\sum_{n=2}^{\infty}nz^{n-1}=z\sum_{n=2}^{\infty}(z^n)'=z\biggl(\sum_{n=2}^{\infty}z^n\biggr)'.
</mathtex><br>
Последняя сумма может быть свёрнута:
<br><mathtex>
\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}.
</mathtex><br>
Подставив свёрнутое выражение обратно, имеем,
<br><mathtex>
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}.
</mathtex><br>
Таким образом, наше последнее уравнение примет вид
<br><mathtex>
G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \frac{z^2(2-z)}{(1-z)^2}.\\
</mathtex><br>
Это уравнение для производящей функции. Из него выражаем <mathtex>G(z)</mathtex>:<br><mathtex>
G(z) = \frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}.
</mathtex><br>
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
<br><mathtex>
G(z) = \frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\frac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}.
</mathtex><br>
Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
<br><mathtex>
\frac{1}{(1-z)^2} =(1-z)^{-2} =\sum_{n=0}^{\infty}\binom{-2}{n}(-z)^n=\sum_{n=0}^{\infty}(-1)^n\binom{n+1}{1}(-z)^n =\sum_{n=0}^{\infty}(n+1)z^n.
</mathtex><br>
Теперь соберём ответ:
<br><mathtex>
G(z) = \frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}=\frac{1}{3}\sum_{n=0}^{\infty}(n+1)z^n+
\frac{7}{9}\sum_{n=0}^{\infty}z^n-\frac{1}{2}\sum_{n=0}^{\infty}2^nz^n+\frac{7}{18}\sum_{n=0}^{\infty}4^nz^n.
</mathtex><br>
Значит,
<br><mathtex>
a_n=
\frac{n+1}{3}
+\frac{7\cdot4^n}{18}=
\frac{7\cdot4^n+6n+20}{18} - 2^{n-1}.
</mathtex><br>
==См. также==
