302
правки
Изменения
Нет описания правки
Складываем все строчки:
<br><tex>
f_0 + f_1 z + \displaystyle\sum_{n=2}^{\infty}f_nz^n =z + \displaystyle\sum_{n=2}^{\infty}f_{n-1}z^n+\displaystyle\sum_{n=2}^{\infty}f_{n-2}z^n.
</tex><br>
Третий шаг алгоритма требует привести все суммы к замкнутому виду:
<br><tex>\begin{array}{rcl}
G(z) &{}={}& z + \displaystyle\sum_{n=2}^{\infty}f_{n-1}z^{n-1}+\displaystyle\sum_{n=2}^{\infty}f_{n-2}z^{n-2}, \\G(z) &{}={}& z + \displaystyle\sum_{n=1}^{\infty}f_{n}z^n+\displaystyle\sum_{n=0}^{\infty}f_{n}z^n, \\
G(z)&{}={}& \displaystyle z + z(G(z)-f_0)+z^2G(z),\\
G(z)&{}={}& \displaystyle z + zG(z)+z^2G(z),\\
Нам известно разложение следующей рациональной функции:
<br><tex>
\dfrac{1}{1-z} = \displaystyle\sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
</tex><br>
<br><tex>
\dfrac{z_1/(z_1-z_2)}{z_1-z} = \dfrac1{z_1-z_2}\dfrac{1}{1-\dfrac{z}{z_1}} =
\dfrac1{z_1-z_2}\displaystyle\sum_{n=0}^{\infty}\dfrac{z^n}{z_1^n}.
</tex><br>
<br><tex>
\dfrac{z_2/(z_2-z_1)}{z_2-z} = \dfrac1{z_2-z_1}\dfrac1{1-\dfrac{z}{z_2}} =
\dfrac1{z_2-z_1}\displaystyle\sum_{n=0}^{\infty}\dfrac{z^n}{z_2^n}.
</tex><br>
Таким образом,
<br><tex>
G(z)=\displaystyle\sum_{n=0}^{\infty} f_nz^n =\displaystyle\sum_{n=0}^{\infty}\biggr(\dfrac{1}{z_1-z_2}\dfrac{1}{z_1^n} + \dfrac{1}{z_2-z_1}\dfrac{1}{z_2^n} \biggr)z^n,
</tex><br>
Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:
<br><tex>\begin{array}{rcl}
\displaystyle a_0 + a_1 z + \displaystyle\sum_{n=2}^{\infty}{a_n}{z^n} &{}={}& 1+2z+6\displaystyle\sum_{n=2}^{\infty}{a_{n-1}}{z^n}-8\displaystyle\sum_{n=2}^{\infty}{a_{n-2}}{z^n}+\displaystyle\sum_{n=2}^{\infty}nz^n, \\G(z) &{}={}& 1+2z+6z\displaystyle\sum_{n=2}^{\infty}{a_{n-1}}{z^{n-1}}-8z^2\displaystyle\sum_{n=2}^{\infty}{a_{n-2}}{z^{n-2}}+\displaystyle\sum_{n=2}^{\infty}nz^n, \\G(z) &{}={}& 1+2z+6z\displaystyle\sum_{n=1}^{\infty}{a_{n}}{z^{n}}-8z^2\displaystyle\sum_{n=0}^{\infty}{a_{n}}{z^{n}}+\displaystyle\sum_{n=2}^{\infty}nz^n, \\G(z) &{}={} & 1+ 2z + 6z(G(z)-a_0)-8z^2G(z) + \displaystyle\sum_{n=2}^{\infty}nz^n.\\G(z) &{}={} & 1 - 4z + 6zG(z)-8z^2G(z) + \displaystyle\sum_{n=2}^{\infty}nz^n.\\
\end{array}
</tex><br>
поэтому
<br><tex>
\displaystyle\sum_{n=2}^{\infty}nz^n=z\displaystyle\sum_{n=2}^{\infty}nz^{n-1}=z\displaystyle\sum_{n=2}^{\infty}(z^n)'=z\biggl(\displaystyle\sum_{n=2}^{\infty}z^n\biggr)'.
</tex><br>
Последняя сумма может быть свёрнута:
<br><tex>
\displaystyle\sum_{n=2}^{\infty}z^n=\displaystyle\sum_{n=0}^{\infty}z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}.
</tex><br>
Подставив свёрнутое выражение обратно, имеем,
<br><tex>
z\biggl(\displaystyle\sum_{n=2}^{\infty}z^n\biggr)' = z \biggl(\dfrac{z^2}{1-z}\biggr)'=\dfrac{z^2(2-z)}{(1-z)^2}.
</tex><br>
Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
<br><tex>
\dfrac{1}{(1-z)^2} =(1-z)^{-2} =\displaystyle\sum_{n=0}^{\infty}\binom{-2}{n}(-z)^n=\displaystyle\sum_{n=0}^{\infty}(-1)^n\binom{n+1}{1}(-z)^n =\displaystyle\sum_{n=0}^{\infty}(n+1)z^n.
</tex><br>
Теперь соберём ответ:
<br><tex>
G(z) = \dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=\dfrac{1}{3}\displaystyle\sum_{n=0}^{\infty}(n+1)z^n+\dfrac{7}{9}\displaystyle\sum_{n=0}^{\infty}z^n-\dfrac{1}{2}\displaystyle\sum_{n=0}^{\infty}2^nz^n+\dfrac{7}{18}\displaystyle\sum_{n=0}^{\infty}4^nz^n.
</tex><br>
