Изменения

====ЧИСЛА ФИБОНАЧЧИ====

Рассмотрим рекуррентное соотношение для чисел Фибоначчи:

<br><math>\begin{array}{rcl}

f_0&{}={}&0,\\

\end{array}

</math><br>

Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:

<br><math>\begin{array}{rcl}

1\cdot f_0&{}={}&0\cdot 1,\\

\end{array}

</math><br>

Складываем все строчки:

<br><math>

f_0 + f_1 z + \sum_{n=2}^{\infty}f_nz^n =

z + \sum_{n=2}^{\infty}f_{n-1}z^n+\sum_{n=2}^{\infty}f_{n-2}z^n.

</math><br>

Третий шаг алгоритма требует привести все суммы к замкнутому виду:

<br><math>\begin{array}{rcl}

G(z) &{}={}& \displaystyle z + z\sum_{n=z} &{}={}& \displaystyle z + zG(z)+z^2G(z),\\

\end{array}

</math><br>

откуда получаем замкнутое выражение для производящей функции:

<br><math>

G(z) = \frac{z}{1-z-z^2}.

</math><br>

<br><math>\displaylines{

1-z-z^2 = 0 \cr

}

</math><br>

<br><math>

G(z) = \frac{z}{1-z-z^2}=\frac{-z}{(z_1-z)(z_2-z)}

\frac{z_1/(z_1-z_2)}{z_1-z} + \frac{z_2/(z_2-z_1)}{z_2-z}.

</math><br>

<br><math>

\frac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.

</math><br>

<br><math>

\frac{z_1/(z_1-z_2)}{z_1-z} = \frac1{z_1-z_2}\frac{1}{1-\frac{z}{z_1}} =

\frac1{z_1-z_2}\sum_{n=0}^{\infty}\frac{z^n}{z_1^n}.

</math><br>

<br><math>

\frac{z_2/(z_2-z_1)}{z_2-z} = \frac1{z_2-z_1}\frac1{1-\frac{z}{z_2}} =

\frac1{z_2-z_1}\sum_{n=0}^{\infty}\frac{z^n}{z_2^n}.

</math><br>

Таким образом,

<br><math>

G(z)=\sum_{n=0}^{\infty} f_nz^n =

...rac{1}{z_1^n} + \frac{1}{z_2-z_1}\frac{1}{z_2^n} \biggr)z^n,

</math><br>

и, следовательно,

<br><math>

f_n = \frac1{z_1-z_2}\frac{1}{z_1^n} + \frac1{z_2-z_1}\frac{1}{z_2^n}.

</math><br>

<br><math>

f_n=\frac{1}{\sqrt{5}}\left( \biggl( \frac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \frac{1-\sqrt{5}}{2} \biggr)^n \right).