302
правки
Изменения
Нет описания правки
</math><br>
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <math>z1z_1</math>:
<br><math>
\frac{z_1/(z_1-z_2)}{z_1-z} = \frac1{z_1-z_2}\frac{1}{1-\frac{z}{z_1}} =
</math><br>
Аналогично (но с делением на <math>z2z_2</math>) поступим со второй дробью:
<br><math>
\frac{z_2/(z_2-z_1)}{z_2-z} = \frac1{z_2-z_1}\frac1{1-\frac{z}{z_2}} =
====БОЛЕЕ СЛОЖНОЕ СООТНОШЕНИЕ====
Рассмотрим произвольное рекуррентное соотношение:
<br><math>\begin{array}{rcl}
a_0&{}={}&1,\\
a_1&{}={}&2,\\
a_n&{}={}&6a_{n-1}-8f_{n-2}+n, \quad n\geq2.\\
\end{array}
</math><br>
Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:
<br><math>\begin{array}{rcl}
\displaystyle a_0 + a_1 z + \sum_{n=2}^{...
... 6zG(z)-8z^2G(z) + \sum_{n=2}^{\infty}nz^n.\\
\end{array}
</math><br>
Вспомним, что
<br><math>
(z^n)' = nz^{n-1},
</math><br>
поэтому
<br><math>
\sum_{n=2}^{\infty}nz^n=z\sum_{n=2}^{\infty}nz^{n-1}=
z\...
...2}^{\infty}(z^n)'=
z\biggl(\sum_{n=2}^{\infty}z^n\biggr)'.
</math><br>
Последняя сумма может быть свёрнута:
<br><math>
\sum_{n=2}^{\infty}z^n=\sum_{n=0}^{\infty}z^n-1-z=\frac{1}{1-z}-1-z=\frac{z^2}{1-z}.
</math><br>
Подставив свёрнутое выражение обратно, имеем,
<br><math>
z\biggl(\sum_{n=2}^{\infty}z^n\biggr)' = z \biggl(\frac{z^2}{1-z}\biggr)'=\frac{z^2(2-z)}{(1-z)^2}.
</math><br>
Таким образом, наше последнее уравнение примет вид
<br><math>
G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \frac{z^2(2-z)}{(1-z)^2}.\\
</math><br>
Это уравнение для производящей функции. Из него выражаем <math>G(z)</math>:
<br><math>
G(z) = \frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}.
</math><br>
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
<br><math>
G(z) = \frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=
\frac...
...(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}.
</math><br>
Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
<br><math>
\frac{1}{(1-z)^2} =
(1-z)^{-2} =
\sum_{n=0}^{\infty}\...
...}(-1)^n\binom{n+1}{1}(-z)^n =
\sum_{n=0}^{\infty}(n+1)z^n.
</math><br>
Теперь соберём ответ:
<br><math>
G(z) = \frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z...
...=0}^{\infty}2^nz^n
+\frac{7}{18}\sum_{n=0}^{\infty}4^nz^n.
</math><br>
Значит,
<br><math>
a_n=
\frac{n+1}{3}
+\frac{7}{9}
-\frac{2^n}{2}
+\frac{7\cdot4^n}{18}=
\frac{7\cdot4^n+6n+20}{18} - 2^{n-1}.
</math><br>
