302
правки
Изменения
Нет описания правки
<ol>
<li>Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен <math>k</math>):
<image src="httpbr>[[Файл://www.genfunc.ru/theory/rsol/img37.png"></image>]]
</li>
<li>Выразить <math>G(z)</math> в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням <math>z</math>.</li>
</ol>
==Доказательство==
==Примеры==
====ЧИСЛА ФИБОНАЧЧИ====
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
<br>[[Файл:Img39.png]]<br>
Это хорошо известная последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:
<br>[[Файл:Img40.png]]<br>
Эти числа очень быстро растут, например, f10=55, f20=6765, f30=832040, f100=354224848179261915075.
Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
<br>[[Файл:Img45.png]]<br>
Складываем все строчки:
<br>[[Файл:Img46.png]]<br>
Третий шаг алгоритма требует привести все суммы к замкнутому виду:
<br>[[Файл:Img47.png]]<br>
откуда получаем замкнутое выражение для производящей функции:
<br>[[Файл:Img48.png]]<br>
Осталось «всего лишь» разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
<br>[[Файл:Img49.png]]<br>
Таким образом (проверьте),
<br>[[Файл:Img50.png]]<br>
Как теперь поступить с этими выражениями? Ведь пока нам известно разложение только одной рациональной функции:
<br>[[Файл:Img31.png]]<br>
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на z1:
<br>[[Файл:Img52.png]]<br>
Аналогично (но с делением на z2) поступим со второй дробью:
<br>[[Файл:Img53.png]]<br>
Таким образом,
<br>[[Файл:Img54.png]]<br>
и, следовательно,
<br>[[Файл:Img55.png]]<br>
Данное выражение можно «причесать», если обратить внимание на то, что 1/z1=-z2, 1/z2=-z1 и z1-z2=√5 (корень из 5):
<br>[[Файл:Img59.png]]<br>
====БОЛЕЕ СЛОЖНОЕ СООТНОШЕНИЕ====
