1632
правки
Изменения
м
Во многих задачах полезно знать<tex>F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, есть ли у рекурсивной функции нерекурсивная или как еще говорят «замкнутая» форма\quad n\geqslant 2, т.е. получение <math>f(\quad n)\in Z</mathtex> в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:
может быть переведена в замкнутую форму: <math>f = \frac{n(n+1)}{2}</math>. Для этого можно использовать метод производящих функций(англ. ''generating function method'').
Данное выражение можно упростить, если обратить внимание на то, что <math>1/z_1=-z_2</math>, <math>1/z_2=-z_1</math> и <math>z_1-z_2=√5</math>Приведём суммы к замкнутому виду:<br><mathtex>f_n\begin{array}{ll}A(z) =\fracdisplaystyle\sum_{n=0}^{\infty}a_nz^n = 1+ z + 4z^2 + \displaystyle\sum_{n=3}^{\sqrtinfty}(2a_{5n-1}+ 2a_{n-2}- a_{n-3})z^n, \left\A( z) = 1 + z + 4z^2 + 2\biggl( displaystyle\sum_{n=3}^{\fracinfty}a_{n-1}z^n +2\sqrtdisplaystyle\sum_{5n=3}^{\infty}a_{n-2} z^n - \displaystyle\biggr)sum_{n=3}^{\infty}a_{n - 3}z^n, \biggl\A( z) = 1 + z + 4z^2 + 2z\displaystyle\sum_{n=2}^{\infty}a_nz^n + 2z^2\fracdisplaystyle\sum_{n=1}^{\infty}a_nz^n -z^3\sqrtdisplaystyle\sum_{5n=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), \\biggrA(z)(1 - 2z - 2z^2 + z^3)= 1 + z + 4z^n 2 - 2z - 2z^2 - 2z^2 = 1 - z, \\\rightend{array}</tex><br>откуда получаем замкнутое выражение для производящей функции:<br><tex>G(z)= \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.</mathtex><br>
rollbackEdits.php mass rollback
{{Определение
|definition=
'''Рекуррентная формула''' (англ. ''recurrence relation'') — формула вида <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>, вместе с заданными первыми p членами, где <tex>p</tex>— порядок рекуррентного соотношения.
}}
Для рекуррентного соотношения, которому удовлетворяет последовательность <tex> \{ a_n \} </tex> мы часто хотим получить выражение для <tex>a_n</tex>. Например, для рекуррентного соотношения, задающего числа Фибоначчи:
<mathtex> f a_n</tex> член может быть записан следующим образом: <tex>a_n= \begindfrac{1}{\sqrt{cases5} f}\left( \biggl(0)=0; \dfrac{1+\sqrt{5}}{2} \ f(nbiggr) = ^n + f- \biggl(n\dfrac{1-1\sqrt{5}}{2} \biggr),\quad ^n > 0 \end{cases}right).</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\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>.#Решить полученное уравнение, n≥kполучив для <tex>G(z)</mathtex>выражение в замкнутом виде.#Разложить <tex>G(z)</litex>в степенной ряд, коэффициент при <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>. Будем искать производящую функцию последовательности в виде<libr>Домножить каждую <tex>G(z)=\displaystyle\sum_{n=0}^{\infty} a_nz^n = a_0+a_1z+a_2z^2+\cdots,</tex><br> с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на <mathtex>z^0</mathtex>, следующую — на <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> Теперь сложим все уравнения для всех значений <mathtex>n≥0</mathtex>:<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.</litex><br> Левая часть уравнения в точности равна <litex>В полученном уравнениипривести все G(z)</tex>, а в правой части есть суммы , очень похожие на функцию <mathtex>∑G(z)</mathtex> , но не равные ей. Эти суммы нужно привести к замкнутому виду<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),</litex><br> откуда получаем производящую функцию последовательности в замкнутом виде:<libr>Выразить <mathtex>G(z)= \dfrac{z}{1-5z+6z^2}.</mathtex><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><mathtex>\dfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.</mathtex><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.</litex><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.</oltex><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><mathtex>\begin{array}{rcl}
f_0&{}={}&0,\\
f_1&{}={}&1,\\
f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2geqslant2.\\
\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\geq2geqslant2.\\
\end{array}
</mathtex><br>
Складываем все строчки:
<br><mathtex>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.</mathtex><br>
Третий шаг алгоритма требует привести все суммы к замкнутому виду:
<br><mathtex>\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}
</mathtex><br>
откуда получаем замкнутое выражение для производящей функции:
<br><mathtex>G(z) = \fracdfrac{z}{1-z-z^2}.</mathtex><br>
Осталось разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
<br><mathtex>\displaylines{
1-z-z^2 = 0 \cr
z_1=-\fracdfrac{1-\sqrt{5}}{2}, z_2=-\fracdfrac{1+\sqrt{5}}{2}.
}
</mathtex><br>
Таким образом,
<br><mathtex>G(z) = \fracdfrac{z}{1-z-z^2}=\fracdfrac{-z}{(z_1-z)(z_2-z)}
=
\fracdfrac{z_1/(z_1-z_2)}{z_1-z} + \fracdfrac{z_2/(z_2-z_1)}{z_2-z}.</mathtex><br>
Нам известно разложение следующей рациональной функции:
<br><mathtex>\fracdfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.</mathtex><br>
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <mathtex>z_1</mathtex>:<br><mathtex>\fracdfrac{z_1/(z_1-z_2)}{z_1-z} = \frac1dfrac1{z_1-z_2}\fracdfrac{1}{1-\fracdfrac{z}{z_1}} =\frac1dfrac1{z_1-z_2}\displaystyle\sum_{n=0}^{\infty}\fracdfrac{z^n}{z_1^n}.</mathtex><br>
Аналогично (но с делением на <mathtex>z_2</mathtex>) поступим со второй дробью:<br><mathtex>\fracdfrac{z_2/(z_2-z_1)}{z_2-z} = \frac1dfrac1{z_2-z_1}\frac1dfrac1{1-\fracdfrac{z}{z_2}} =\frac1dfrac1{z_2-z_1}\displaystyle\sum_{n=0}^{\infty}\fracdfrac{z^n}{z_2^n}.</mathtex><br>
Таким образом,
<br><mathtex>G(z)=\displaystyle\sum_{n=0}^{\infty} f_nz^n =\displaystyle\sum_{n=0}^{\infty}\biggr(\fracdfrac{1}{z_1-z_2}\fracdfrac{1}{z_1^n} + \fracdfrac{1}{z_2-z_1}\fracdfrac{1}{z_2^n} \biggr)z^n,</mathtex><br>
и, следовательно,
<br><mathtex>f_n = \frac1dfrac1{z_1-z_2}\fracdfrac{1}{z_1^n} + \frac1dfrac1{z_2-z_1}\fracdfrac{1}{z_2^n}.</mathtex><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>
====Произвольное соотношение=<tex>4</tex> пример===
Рассмотрим следующее рекуррентное соотношение:
<br><mathtex>\begin{array}{rcl}
a_0&{}={}&1,\\
a_1&{}={}&2,\\
a_n&{}={}&6a_{n-1}-8f_8a_{n-2}+n, \quad n\geq2geqslant2.\\
\end{array}
</mathtex><br>
Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:
<br><mathtex>\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}
</mathtex><br>
Вспомним, что
<br><mathtex>
(z^n)' = nz^{n-1},
</mathtex><br>
поэтому
<br><mathtex>\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)'.</mathtex><br>
Последняя сумма может быть свёрнута:
<br><mathtex>\displaystyle\sum_{n=2}^{\infty}z^n=\displaystyle\sum_{n=0}^{\infty}z^n-1-z=\fracdfrac{1}{1-z}-1-z=\fracdfrac{z^2}{1-z}.</mathtex><br>
Подставив свёрнутое выражение обратно, имеем,
<br><mathtex>z\biggl(\displaystyle\sum_{n=2}^{\infty}z^n\biggr)' = z \biggl(\fracdfrac{z^2}{1-z}\biggr)'=\fracdfrac{z^2(2-z)}{(1-z)^2}.</mathtex><br>
Таким образом, наше последнее уравнение примет вид
<br><mathtex>G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \fracdfrac{z^2(2-z)}{(1-z)^2}.\\</mathtex><br>
Это уравнение для производящей функции. Из него выражаем <mathtex>G(z)</mathtex>:<br><mathtex>G(z) = \fracdfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}.</mathtex><br>
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
<br><mathtex>G(z) = \fracdfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\fracdfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\fracdfrac{1/3}{(1-z)^2}+\fracdfrac{7/9}{1-z}-\fracdfrac{1/2}{1-2z}+\fracdfrac{7/18}{1-4z}.</mathtex><br>
Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
<br><mathtex>\fracdfrac{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.</mathtex><br>
Теперь соберём ответ:
<br><mathtex>G(z) = \fracdfrac{1/3}{(1-z)^2}+\fracdfrac{7/9}{1-z}-\fracdfrac{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+\fracdfrac{7}{18}\displaystyle\sum_{n=0}^{\infty}4^nz^n.</mathtex><br>
Значит,
<br><mathtex>
a_n=
\fracdfrac{n+1}{3}+\fracdfrac{7}{9}-\fracdfrac{2^n}{2}+\fracdfrac{7\cdot4^n}{18}=\fracdfrac{7\cdot4^n+6n+20}{18} - 2^{n-1}.</mathtex><br> ==См. также==* [[Производящая функция]]* [[Арифметические действия с формальными степенными рядами]] == Источники информации == * [http://www.genfunc.ru/theory/rsol/ Решение рекуррентных соотношений] [[Категория: Дискретная математика и алгоритмы]][[Категория: Производящая функция]]
