Изменения

<br><math>a_{0} = ...,<br>\\ a_{1} = ...,<br>\\ a_{k-1} = ...,<br>\\ a_{n} = ..., n&ge;k</math>

 <br>[[Файл:Img39<math>\begin{array}{rcl}f_0&{}={}&0,\\f_1&{}={}&1,\\f_n&{}={}&f_{n-1}+f_{n-2}, \quad n\geq2.png]]\\\end{array}</math><br>

 <br>[[Файл:Img40<math>\begin{tabular}{\vert c\vert c\vert c\vert c\vert c\vert c.....png]].& 2 & 3 & 5 & 8 & 13 & 21 & 34 \\\hline\end{tabular}</math><br>Эти числа очень быстро растут, например, f10=55, f20=6765, f30=832040, f100=354224848179261915075. 

 <br>[[Файл:Img45<math>\begin{array}{rcl}1\cdot f_0&{}={}&0\cdot 1,\\z\cdot f_1&{}={}&1\cdot z,\\z^n\cdot f_n&{}={}&(f_{n-1}+f_{n-2})\cdot z^n, \quad n\geq2.png]]\\\end{array}</math><br>

 <br>[[Файл:Img46<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.png]]</math><br>

 <br>[[Файл:Img47.png]]<math>\begin{array}{rcl}G(z) &{}={}& \displaystyle z + z\sum_{n=z} &{}={}& \displaystyle z + zG(z)+z^2G(z),\\\end{array}</math><br>

 <br>[[Файл:Img48<math>G(z) = \frac{z}{1-z-z^2}.png]]</math><br>Осталось «всего лишь» разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения: <br><math>\displaylines{1-z-z^2 = 0 \crz_1=-\frac{1-\sqrt{5}}{2}, z_2=-\frac{1+\sqrt{5}}{2}.}</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>[[ФайлКак теперь поступить с этими выражениями? Ведь пока нам известно разложение только одной рациональной функции:Img49 <br><math>\frac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.png]]</math><br>Рассмотрим первую дробь и поделим в ней числитель и знаменатель на z1: <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>Аналогично (но с делением на z2) поступим со второй дробью: <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>[[Файл:Img50.png]]<br>Нам известно разложение только следующей рациональной функции:<br>[[Файл:Img31.png]]<br>Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <math>z1</math>:<br>[[Файл:Img52.png]]<br>Аналогично G(но с делением на <math>z2</math>z) поступим со второй дробью:=\sum_{n=0}^{\infty} f_nz^n =<br>[[Файл:Img53\sum_{n=0}^{\infty}\b...png]]<br>Таким образом...rac{1}{z_1^n} + \frac{1}{z_2-z_1}\frac{1}{z_2^n} \biggr)z^n,<br/math>[[Файл:Img54.png]]<br>

 <br>[[Файл:Img55<math>f_n = \frac1{z_1-z_2}\frac{1}{z_1^n} + \frac1{z_2-z_1}\frac{1}{z_2^n}.png]]</math><br>Данное выражение можно упростить«причесать», если обратить внимание на то, что <math>1/z1=-z2</math>, <math>1/z2=-z1</math> и <math>z1-z2=√5(корень из 5): <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).<br/math>[[Файл:Img59.png]]<br>