302
правки
Изменения
Нет описания правки
Для этого можно использовать [[Решение_рекуррентных_соотношений#Метод производящих функций | метод производящих функций]] (англ. ''generating Function Method'').
==Общая схемаМетод производящих функций==Алгоритм получения замкнутого выражения для чисел <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>n\geqslant0</tex>.</li><li>В полученном уравнении привести все суммы <tex>∑</tex> к замкнутому виду. Получить уравнение для производящей функции.</li><li>Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.</li></ol> ==Примеры=====1 пример===
[[Производящая_функция| Производящие функции]] позволяют решать рекуррентные соотношение механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.
поэтому, в силу равенства рядов, <tex>a_n=3^n-2^n</tex> (для <tex>n\geqslant 0</tex>).
==Метод производящих функций==Алгоритм получения замкнутого выражения для чисел <tex>a_{n}</tex>, удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из <tex>4</tex> шагов.<ol><li>Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>)2 пример:<br><tex>a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ a_{n} = …, n\geqslant k</tex></li> <li>Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n\geqslant0</tex>.</li><li>В полученном уравнении привести все суммы <tex>∑</tex> к замкнутому виду. Получить уравнение для производящей функции.</li><li>Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.</li></ol> ==Примеры======Числа числа Фибоначчи====
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
<br><tex>\begin{array}{rcl}
</tex><br>
====Произвольное соотношение3 пример====
Рассмотрим следующее рекуррентное соотношение:
<br><tex>\begin{array}{rcl}
