302
правки
Изменения
Нет описания правки
==Общая схема==
Пусть последовательность <tex>(a_0, a_1, a_2, … )</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n\geq geqslant 0</tex>) в замкнутом виде (если это возможно). [[Производящая_функция| Производящие функции]] позволяют делать эту работу почти механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.
Задано линейное однородное рекуррентное соотношение порядка <tex>2</tex> с постоянными коэффициентами:
a_0&{}={}&0,\\
a_1&{}={}&1,\\
a_n&{}={}&5a_{n-1}-6a_{n-2}, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
1\cdot a_0&{}={}&0\cdot 1,\\
z\cdot a_1&{}={}&0\cdot 1,\\
z^n\cdot a_n&{}={}&5a_{n-1}-6a_{n-2}\cdot z^n, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
G(z)=\displaystyle\sum_{n=0}^{\infty} a_nz^n,
</tex><br>
поэтому, в силу равенства рядов, <tex>a_n=3^n-2^n</tex> (для <tex>n\geq geqslant 0</tex>).
==Метод производящих функций==
<ol>
<li>Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <tex>k</tex>):
<br><tex>a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ a_{n} = …, n\geq geqslant k</tex>
</li>
<li>Домножить каждую строчку на <tex>z</tex> в соответствующей степени и просуммировать строчки для всех <tex>n\geq0geqslant0</tex>.</li>
<li>В полученном уравнении привести все суммы <tex>∑</tex> к замкнутому виду. Получить уравнение для производящей функции.</li>
<li>Выразить <tex>G(z)</tex> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <tex>z</tex>.</li>
f_0&{}={}&0,\\
f_1&{}={}&1,\\
f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
1\cdot f_0&{}={}&0\cdot 1,\\
z\cdot f_1&{}={}&1\cdot z,\\
z^n\cdot f_n&{}={}&(f_{n-1}+f_{n-2})\cdot z^n, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
a_0&{}={}&1,\\
a_1&{}={}&2,\\
a_n&{}={}&6a_{n-1}-8f_{n-2}+n, \quad n\geq2geqslant2.\\
\end{array}
</tex><br>
