302
правки
Изменения
→Метод производящих функций
==Метод производящих функций==
Алгоритм получения замкнутого выражения формулы для чисел <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</tex>. В левой части получится сумма <tex>\displaystyle\sum_{n=0}^{\geqslant0infty} 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>za_n</tex>.</li>
</ol>
