==Метод производящих функций==
Алгоритм получения выражения для чисел <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_i</tex>, где <tex>i \in [k, +\infty)</tex>. В левой части получится сумма <tex>\displaystyle\sum_{n=0}^{\infty} a_nz^n</tex> — это производящая функция, назовем ее <tex>G(z)</tex>. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее <tex>G(z)</tex>.</li><li>#Решить полученное уравнение, получив для <tex>G(z)</tex> выражение в замкнутом виде.</li><li>#Разложить <tex>G(z)</tex> в степенной ряд, коэффициент при <tex>z_n</tex> будет искомым выражением для <tex>a_n</tex>.</li></ol>
==Примеры==
