Изменения
Нет описания правки
которые фактически являются производящими функциями последовательностей <tex>1, 2, 3...</tex> и <tex>1, 4, 9...</tex>, где z взято равным <tex>\frac{1}{2}</tex>
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>С_nC_n</tex> {{---}} числа Каталана. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> в замкнутом виде.
== Решение рекуррентных соотношений ==
Пусть последовательность <tex>(a_0, a_1, a_2, ...)</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n \ge 0</tex>) в замкнутом виде (то есть выразив лишь!!!!!!!!!!!! через номер члена последовательности). Алгоритм получения замкнутого выражения для чисел <tex>a_n</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций состоит из 4 шагов:
1)Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен k, то есть количество предшествующих элементов, требуемых для вычисления элемента с номером n, равно k):
Разложим знаменатель на множители и [http://www.genfunc.ru/theory/pril04/ разобьём дробь на сумму простых дробей]:
<tex>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}</tex>
<tex>\frac{1}{(1-z)^2}=(1-z)^{-2}=\sum_{n=0}^{\infty} {-2\choose n}(-z)^n</tex>
== Ссылки ==
