Изменения

'''Рекуррентная формула''' (англ. ''recurrence relation'') — формула вида <tex>a_n=f(n, a_{n-1}, a_{n-2}, \dots, a_{n-p} ) </tex>, выражающая каждый следующий член последовательности <tex>a_n</tex> через <tex>p</tex> предыдущих членов и номер члена последовательности <tex>n</tex>, вместе с заданными первыми p членами, где <tex>p</tex> — порядок рекуррентного соотношения.

Пусть Для рекуррентного соотношения, которому удовлетворяет последовательность <tex>(a_0, a_1, a_2, … )\{ a_n \} </tex> удовлетворяет некоторому рекуррентному соотношению. Часто мы часто хотим получить выражение для <tex>a_n</tex> (при <tex>n\geqslant 0</tex>) в замкнутой форме (в виде конечного количества математических объектов), то есть решить рекуррентное соотношение. Например, для рекурсивной функциирекуррентного соотношения, описывающей сумму чисел натурального рядазадающего числа Фибоначчи:  

f F_0 = 0,\begin{cases} f(0)qquad F_1 =0; 1,\\ f(qquad F_{n) } = F_{n -1} + f(F_{n-1)2},\quad n \gt 0 geqslant 2, \quad n\end{cases}in Z</tex>

Для этого можно использовать [[Решение_рекуррентных_соотношений#Метод производящих функций | метод производящих функций]] (англ. ''generating Function Methodfunction method'').

Алгоритм получения замкнутого выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex> шагов.<ol><li>#Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>):<br>#:<tex>a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ … \\ a_{n} = …, n\geqslant k</tex></li> <li>#Домножить каждую строчку на <tex>z</tex> в соответствующей степени (<tex>z^{k} \cdot a_{k} = … \cdot z^{k}</tex>) и просуммировать строчки для всех сложить все выражения, многоточие надо рассматривать как множество из выражений, где <tex>n\geqslant0in [k, +\infty)</tex>.В левой части получится сумма </litex>\displaystyle\sum_{n=0}^{\infty} a_nz^n<li/tex>В полученном уравнении привести все суммы — это производящая функция, назовем ее <tex>&sum;G(z)</tex> к замкнутому виду. Получить уравнение для производящей функции.Правую часть преобразовать так, чтобы она превратилась в выражение, включающее <tex>G(z)</litex>.<li>Выразить #Решить полученное уравнение, получив для <tex>G(z)</tex> выражение в явном замкнутом виде .#Разложить <tex>G(решить уравнение, полученное на предыдущем шагеz) и разложить производящую функцию </tex> в степенной ряд по степеням , коэффициент при <tex>zz_n</tex>.будет искомым выражением для </litex>a_n</oltex>.

===<tex>1 </tex> пример===

z\cdot a_1&{}={}&01\cdot 1z,\\z^n\cdot a_n&{}={}&(5a_{n-1}-6a_{n-2})\cdot z^n, \quad n\geqslant2.\\

z\biggr( \underbrace{ z\displaystyle\sum_{n=1}^{\infty}a_{n}z^n+a_0}_{G(z)} - a_0\biggr)=z(G(z)-a_0)\stackrel{(4)}{=}zGz G(z).

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

====<tex>2 </tex> пример: числа Фибоначчи====

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, \\

Данное выражение можно упростить, если обратить внимание на то, что <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> в предыдущее выражение:

===<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> Приведём суммы к замкнутому виду:<br><tex>\begin{array}{ll}A(z) = \displaystyle\sum_{n=0}^{\infty}a_nz^n = 1 + z + 4z^2 + \displaystyle\sum_{n=3}^{\infty}(2a_{n-1} + 2a_{n-2} - a_{n-3})z^n, \\A(z) = 1 + z + 4z^2 + 2\displaystyle\sum_{n=3}^{\infty}a_{n-1}z^n + 2\displaystyle\sum_{n=3}^{\infty}a_{n-2}z^n - \displaystyle\sum_{n=3}^{\infty}a_{n-3}z^n, \\A(z) = 1 + z + 4z^2 + 2z\displaystyle\sum_{n=2}^{\infty}a_nz^n + 2z^2\displaystyle\sum_{n=1}^{\infty}a_nz^n - z^3\displaystyle\sum_{n=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), \\A(z)(1 - 2z - 2z^2 + z^3) = 1 + z + 4z^2 - 2z - 2z^2 - 2z^2 = 1 - z, \\\end{array}</tex><br>откуда получаем замкнутое выражение для производящей функции:<br><tex>G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.</tex><br> ===<tex>4</tex> пример====

a_n&{}={}&6a_{n-1}-8f_8a_{n-2}+n, \quad n\geqslant2.\\