Изменения

'''Рекуррентная формула''' (англ. ''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>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> в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:

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

может быть переведена в замкнутую форму: <math>f = \frac{n(n+1)}{2}</math>. Для этого можно использовать метод производящих функций(англ. ''generating function method'').

Алгоритм получения замкнутого выражения для чисел <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&ge;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>. Будем искать производящую функцию последовательности в виде<br><litex>Домножить каждую G(z)=\displaystyle\sum_{n=0}^{\infty} a_nz^n = a_0+a_1z+a_2z^2+\cdots,</tex><br> с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на <tex>z^0</tex>, следующую — на <mathtex>z^1</mathtex> в соответствующей степени и просуммировать строчки последнюю — на <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&ge;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> Левая часть уравнения в точности равна <tex>G(z)<li/tex>В полученном уравнениипривести все , а в правой части есть суммы , очень похожие на функцию <mathtex>&sum;G(z)</mathtex> , но не равные ей. Эти суммы нужно привести к замкнутому виду. Получить уравнение для производящей функции.<tex>G(z)</litex>. Начнём с первой:<libr>Выразить <mathtex>\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</mathtex> в явном виде первой степени за знак суммы, это необходимо, чтобы уровнять степень переменной <tex>z</tex> и индекс переменной a внутри суммы. Действие <tex>(решить уравнение2)</tex> — изменение индекса суммирования, полученное на предыдущем шагекоторое позволяет избавиться от <tex>n-1</tex>. Равенство <tex>(3) </tex> получается, если прибавить и разложить производящую функцию в ряд по степеням снова отнять значение <tex>a_0</tex>, чтобы получить полную сумму от <tex>n=0</tex> до <mathtex>z∞</mathtex>.Равенство <tex>(4)</litex>справедливо в силу того, что <tex>a_0=0</oltex>.

Аналогичные манипуляции со второй суммой дают нам выражение<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),</tex><br> откуда получаем производящую функцию последовательности в замкнутом виде:<br><tex>G(z) = \dfrac{z}{1-5z+6z^2}.</tex><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><tex>\dfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.</tex><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.</tex><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.</tex><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_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2geqslant2.\\

</mathtex><br>Это хорошо известная последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих: <br><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><br>Эти числа очень быстро растут, например, f10=55, f20=6765, f30=832040, f100=354224848179261915075.

 <br><mathtex>\begin{array}{rcl}

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

</mathtex><br> 

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

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><tex>\dfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.</tex><br>

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <tex>z_1</tex>:<br><mathtex>\fracdfrac{z_1/(z_1-z_2)}{z_1-z} = \dfrac1{z_1-z_2}\dfrac{1}{1-\dfrac{z}{z_1}} = \dfrac1{z_1-z_2}\displaystyle\sum_{n=0}^{\infty}\dfrac{z^n = 1 + z + z}{z_1^2 + z^3 + \cdotsn}.</mathtex><br>Рассмотрим первую дробь и поделим в ней числитель и знаменатель на z1:

Аналогично (но с делением на <tex>z_2</tex>) поступим со второй дробью:<br><mathtex>\fracdfrac{z_1z_2/(z_2-z_1-z_2)}{z_1z_2-z} = \frac1dfrac1{z_2-z_1-z_2}\frac{1}dfrac1{1-\fracdfrac{z}{z_1z_2}} =\frac1dfrac1{z_2-z_1-z_2}\displaystyle\sum_{n=0}^{\infty}\fracdfrac{z^n}{z_1z_2^n}.</mathtex><br>Аналогично (но с делением на z2) поступим со второй дробью:

<br><math>f_n = \frac1{z_1-z_2}\frac{1}{z_1^n} + \frac1{z_2-z_1}\frac{1}{z_2^n}=См.также==</math><br>* [[Производящая функция]]Данное выражение можно «причесать», если обратить внимание на то, что 1/z1=-z2, 1/z2=-z1 и z1-z2=√5 (корень из 5):* [[Арифметические действия с формальными степенными рядами]]

<br><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)* [http://www.genfunc.<ru/theory/rsol/math><br>Решение рекуррентных соотношений]