Изменения

'''Рекуррентная формула''' (англ. ''Recurrence 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>F_0 = 0,\qquad F_1 = 1, есть ли у рекурсивной функции нерекурсивная или как еще говорят замкнутая форма (англ. ''Closed\qquad F_{n} = F_{n-1} + F_{n-form'')2}, то есть получение <tex>f(\quad n\geqslant 2, \quad n)\in Z</tex> в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:

<tex> f a_n</tex> член может быть записан следующим образом: <tex>a_n= \begindfrac{cases1}{\sqrt{5} f}\left(0)=0; \biggl( \dfrac{1+\sqrt{5}}{2} \ f(nbiggr) = n + f(^n-1),\quad n biggl( \gt 0 dfrac{1-\endsqrt{5}}{cases2}\biggr)^n \right).</tex>

может быть переведена в замкнутую форму: <tex>f = \dfrac{n(n+1)}{2}</tex>. Для этого можно использовать [[Решение_рекуррентных_соотношений#Метод производящих функций | метод производящих функций]] (англ. ''Generating Function Methodgenerating function method'').

==Общая схемаМетод производящих функций==Пусть последовательность Алгоритм получения выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex>шагов.#Записать рекуррентное соотношение и начальные данные для него в следующем виде (a_0если порядок соотношения равен <tex>k</tex>):#:<tex>a_{0} = …, a_1\\ a_{1} = …, a_2\\ a_{k-1} = …, \\ … \\ a_{n} = … ), n\geqslant k</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для #Домножить каждую строчку на <tex>a_nz</tex> в соответствующей степени (при <tex>z^{k} \cdot a_{k} = … \cdot z^{k}</tex>) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где <tex>n\geq in [k, +\infty)</tex>. В левой части получится сумма <tex>\displaystyle\sum_{n=0}^{\infty} a_nz^n</tex>— это производящая функция, назовем ее <tex>G(z) </tex>. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее <tex>G(z)</tex>.#Решить полученное уравнение, получив для <tex>G(z)</tex> выражение в замкнутом виде .#Разложить <tex>G(если это возможноz)</tex> в степенной ряд, коэффициент при <tex>z_n</tex> будет искомым выражением для <tex>a_n</tex>.  ==Примеры=====<tex>1</tex> пример===[[Производящая_функция| Производящие функции]] позволяют делать эту работу почти решать рекуррентные соотношение механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.

a_n&{}={}&5a_{n-1}-6a_{n-2}, \quad n\geq2geqslant2.\\

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

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

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>a_n=3^n-2^n</tex> (для <tex>n\geq geqslant 0</tex>). ==Метод производящих функций==Алгоритм получения замкнутого выражения для чисел <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\geq k</tex></li> <li>Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n\geq0</tex>.</li><li>В полученном уравнении привести все суммы <tex>&sum;</tex> к замкнутому виду. Получить уравнение для производящей функции.</li><li>Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.</li></ol>

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

f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2geqslant2.\\

z^n\cdot f_n&{}={}&(f_{n-1}+f_{n-2})\cdot z^n, \quad n\geq2geqslant2.\\

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\geq2geqslant2.\\