Изменения

Перейти к: навигация, поиск

Решение рекуррентных соотношений

104 байта добавлено, 13:32, 13 марта 2018
Нет описания правки
==Примеры==
====ЧИСЛА ФИБОНАЧЧИЧисла Фибоначчи====
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
<br><math>\begin{array}{rcl}
</math><br>
====СЛОЖНОЕ СООТНОШЕНИЕПроизвольное соотношение====Рассмотрим произвольное следующее рекуррентное соотношение:
<br><math>\begin{array}{rcl}
a_0&{}={}&1,\\
Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:
<br><math>\begin{array}{rcl}
\displaystyle a_0 + a_1 z + \sum_{n=2}^{\infty}{a_n}{z^n} &{}={}& 1+2z+6\sum_{n=2}^{\infty}{a_{n-1}}{z^n}+-8\sum_{n=2}^{\infty}nz{a_{n-2}}{z^n, \\\displaystyle a_0 + a_1 z }+ \sum_{n=2}^{\infty}{a_n}{znz^n} , \\G(z) &{}={}& 1+2z+6z\sum_{n=2}^{\infty}{a_{n-1}}{z^{n-1}}-8z^2\sum_{n=2}^{\infty}{a_{n-2}}{z^{n-2}}+\sum_{n=2}^{\infty}nz^n, \\\displaystyle a_0 G(z) &{}={}& 1+ a_1 z 2z+ 6z\sum_{n=21}^{\infty}{a_na_{n}}{z^{n} &{}={}& 1+2z+6-8z^2\sum_{n=20}^{\infty}{a_{n-1}}{z^{n}}+\sum_{n=2}^{\infty}nz^n, \\G(z) &{}={} & 6zG1+ 2z + 6z(G(z)-a_0)-8z^2G(z) + \sum_{n=2}^{\infty}nz^n.\\G(z) &{}={} & 1 - 4z + 6zG(z)-8z^2G(z) + \sum_{n=2}^{\infty}nz^n.\\
\end{array}
</math><br>
поэтому
<br><math>
\sum_{n=2}^{\infty}nz^n=z\sum_{n=2}^{\infty}nz^{n-1}=z\......sum_{n=2}^{\infty}(z^n)'=z\biggl(\sum_{n=2}^{\infty}z^n\biggr)'.
</math><br>
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
<br><math>
G(z) = \frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\frac......{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\frac{1/3}{(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}\......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.
</math><br>
302
правки

Навигация