302
правки
Изменения
Нет описания правки
==Примеры==
====ЧИСЛА ФИБОНАЧЧИ====
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
<br>[[Файл:Img39.png]]<br>
Это хорошо известная последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:
<br>[[Файл:Img40.png]]<br>
Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
<br>[[Файл:Img45.png]]<br>
откуда получаем замкнутое выражение для производящей функции:
<br>[[Файл:Img48.png]]<br>
Осталось «всего лишь» разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
<br>[[Файл:Img49.png]]<br>
Таким образом (проверьте),
<br>[[Файл:Img50.png]]<br>
<br>[[Файл:Img31.png]]<br>
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <math>z1</math>:
<br>[[Файл:Img52.png]]<br>
Аналогично (но с делением на <math>z2</math>) поступим со второй дробью:
<br>[[Файл:Img53.png]]<br>
Таким образом,
и, следовательно,
<br>[[Файл:Img55.png]]<br>
Данное выражение можно «причесать»упростить, если обратить внимание на то, что <math>1/z1=-z2</math>, <math>1/z2=-z1 </math> и <math>z1-z2=√5 (корень из 5)</math>:
<br>[[Файл:Img59.png]]<br>
====БОЛЕЕ СЛОЖНОЕ СООТНОШЕНИЕ====