302
правки
Изменения
Нет описания правки
может быть переведена в замкнутую форму: <tex>f = \dfrac{n(n+1)}{2}</tex>. Для этого можно использовать метод производящих функций.
==Общая схема==
Пусть последовательность <tex>(a_0, a_1, a_2, … )</tex> удовлетворяет некоторому рекуррентному соотношению. Мы хотим получить выражение для <tex>a_n</tex> (при <tex>n\geq 0</tex>) в замкнутом виде (если это возможно). Производящие функции позволяют делать эту работу почти механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.
Задано линейное однородное рекуррентное соотношение порядка <tex>2</tex> с постоянными коэффициентами:
<br><tex>\begin{array}{rcl}
a_0&{}={}&0,\\
a_1&{}={}&1,\\
a_n&{}={}&5a_{n-1}-6a_{n-2}, \quad n\geq2.\\
\end{array}
</tex><br>
Порядок соотношения — это его «глубина», то есть количество предшествующих элементов, требуемых для вычисления элемента с номером n. В данном случае порядок равен <tex>2</tex>, так как для вычисления <tex>a_n<tex> требуется знать <tex>a_{n-1}</tex> и <tex>a_{n-2}</tex>.
Будем искать производящую функцию последовательности в виде
<br><tex>
G(z)=\sum_{n=0}^{\infty} a_nz^n = a_0+a_1z+a_2z^2+\cdots,
</tex><br>
с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на <tex>z^0</tex>, следующую — на <tex>z^1<tex> и последнюю — на <tex>z^n</tex>:
<br><tex>\begin{array}{rcl}
1\cdot a_0&{}={}&0\cdot 1,\\
z\cdot a...
...(5a_{n-1}-6a_{n-2})\cdot z^n, \quad n\geq2.\\
\end{array}
</tex><br>
Теперь сложим все уравнения для всех значений <tex>n</tex>:
<br><tex>
\underbrace{a_0 + a_1 z + \sum_{n=2}^{\infty}a_nz^n}_{g(z)...
...sum_{n=2}^{\infty}a_{n-1}z^n-6\sum_{n=2}^{\infty}a_{n-2}z^n.
</tex><br>
Левая часть уравнения в точности равна <tex>G(z)</tex>, а в правой части есть суммы, очень похожие на функцию <tex>G(z)</tex>, но не равные ей. Эти суммы нужно любым законным способом привести к виду <tex>G(z)</tex>. Начнём с первой:
<br><tex>
\sum_{n=2}^{\infty}a_{n-1}z^n \stackrel{(1)}{=}
z\sum_{...
..._{n}z^{n}+a_0}_{g(z)} - a_0\biggr)
\stackrel{(4)}{=}zg(z).
</tex><br>
Равенство <tex>(1)</tex> получатся вынесением z в первой степени за знак суммы, это необходимо, чтобы уровнять степень переменной <tex>z</tex> и индекс переменной a внутри суммы. Действие <tex>(2)</tex> — изменение индекса суммирования, которое позволяет избавиться от <tex>n-1</tex>. Равенство <tex>(3)</tex> получается, если прибавить и снова отнять значение <tex>a_0</tex>, чтобы получить полную сумму от <tex>n=0</tex> до <tex>∞</tex>. Равенство <tex>(4)</tex> справедливо в силу того, что <tex>a_0=0</tex>.
Аналогичные манипуляции со второй суммой дают нам выражение
<br><tex>
\sum_{n=2}^{\infty}a_{n-2}z^n = z^2\sum_{n=2}^{\infty}a_{n-2}z^{n-2}
= z^2\sum_{n=0}^{\infty}a_{n}z^{n}=z^2g(z).
</tex><br>
Теперь наше исходное уравнение для производящей функции принимает вид:
<br><tex>
G(z) = z + 5zG(z) -6z^2G(z),
</tex><br>
откуда получаем производящую функцию последовательности в замкнутом виде —
<br><tex>
G(z) = \dfrac{z}{1-5z+6z^2}.
</tex><br>
Отыскав производящую функцию в замкнутом виде, её нужно снова разложить в ряд. Это можно сделать разными способами, но самый простой из них — разбить всю дробь на простые дроби и применить формулу для разложения <tex>\dfrac{1}{1-z}</tex>. Итак, разложим знаменатель функции на множители:
<br><tex>
G(z) = \dfrac{z}{1-5z+6z^2} = \dfrac{z}{(1-3z)(1-2z)}.
</tex><br>
Теперь разобьём дробь на сумму простых дробей:
<br><tex>
\dfrac{z}{(1-3z)(1-2z)} = \dfrac{1}{1-3z} - \dfrac{1}{1-2z}.
</tex><br>
Вспомним разложение для простейшей рациональной функции:
<br><tex>
\dfrac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
</tex><br>
Из этого разложения следует, что
<br><tex>
\dfrac{1}{1-3z}= \sum_{n=0}^{\infty}(3z)^n \quad\mbox{ и }\quad \dfrac{1}{1-2z}= \sum_{n=0}^{\infty}(2z)^n.
</tex><br>
Таким образом,
<br><tex>
G(z) = \sum_{n=0}^{\infty}3^nz^n - \sum_{n=0}^{\infty}2^nz^n = \sum_{n=0}^{\infty}(3^n-2^n)z^n.
</tex><br>
С другой стороны, мы искали <tex>G(z)</tex> в виде
<br><tex>
G(z)=\sum_{n=0}^{\infty} a_nz^n,
</tex><br>
поэтому, в силу равенства рядов, <tex>a_n=3^n-2^n</tex> (для <tex>n\geq 0</tex>).
==Метод производящих функций==
