Рекуррентный способ математика это

Рекуррентные соотношения и уравнения

В этом разделе вы найдете бесплатные примеры решений рекуррентных соотношений методом характеристического уравнения и подбора частного решения по правой части. Также приведены краткие алгоритмы решения для двух методов и пример их использования для последовательности Фибоначчи.

Как решать рекуррентные соотношения?

Для решения рекуррентных соотношений применяют один из двух основных способов:

• Метод производящих функций
• Метод характеристического уравнения

В следующем разделе мы сравним, как выглядит процесс решения для одной и той же последовательности двумя методами.

Метод производящих функций

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен $k$) $$a_ <0>= …, \\ a_ <1>= …, \\ a_ = …, \\ … \\ a_ = …, n\geqslant k$$
2. Домножить каждую строчку на $z$ в соответствующей степени $z^ \cdot a_$ и сложить все выражения для $n \ge 0$. В левой части получится сумма $\displaystyle\sum_^ <\infty>a_nz^n$ — это производящая функция, назовем ее $G(z)$. Правую часть преобразовать так, чтобы она превратилась в выражение, включающее $G(z)$.
3. Решить полученное уравнение относительно $G(z)$.
4. Разложить $G(z)$ в степенной ряд, тогда коэффициент при $z_n$ будет искомым выражением для $a_n$.

Метод характеристических функций

Этот метод практически полностью аналогичен методу решения линейных неоднородных дифференциальных уравнений с постоянными коэффициентами, кратко алгоритм выглядит так:

1. Записать соответствующее однородное рекуррентное уравнение (РУ): $$ p_ a_ + p_a_ + . + p_n a_n =f \to \\ \to p_ a_ + p_a_ + . + p_n a_n =0. $$
2. Выписать для него характеристическое уравнение и найти его корни $\lambda_i$ $$ p_ \lambda^ + p_\lambda^ + . + p_\lambda + p_n =0. $$
3. Выписать согласно полученным корням $\lambda_1, . \lambda_k$ общее решение однородного рекуррентного соотношения (подробнее теорию см. по ссылке [1] ниже). $$ C_1 \lambda_1^n +. +C_k \lambda_k^n \, \mbox < для случая различных простых корней>, $$ $$ C_1 \lambda_1^n + C_2 n\lambda_1^n +. +C_m n^m \lambda_1^n+. +C_k \lambda_k^n \mbox < для случая корня >\, \lambda_1 \, < кратности >\, m. $$
4. Подобрать частное решение неоднородного рекуррентного соотношения по виду правой части (особенно удобно для правых частей вида $\mu^n*P(n)$, $P(n)$ — многочлен от $n$).
5. Представить общее решение неоднородного РУ как сумму общего решения соответствующего однородного РУ и частного решения неоднородного РУ.
6. Подставить начальные условия $a_0, a_1, . a_$ и получить значения констант $C_1, . C_k$.

Решение для последовательности чисел Фибоначчи

Последовательность чисел Фибоначи — это последовательность, каждый элемент которой (кроме нулевого и первого) равен сумме двух предыдущих:

$$ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 , . $$

Числа Фибоначчи растут быстро: $f_<10>=55$, $f_<20>=6765$, а $f_<100>=354224848179261915075$.

Общая формула данной рекуррентной последовательности имеет вид6

Способ 1. Производящяя функция

Начинаем с второго шага алгоритма, домножаем на $z^n$:

$$\begin 1\cdot f_0 &= &0\cdot 1,\\ z\cdot f_1 &= &1\cdot z,\\ z\cdot f_n & = &(f_+f_)\cdot z^n, \quad n\geq2.\\ \end $$

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

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

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

Теперь разложим ее в степенной ряд. Для этого сначала разложим знаменатель на множители. Найдем корни уравнения:

Чтобы разложить данные дроби в ряды, используем известное разложение для дроби:

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на $z_1$:

Аналогично (но с делением на $z_2$) действуем со второй дробью:

Преобразуем данное выражение, используя то, что

$$1/z_1=-z_2, \quad 1/z_2 = -z_1, \quad z_1-z_2=\sqrt <5>$$ $$f_n=\frac<1><\sqrt<5>>\left( \biggl( \frac<1+\sqrt<5>> <2>\biggr)^n — \biggl( \frac<1-\sqrt<5>> <2>\biggr)^n \right). $$

Способ 2. Характеристическое уравнение

Запишем характеристический многочлен для $f_n=f_+f_$, и найдем его корни:

Тогда общее решение однородного рекуррентного уравнения имеет вид:

Осталось найти значения произвольных постоянных $C_1, C_2$ из начальных условий $f_0=0, f_1=1$.

Решая систему, найдем

Итоговое выражение для последовательности чисел Фибоначчи:

Результаты обоих методов совпали, решение вторым методом оказалось проще и короче.

Примеры решений

Задача 1. Решить рекуррентное соотношение $f(n+2)=-6f(n+1)+7f(n)+n-3$ с начальными условиями $f(0)=2$ и $f(1)=4$, сделать проверку

Задача 2. Решить рекуррентное соотношение $f(n+2)=-2f(n+1)+3f(n)-3^n$ с начальными условиями $f(0)=1$, $f(1)=3$ и сделать проверку

Задача 3. 1. Решить рекуррентное соотношение $f(n+2) =-5f(n+1) -4f(n) + 3n^2$ с начальными условиями $f(0) = 2$, $f(1) = 3$.
2. Проверить, удовлетворяет ли найденное решение начальным условиям и обращает ли оно рекуррентное соотношение в справедливое тождество.

Задача 4. Найти последовательность $$, удовлетворяющую рекуррентному соотношению $a_ + 4 a_ + 3 a_ = 0$ и начальным условиям $a_1=2$, $a_2=4$.

Источник

Дискретная математика — рекуррентное соотношение

В этой главе мы обсудим, как рекурсивные методы могут выводить последовательности и использоваться для решения задач подсчета. Процедура поиска членов последовательности рекурсивным способом называется рекуррентным отношением . Мы изучаем теорию линейных рекуррентных соотношений и их решения. Наконец, мы вводим производящие функции для решения рекуррентных отношений.

Определение

Рекуррентное отношение — это уравнение, которое рекурсивно определяет последовательность, в которой следующий член является функцией предыдущих членов (выражая F n как некоторую комбинацию F i с i n ).

Пример — ряд Фибоначчи — F n = F n − 1 + F n − 2 , Ханойская башня — F n = 2 F n − 1 + 1

Линейные рекуррентные отношения

Линейное рекуррентное уравнение степени k или порядка k — это рекуррентное уравнение в формате x n = A 1 x n − 1 + A 2 x n − 1 + A 3 x n − 1 + d o t s A k x n k ( A n — константа, а A k n e q 0 ) на последовательности чисел как полинома первой степени.

Вот некоторые примеры линейных рекуррентных уравнений —

Рецидив отношений	Начальные значения	Решения
F n = F n-1 + F n-2	a 1 = a 2 = 1	Число Фибоначчи
F n = F n-1 + F n-2	а 1 = 1, а 2 = 3	Номер Лукаса
F n = F n-2 + F n-3	a 1 = a 2 = a 3 = 1	Падовская последовательность
F n = 2F n-1 + F n-2	a 1 = 0, a 2 = 1	Число Пелла

Как решить линейное рекуррентное соотношение

Предположим, что два упорядоченных линейных рекуррентных соотношения имеют вид — F n = A F n − 1 + B F n − 2 , где A и B — действительные числа.

Характеристическое уравнение для вышеуказанного рекуррентного соотношения —

x 2 − A x e − B = 0

Три случая могут возникнуть при поиске корней —

Случай 1 — Если это уравнение учитывается как ( x − x 1 ) ( x − x 1 ) = 0 и оно дает два различных реальных корня x 1 и x 2 , то F n = a x n 1 + b x n 2 является решение. [Здесь a и b являются константами]

Случай 2 — Если это уравнение вычисляется как ( x − x 1 ) 2 = 0 , и оно порождает один действительный корень x 1 , то решением является F n = a x n 1 + b n x n 1 .

Случай 3 — Если уравнение дает два различных комплексных корня, x 1 и x 2 в полярной форме x 1 = r a n g l e t h e t a и x 2 = r a n g l e ( − t h e t a ) , то F n = r n ( a c o s ( n t h e t a ) + b s i n ( n t h e t a ) ) является решением.

Решите рекуррентное соотношение F n = 5 F n − 1 − 6 F n − 2 , где F 0 = 1 и F 1 = 4 .

Характеристическое уравнение рекуррентного соотношения —

Итак, ( x − 3 ) ( x − 2 ) = 0

x 1 = 3 и x 2 = 2

Корни реальны и различны. Итак, это в форме дела 1

F n = a x n 1 + b x n 2

Здесь F n = a 3 n + b 2 n ( A s x 1 = 3 a n d x 2 = 2 )

1 = F 0 = a 3 0 + b 2 0 = a + b

4 = F 1 = a 3 1 + b 2 1 = 3 a + 2 b

Решая эти два уравнения, мы получаем a = 2 и b = − 1

Следовательно, окончательное решение —

$$ F_n = 2,3 ^ n + (-1). 2 ^ n = 2,3 ^ n — 2 ^ n $$

Решите рекуррентное соотношение — F n = 10 F n − 1 − 25 F n − 2 , где F 0 = 3 и F 1 = 17 .

Характеристическое уравнение рекуррентного соотношения —

x 2 − 10 x − 25 = 0

Итак, ( x − 5 ) 2 = 0

Следовательно, существует один действительный корень x 1 = 5

Поскольку существует единый действительный корень, он имеет вид случая 2

F n = a x n 1 + b n x n 1

3 = F 0 = a .5 0 + b .0 .5 0 = a

17 = F 1 = a .5 1 + b .1 .5 1 = 5 a + 5 b

Решая эти два уравнения, мы получаем a = 3 и b = 2 / 5

Следовательно, окончательное решение — F n = 3.5 n + ( 2 / 5 ) . n .2 n

Решите рекуррентное соотношение F n = 2 F n − 1 − 2 F n − 2 , где F 0 = 1 и F 1 = 3

Характеристическое уравнение рекуррентного соотношения —

Источник

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

Содержание

Определения [ править ]

Определение:

Рекуррентная формула (англ. recurrence relation) — формула вида [math]a_n=f(n, a_, a_, \dots, a_ ) [/math] , выражающая каждый следующий член последовательности [math]a_n[/math] через [math]p[/math] предыдущих членов и номер члена последовательности [math]n[/math] , вместе с заданными первыми p членами, где [math]p[/math] — порядок рекуррентного соотношения.

Для рекуррентного соотношения, которому удовлетворяет последовательность [math] \ < a_n \>[/math] мы часто хотим получить выражение для [math]a_n[/math] . Например, для рекуррентного соотношения, задающего числа Фибоначчи:

[math] F_0 = 0,\qquad F_1 = 1,\qquad F_ = F_ + F_, \quad n\geqslant 2, \quad n\in Z[/math]

[math]a_n[/math] член может быть записан следующим образом: [math]a_n=\dfrac<1><\sqrt<5>>\left( \biggl( \dfrac<1+\sqrt<5>> <2>\biggr)^n — \biggl( \dfrac<1-\sqrt<5>> <2>\biggr)^n \right).[/math]

Для этого можно использовать метод производящих функций (англ. generating function method).

Метод производящих функций [ править ]

Алгоритм получения выражения для чисел [math]a_[/math] , удовлетворяющих рекуррентному соотношению, с помощью производящих функций cостоит из [math]4[/math] шагов.

1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен [math]k[/math] ): [math]a_ <0>= …, \\ a_ <1>= …, \\ a_ = …, \\ … \\ a_ = …, n\geqslant k[/math]
2. Домножить каждую строчку на [math]z[/math] в соответствующей степени ( [math]z^ \cdot a_ = … \cdot z^[/math] ) и сложить все выражения, многоточие надо рассматривать как множество из выражений, где [math]n \in [k, +\infty)[/math] . В левой части получится сумма [math]\displaystyle\sum_^ <\infty>a_nz^n[/math] — это производящая функция, назовем ее [math]G(z)[/math] . Правую часть преобразовать так, чтобы она превратилась в выражение, включающее [math]G(z)[/math] .
3. Решить полученное уравнение, получив для [math]G(z)[/math] выражение в замкнутом виде.
4. Разложить [math]G(z)[/math] в степенной ряд, коэффициент при [math]z_n[/math] будет искомым выражением для [math]a_n[/math] .

Примеры [ править ]

[math]1[/math] пример [ править ]

Производящие функции позволяют решать рекуррентные соотношение механически по одному и тому же алгоритму. Рассмотрим общую схему на простом примере, который позволит продемонстрировать базовые приёмы работы.

Задано линейное однородное рекуррентное соотношение порядка [math]2[/math] с постоянными коэффициентами:
[math]\begin a_0&<>=<>&0,\\ a_1&<>=<>&1,\\ a_n&<>=<>&5a_-6a_, \quad n\geqslant2.\\ \end [/math]

Порядок соотношения — это его «глубина», то есть количество предшествующих элементов, требуемых для вычисления элемента с номером [math]n[/math] . В данном случае порядок равен [math]2[/math] , так как для вычисления [math]a_n[/math] требуется знать [math]a_[/math] и [math]a_[/math] .

Будем искать производящую функцию последовательности в виде
[math] G(z)=\displaystyle\sum_^ <\infty>a_nz^n = a_0+a_1z+a_2z^2+\cdots, [/math]

с этой целью умножим верхнюю строчку в записи рекуррентного соотношения на [math]z^0[/math] , следующую — на [math]z^1[/math] и последнюю — на [math]z^n[/math] :
[math]\begin 1\cdot a_0&<>=<>&0\cdot 1,\\ z\cdot a_1&<>=<>&1\cdot z,\\ z^n\cdot a_n&<>=<>&(5a_-6a_)\cdot z^n, \quad n\geqslant2.\\ \end [/math]

Теперь сложим все уравнения для всех значений [math]n[/math] :
[math] \underbrace^<\infty>a_nz^n>_ <=>z+5\displaystyle\sum_^<\infty>a_z^n-6\displaystyle\sum_^<\infty>a_z^n. [/math]

Левая часть уравнения в точности равна [math]G(z)[/math] , а в правой части есть суммы, очень похожие на функцию [math]G(z)[/math] , но не равные ей. Эти суммы нужно привести к виду [math]G(z)[/math] . Начнём с первой:
[math] \displaystyle\sum_^<\infty>a_z^n \stackrel<(1)><=>z\displaystyle\sum_^<\infty>a_z^ \stackrel<(2)> <=>z\displaystyle\sum_^<\infty>a_z^n \stackrel<(3)> <=>z\biggr( \underbrace< \displaystyle\sum_^<\infty>a_z^n+a_0>_ — a_0\biggr)=z(G(z)-a_0) \stackrel<(4)> <=>z G(z). [/math]

Равенство [math](1)[/math] получатся вынесением [math]z[/math] в первой степени за знак суммы, это необходимо, чтобы уровнять степень переменной [math]z[/math] и индекс переменной a внутри суммы. Действие [math](2)[/math] — изменение индекса суммирования, которое позволяет избавиться от [math]n-1[/math] . Равенство [math](3)[/math] получается, если прибавить и снова отнять значение [math]a_0[/math] , чтобы получить полную сумму от [math]n=0[/math] до [math]∞[/math] . Равенство [math](4)[/math] справедливо в силу того, что [math]a_0=0[/math] .

Аналогичные манипуляции со второй суммой дают нам выражение
[math] \displaystyle\sum_^<\infty>a_z^n = z^2\displaystyle\sum_^<\infty>a_z^ = z^2\displaystyle\sum_^<\infty>a_z^=z^2G(z). [/math]

Теперь наше исходное уравнение для производящей функции принимает вид:
[math] G(z) = z + 5zG(z) -6z^2G(z), [/math]

откуда получаем производящую функцию последовательности в замкнутом виде:
[math] G(z) = \dfrac<1-5z+6z^2>. [/math]

Отыскав производящую функцию в замкнутом виде, её нужно снова разложить в ряд. Это можно сделать разными способами, но самый простой из них — разбить всю дробь на простые дроби и применить формулу для разложения [math]\dfrac<1><1-z>[/math] . Итак, разложим знаменатель функции на множители:
[math] G(z) = \dfrac <1-5z+6z^2>= \dfrac<(1-3z)(1-2z)>. [/math]

Теперь разобьём дробь на сумму простых дробей:
[math] \dfrac <(1-3z)(1-2z)>= \dfrac<1> <1-3z>— \dfrac<1><1-2z>. [/math]

Из этого разложения следует, что
[math] \dfrac<1><1-3z>= \displaystyle\sum_^<\infty>(3z)^n \quad\mbox< и >\quad \dfrac<1><1-2z>= \displaystyle\sum_^<\infty>(2z)^n. [/math]

Таким образом,
[math] G(z) = \displaystyle\sum_^<\infty>3^nz^n — \displaystyle\sum_^<\infty>2^nz^n = \displaystyle\sum_^<\infty>(3^n-2^n)z^n. [/math]

С другой стороны, мы искали [math]G(z)[/math] в виде
[math] G(z)=\displaystyle\sum_^ <\infty>a_nz^n, [/math]
поэтому, в силу равенства рядов, [math]a_n=3^n-2^n[/math] (для [math]n\geqslant 0[/math] ).

[math]2[/math] пример: числа Фибоначчи [ править ]

Рассмотрим рекуррентное соотношение для чисел Фибоначчи:
[math]\begin f_0&<>=<>&0,\\ f_1&<>=<>&1,\\ f_n&<>=<>&f_+f_, \quad n\geqslant2.\\ \end [/math]

Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
[math]\begin 1\cdot f_0&<>=<>&0\cdot 1,\\ z\cdot f_1&<>=<>&1\cdot z,\\ z^n\cdot f_n&<>=<>&(f_+f_)\cdot z^n, \quad n\geqslant2.\\ \end [/math]

Складываем все строчки:
[math] f_0 + f_1 z + \displaystyle\sum_^<\infty>f_nz^n = z + \displaystyle\sum_^<\infty>f_z^n+\displaystyle\sum_^<\infty>f_z^n. [/math]

Третий шаг алгоритма требует привести все суммы к замкнутому виду:
[math]\begin G(z) &<>=<>& z + z\displaystyle\sum_^<\infty>f_z^+z^2\displaystyle\sum_^<\infty>f_z^, \\ G(z) &<>=<>& z + z\displaystyle\sum_^<\infty>f_z^n+z^2\displaystyle\sum_^<\infty>f_z^n, \\ G(z)&<>=<>& \displaystyle z + z(G(z)-f_0)+z^2G(z),\\ G(z)&<>=<>& \displaystyle z + zG(z)+z^2G(z),\\ \end [/math]

откуда получаем замкнутое выражение для производящей функции:
[math] G(z) = \dfrac<1-z-z^2>. [/math]

Осталось разложить её в ряд (чего требует четвёртый шаг алгоритма). С этой целью нужно разложить знаменатель на множители. Найдем корни уравнения:
[math]\displaylines< 1-z-z^2 = 0 \cr z_1=-\dfrac<1-\sqrt<5>><2>, z_2=-\dfrac<1+\sqrt<5>><2>. > [/math]

Нам известно разложение следующей рациональной функции:
[math] \dfrac<1> <1-z>= \displaystyle\sum_^<\infty>z^n = 1 + z + z^2 + z^3 + \cdots. [/math]

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на [math]z_1[/math] :
[math] \dfrac = \dfrac1\dfrac<1><1-\dfrac> = \dfrac1\displaystyle\sum_^<\infty>\dfrac. [/math]

Аналогично (но с делением на [math]z_2[/math] ) поступим со второй дробью:
[math] \dfrac = \dfrac1\dfrac1<1-\dfrac> = \dfrac1\displaystyle\sum_^<\infty>\dfrac. [/math]

Данное выражение можно упростить, если обратить внимание на то, что [math]1/z_1=-z_2[/math] , [math]1/z_2=-z_1[/math] и [math]z_1-z_2=√5[/math] . Подставим [math]z_1[/math] и [math]z_2[/math] в предыдущее выражение:
[math] f_n=\dfrac<1><\sqrt<5>>\left( \biggl( \dfrac<1+\sqrt<5>> <2>\biggr)^n — \biggl( \dfrac<1-\sqrt<5>> <2>\biggr)^n \right). [/math]

[math]3[/math] пример [ править ]

Найдём производящую функцию для последовательности квадратов чисел Фибоначчи: $1, 1, 4, 9, 25, \ldots, f_k^2,\ldots$.

По определению последовательности Фибоначчи выполняется:
[math] \left\< \begin f_ = f_ + f_n \\ f_ = f_ — f_n \end \right. [/math]
Возведя в квадрат и сложив, получим:
[math] \begin f_^2 + f_^2 = 2f_^2 + 2f_n^2, \\ f_^2 = 2f_^2 + 2f_n^2 — f_^2, \\ f_^2 = 2f_^2 + 2f_^2 — f_^2.\\ \end [/math]
Обозначим рассматриваемую последовательность [math]A[/math] , а её члены [math]a_n[/math] , тогда:
[math]a_n = 2a_ + 2a_ — a_[/math]

Рекуррентное соотношение:
[math] \begin a_0 = f_0^2 = 1 \\ a_1 = f_1^2 = 1 \\ a_2 = f_2^2 = 4 \\ a_n = 2a_ + 2a_ — a_, \quad n\geqslant3.\\ \end [/math]

Приведём суммы к замкнутому виду:
[math] \begin A(z) = \displaystyle\sum_^<\infty>a_nz^n = 1 + z + 4z^2 + \displaystyle\sum_^<\infty>(2a_ + 2a_ — a_)z^n, \\ A(z) = 1 + z + 4z^2 + 2\displaystyle\sum_^<\infty>a_z^n + 2\displaystyle\sum_^<\infty>a_z^n — \displaystyle\sum_^<\infty>a_z^n, \\ A(z) = 1 + z + 4z^2 + 2z\displaystyle\sum_^<\infty>a_nz^n + 2z^2\displaystyle\sum_^<\infty>a_nz^n — z^3\displaystyle\sum_^<\infty>a_nz^n, \\ A(z) = 1 + z + 4z^2 + 2z(A(z) — 1 — z) + 2z^2(A(z) — 1) — z^3A(z), \\ A(z) = 1 + z + 4z^2 + 2zA(z) — 2z — 2z^2 + 2z^2A(z) — 2z^2 — z^3A(z), \\ A(z)(1 — 2z — 2z^2 + z^3) = 1 + z + 4z^2 — 2z — 2z^2 — 2z^2 = 1 — z, \\ \end [/math]
откуда получаем замкнутое выражение для производящей функции:
[math]G(z) = \dfrac<1 - z><1 - 2z 2z^2 + z^3>.[/math]

[math]4[/math] пример [ править ]

Рассмотрим следующее рекуррентное соотношение:
[math]\begin a_0&<>=<>&1,\\ a_1&<>=<>&2,\\ a_n&<>=<>&6a_-8a_+n, \quad n\geqslant2.\\ \end [/math]

Следующие действия аналогичны тем, которые мы делали для чисел Фибоначчи:
[math]\begin \displaystyle a_0 + a_1 z + \displaystyle\sum_^<\infty> &<>=<>& 1+2z+6\displaystyle\sum_^<\infty>>-8\displaystyle\sum_^<\infty>>+\displaystyle\sum_^<\infty>nz^n, \\ G(z) &<>=<>& 1+2z+6z\displaystyle\sum_^<\infty>>>-8z^2\displaystyle\sum_^<\infty>>>+\displaystyle\sum_^<\infty>nz^n, \\ G(z) &<>=<>& 1+2z+6z\displaystyle\sum_^<\infty>>>-8z^2\displaystyle\sum_^<\infty>>>+\displaystyle\sum_^<\infty>nz^n, \\ G(z) &<>=<> & 1+ 2z + 6z(G(z)-a_0)-8z^2G(z) + \displaystyle\sum_^<\infty>nz^n.\\ G(z) &<>=<> & 1 — 4z + 6zG(z)-8z^2G(z) + \displaystyle\sum_^<\infty>nz^n.\\ \end [/math]

Вспомним, что
[math] (z^n)’ = nz^, [/math]

поэтому
[math] \displaystyle\sum_^<\infty>nz^n=z\displaystyle\sum_^<\infty>nz^=z\displaystyle\sum_^<\infty>(z^n)’=z\biggl(\displaystyle\sum_^<\infty>z^n\biggr)’. [/math]

Последняя сумма может быть свёрнута:
[math] \displaystyle\sum_^<\infty>z^n=\displaystyle\sum_^<\infty>z^n-1-z=\dfrac<1><1-z>-1-z=\dfrac<1-z>. [/math]

Подставив свёрнутое выражение обратно, имеем,
[math] z\biggl(\displaystyle\sum_^<\infty>z^n\biggr)’ = z \biggl(\dfrac<1-z>\biggr)’=\dfrac<(1-z)^2>. [/math]

Таким образом, наше последнее уравнение примет вид
[math] G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \dfrac<(1-z)^2>.\\ [/math]

Это уравнение для производящей функции. Из него выражаем [math]G(z)[/math] :
[math] G(z) = \dfrac<1-6z+11z^2-5z^3><(1-6z+8z^2)(1-z)^2>. [/math]

Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
[math] \dfrac<1> <(1-z)^2>=(1-z)^ <-2>=\displaystyle\sum_^<\infty>\binom<-2>(-z)^n=\displaystyle\sum_^<\infty>(-1)^n\binom<1>(-z)^n =\displaystyle\sum_^<\infty>(n+1)z^n. [/math]

Источник