Изменения

Для рекуррентного соотношения, которому удовлетворяет последовательность <tex> \{ a_n \} </tex> мы часто хотим получить выражение для <tex>a_n</tex>. Например, для чисел рекуррентного соотношения, задающего числа Фибоначчи:

F_0 = 0,\qquad F_1 = 1,\qquad F_{n} = F_{n-1} + F_{n-2}, \quad n\geqslant 2, \quad n\in Z.</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 n \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>

===<tex>1 </tex> пример===

z^n\cdot a_n&{}={}&(5a_{n-1}-6a_{n-2})\cdot z^n, \quad n\geqslant2.\\

откуда получаем производящую функцию последовательности в замкнутом виде —:

====<tex>2 </tex> пример: числа Фибоначчи====

Данное выражение можно упростить, если обратить внимание на то, что <tex>1/z_1=-z_2</tex>, <tex>1/z_2=-z_1</tex> и <tex>z_1-z_2=√5</tex>, подставим . Подставим <tex>z_1</tex> и <tex>z_2</tex>в предыдущее выражение:

===<tex>3</tex> пример===Найдём производящую функцию для последовательности квадратов чисел Фибоначчи: $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$. По определению последовательности Фибоначчи выполняется:<br><tex>\left\{ \begin{array}{ll} f_{n+2} = f_{n+1} + f_n \\ f_{n-1} = f_{n+1} - f_n \end{array} \right.</tex><br>Возведя в квадрат и сложив, получим:<br><tex>\begin{array}{rcl}f_{n+2}^2 + f_{n-1}^2 = 2f_{n+1}^2 + 2f_n^2, \\f_{n+2}^2 = 2f_{n+1}^2 + 2f_n^2 - f_{n-1}^2, \\f_{n}^2 = 2f_{n-1}^2 + 2f_{n-2}^2 - f_{n-3}^2.\\\end{array}</tex><br>Обозначим рассматриваемую последовательность <tex>A</tex>, а её члены <tex>a_n</tex>, тогда:<br><tex>a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3 }</tex><br> Рекуррентное соотношение:<br><tex>\begin{array}{ll}a_0 = f_0^2 = 1 \\a_1 = f_1^2 = 1 \\a_2 = f_2^2 = 4 \\a_n = 2a_{n-1} + 2a_{n-2} - a_{n-3}, \quad n\geqslant3.\\\end{array}</tex><br> Приведём суммы к замкнутому виду:<br><tex>\begin{array}{ll}A(z) = \displaystyle\sum_{n=0}^{\infty}a_nz^n = 1 + z + 4z^2 + \displaystyle\sum_{n=3}^{\infty}(2a_{n-1} + 2a_{n-2} - a_{n-3})z^n, \\A(z) = 1 + z + 4z^2 + 2\displaystyle\sum_{n=3}^{\infty}a_{n-1}z^n + 2\displaystyle\sum_{n=3}^{\infty}a_{n-2}z^n - \displaystyle\sum_{n=3}^{\infty}a_{n-3}z^n, \\A(z) = 1 + z + 4z^2 + 2z\displaystyle\sum_{n=2}^{\infty}a_nz^n + 2z^2\displaystyle\sum_{n=1}^{\infty}a_nz^n - z^3\displaystyle\sum_{n=0}^{\infty}a_nz^n, \\A(z) = 1 + z + 4z^2 + 2z(A(z) - 1 - z) + 2z^2(A(z) - 1) - z^3A(z), \\A(z) = 1 + z + 4z^2 + 2zA(z) - 2z - 2z^2 + 2z^2A(z) - 2z^2 - z^3A(z), \\A(z)(1 - 2z - 2z^2 + z^3) = 1 + z + 4z^2 - 2z - 2z^2 - 2z^2 = 1 - z, \\\end{array}</tex><br>откуда получаем замкнутое выражение для производящей функции:<br><tex>G(z) = \dfrac{1 - z}{1 - 2z - 2z^2 + z^3}.</tex><br> ===<tex>4</tex> пример====

a_n&{}={}&6a_{n-1}-8f_8a_{n-2}+n, \quad n\geqslant2.\\