302
правки
Изменения
Нет описания правки
<tex> f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n > 0 \end{cases}</tex>
может быть переведена в замкнутую форму: <tex>f = \fracdfrac{n(n+1)}{2}</tex>. Для этого можно использовать метод производящих функций.
==Метод производящих функций==
откуда получаем замкнутое выражение для производящей функции:
<br><tex>
G(z) = \fracdfrac{z}{1-z-z^2}.
</tex><br>
<br><tex>\displaylines{
1-z-z^2 = 0 \cr
z_1=-\fracdfrac{1-\sqrt{5}}{2}, z_2=-\fracdfrac{1+\sqrt{5}}{2}.
}
</tex><br>
Таким образом,
<br><tex>
G(z) = \fracdfrac{z}{1-z-z^2}=\fracdfrac{-z}{(z_1-z)(z_2-z)}
=
\fracdfrac{z_1/(z_1-z_2)}{z_1-z} + \fracdfrac{z_2/(z_2-z_1)}{z_2-z}.
</tex><br>
Нам известно разложение следующей рациональной функции:
<br><tex>
\fracdfrac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
</tex><br>
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <tex>z_1</tex>:
<br><tex>
\fracdfrac{z_1/(z_1-z_2)}{z_1-z} = \frac1dfrac1{z_1-z_2}\fracdfrac{1}{1-\fracdfrac{z}{z_1}} =\frac1dfrac1{z_1-z_2}\sum_{n=0}^{\infty}\fracdfrac{z^n}{z_1^n}.
</tex><br>
Аналогично (но с делением на <tex>z_2</tex>) поступим со второй дробью:
<br><tex>
\fracdfrac{z_2/(z_2-z_1)}{z_2-z} = \frac1dfrac1{z_2-z_1}\frac1dfrac1{1-\fracdfrac{z}{z_2}} =\frac1dfrac1{z_2-z_1}\sum_{n=0}^{\infty}\fracdfrac{z^n}{z_2^n}.
</tex><br>
<br><tex>
G(z)=\sum_{n=0}^{\infty} f_nz^n =
\sum_{n=0}^{\infty}\biggr(\fracdfrac{1}{z_1-z_2}\fracdfrac{1}{z_1^n} + \fracdfrac{1}{z_2-z_1}\fracdfrac{1}{z_2^n} \biggr)z^n,
</tex><br>
и, следовательно,
<br><tex>
f_n = \frac1dfrac1{z_1-z_2}\fracdfrac{1}{z_1^n} + \frac1dfrac1{z_2-z_1}\fracdfrac{1}{z_2^n}.
</tex><br>
Данное выражение можно упростить, если обратить внимание на то, что <tex>1/z_1=-z_2</tex>, <tex>1/z_2=-z_1</tex> и <tex>z_1-z_2=√5</tex>:
<br><tex>
f_n=\fracdfrac{1}{\sqrt{5}}\left( \biggl( \fracdfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \fracdfrac{1-\sqrt{5}}{2} \biggr)^n \right).
</tex><br>
Последняя сумма может быть свёрнута:
<br><tex>
\sum_{n=2}^{\infty}z^n=\sum_{n=0}^{\infty}z^n-1-z=\fracdfrac{1}{1-z}-1-z=\fracdfrac{z^2}{1-z}.
</tex><br>
Подставив свёрнутое выражение обратно, имеем,
<br><tex>
z\biggl(\sum_{n=2}^{\infty}z^n\biggr)' = z \biggl(\fracdfrac{z^2}{1-z}\biggr)'=\fracdfrac{z^2(2-z)}{(1-z)^2}.
</tex><br>
Таким образом, наше последнее уравнение примет вид
<br><tex>
G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \fracdfrac{z^2(2-z)}{(1-z)^2}.\\
</tex><br>
Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:
<br><tex>
G(z) = \fracdfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}.
</tex><br>
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
<br><tex>
G(z) = \fracdfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\fracdfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\fracdfrac{1/3}{(1-z)^2}+\fracdfrac{7/9}{1-z}-\fracdfrac{1/2}{1-2z}+\fracdfrac{7/18}{1-4z}.
</tex><br>
Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
<br><tex>
\fracdfrac{1}{(1-z)^2} =(1-z)^{-2} =\sum_{n=0}^{\infty}\binom{-2}{n}(-z)^n=\sum_{n=0}^{\infty}(-1)^n\binom{n+1}{1}(-z)^n =\sum_{n=0}^{\infty}(n+1)z^n.
</tex><br>
Теперь соберём ответ:
<br><tex>
G(z) = \fracdfrac{1/3}{(1-z)^2}+\fracdfrac{7/9}{1-z}-\fracdfrac{1/2}{1-2z}+\fracdfrac{7/18}{1-4z}=\fracdfrac{1}{3}\sum_{n=0}^{\infty}(n+1)z^n+\fracdfrac{7}{9}\sum_{n=0}^{\infty}z^n-\fracdfrac{1}{2}\sum_{n=0}^{\infty}2^nz^n+\fracdfrac{7}{18}\sum_{n=0}^{\infty}4^nz^n.
</tex><br>
<br><tex>
a_n=
\fracdfrac{n+1}{3}+\fracdfrac{7}{9}-\fracdfrac{2^n}{2}+\fracdfrac{7\cdot4^n}{18}=\fracdfrac{7\cdot4^n+6n+20}{18} - 2^{n-1}.
</tex><br>
