Изменения
Нет описания правки
которые фактически являются производящими функциями последовательностей <tex>1, 2, 3...</tex> и <tex>1, 4, 9...</tex>, где z взято равным <tex>\frac{1}{2}</tex>
Существует целый класс последовательностей, задаваемых рекуррентным соотношением, например, <tex>f_n</tex> {{---}} числа Фибоначчи или <tex>C_n</tex> {{---}} числа Каталана. Метод производящих функций позволяет получить выражение для <tex>a_n</tex> через номер элемента в последоваетльности в замкнутом виде, то есть в таком виде, что выражение можно вычислить, предполагая, что z достаточно мало.
== Решение рекуррентных соотношений ==
Пусть последовательность <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):
