Решение рекуррентных соотношений — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Метод производящих функций)
Строка 9: Строка 9:
 
<tex> f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n > 0 \end{cases}</tex>
 
<tex> f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n > 0 \end{cases}</tex>
  
может быть переведена в замкнутую форму: <tex>f = \frac{n(n+1)}{2}</tex>. Для этого можно использовать метод производящих функций.
+
может быть переведена в замкнутую форму: <tex>f = \dfrac{n(n+1)}{2}</tex>. Для этого можно использовать метод производящих функций.
  
 
==Метод производящих функций==
 
==Метод производящих функций==
Строка 58: Строка 58:
 
откуда получаем замкнутое выражение для производящей функции:
 
откуда получаем замкнутое выражение для производящей функции:
 
<br><tex>
 
<br><tex>
G(z) = \frac{z}{1-z-z^2}.
+
G(z) = \dfrac{z}{1-z-z^2}.
 
</tex><br>
 
</tex><br>
  
Строка 64: Строка 64:
 
<br><tex>\displaylines{
 
<br><tex>\displaylines{
 
1-z-z^2 = 0 \cr
 
1-z-z^2 = 0 \cr
z_1=-\frac{1-\sqrt{5}}{2}, z_2=-\frac{1+\sqrt{5}}{2}.
+
z_1=-\dfrac{1-\sqrt{5}}{2}, z_2=-\dfrac{1+\sqrt{5}}{2}.
 
}
 
}
 
</tex><br>
 
</tex><br>
Строка 70: Строка 70:
 
Таким образом,
 
Таким образом,
 
<br><tex>
 
<br><tex>
G(z) = \frac{z}{1-z-z^2}=\frac{-z}{(z_1-z)(z_2-z)}
+
G(z) = \dfrac{z}{1-z-z^2}=\dfrac{-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}.
+
\dfrac{z_1/(z_1-z_2)}{z_1-z} + \dfrac{z_2/(z_2-z_1)}{z_2-z}.
 
</tex><br>
 
</tex><br>
  
 
Нам известно разложение следующей рациональной функции:
 
Нам известно разложение следующей рациональной функции:
 
<br><tex>
 
<br><tex>
\frac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
+
\dfrac{1}{1-z} = \sum_{n=0}^{\infty}z^n = 1 + z + z^2 + z^3 + \cdots.
 
</tex><br>
 
</tex><br>
  
 
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <tex>z_1</tex>:
 
Рассмотрим первую дробь и поделим в ней числитель и знаменатель на <tex>z_1</tex>:
 
<br><tex>
 
<br><tex>
\frac{z_1/(z_1-z_2)}{z_1-z} = \frac1{z_1-z_2}\frac{1}{1-\frac{z}{z_1}} =
+
\dfrac{z_1/(z_1-z_2)}{z_1-z} = \dfrac1{z_1-z_2}\dfrac{1}{1-\dfrac{z}{z_1}} =
\frac1{z_1-z_2}\sum_{n=0}^{\infty}\frac{z^n}{z_1^n}.
+
\dfrac1{z_1-z_2}\sum_{n=0}^{\infty}\dfrac{z^n}{z_1^n}.
 
</tex><br>
 
</tex><br>
  
 
Аналогично (но с делением на <tex>z_2</tex>) поступим со второй дробью:
 
Аналогично (но с делением на <tex>z_2</tex>) поступим со второй дробью:
 
<br><tex>
 
<br><tex>
\frac{z_2/(z_2-z_1)}{z_2-z} = \frac1{z_2-z_1}\frac1{1-\frac{z}{z_2}} =
+
\dfrac{z_2/(z_2-z_1)}{z_2-z} = \dfrac1{z_2-z_1}\dfrac1{1-\dfrac{z}{z_2}} =
\frac1{z_2-z_1}\sum_{n=0}^{\infty}\frac{z^n}{z_2^n}.
+
\dfrac1{z_2-z_1}\sum_{n=0}^{\infty}\dfrac{z^n}{z_2^n}.
 
</tex><br>
 
</tex><br>
  
Строка 95: Строка 95:
 
<br><tex>
 
<br><tex>
 
G(z)=\sum_{n=0}^{\infty} f_nz^n =
 
G(z)=\sum_{n=0}^{\infty} f_nz^n =
\sum_{n=0}^{\infty}\biggr(\frac{1}{z_1-z_2}\frac{1}{z_1^n} + \frac{1}{z_2-z_1}\frac{1}{z_2^n} \biggr)z^n,
+
\sum_{n=0}^{\infty}\biggr(\dfrac{1}{z_1-z_2}\dfrac{1}{z_1^n} + \dfrac{1}{z_2-z_1}\dfrac{1}{z_2^n} \biggr)z^n,
 
</tex><br>
 
</tex><br>
  
 
и, следовательно,
 
и, следовательно,
 
<br><tex>
 
<br><tex>
f_n = \frac1{z_1-z_2}\frac{1}{z_1^n} + \frac1{z_2-z_1}\frac{1}{z_2^n}.
+
f_n = \dfrac1{z_1-z_2}\dfrac{1}{z_1^n} + \dfrac1{z_2-z_1}\dfrac{1}{z_2^n}.
 
</tex><br>
 
</tex><br>
  
 
Данное выражение можно упростить, если обратить внимание на то, что <tex>1/z_1=-z_2</tex>, <tex>1/z_2=-z_1</tex> и <tex>z_1-z_2=√5</tex>:
 
Данное выражение можно упростить, если обратить внимание на то, что <tex>1/z_1=-z_2</tex>, <tex>1/z_2=-z_1</tex> и <tex>z_1-z_2=√5</tex>:
 
<br><tex>
 
<br><tex>
f_n=\frac{1}{\sqrt{5}}\left( \biggl( \frac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \frac{1-\sqrt{5}}{2} \biggr)^n \right).
+
f_n=\dfrac{1}{\sqrt{5}}\left( \biggl( \dfrac{1+\sqrt{5}}{2} \biggr)^n - \biggl( \dfrac{1-\sqrt{5}}{2} \biggr)^n \right).
 
</tex><br>
 
</tex><br>
  
Строка 139: Строка 139:
 
Последняя сумма может быть свёрнута:
 
Последняя сумма может быть свёрнута:
 
<br><tex>
 
<br><tex>
\sum_{n=2}^{\infty}z^n=\sum_{n=0}^{\infty}z^n-1-z=\frac{1}{1-z}-1-z=\frac{z^2}{1-z}.
+
\sum_{n=2}^{\infty}z^n=\sum_{n=0}^{\infty}z^n-1-z=\dfrac{1}{1-z}-1-z=\dfrac{z^2}{1-z}.
 
</tex><br>
 
</tex><br>
  
 
Подставив свёрнутое выражение обратно, имеем,
 
Подставив свёрнутое выражение обратно, имеем,
 
<br><tex>
 
<br><tex>
z\biggl(\sum_{n=2}^{\infty}z^n\biggr)' = z \biggl(\frac{z^2}{1-z}\biggr)'=\frac{z^2(2-z)}{(1-z)^2}.
+
z\biggl(\sum_{n=2}^{\infty}z^n\biggr)' = z \biggl(\dfrac{z^2}{1-z}\biggr)'=\dfrac{z^2(2-z)}{(1-z)^2}.
 
</tex><br>
 
</tex><br>
  
 
Таким образом, наше последнее уравнение примет вид
 
Таким образом, наше последнее уравнение примет вид
 
<br><tex>
 
<br><tex>
G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \frac{z^2(2-z)}{(1-z)^2}.\\
+
G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \dfrac{z^2(2-z)}{(1-z)^2}.\\
 
</tex><br>
 
</tex><br>
  
 
Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:
 
Это уравнение для производящей функции. Из него выражаем <tex>G(z)</tex>:
 
<br><tex>
 
<br><tex>
G(z) = \frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}.
+
G(z) = \dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}.
 
</tex><br>
 
</tex><br>
  
 
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
 
Разложим знаменатель на множители и разобьём дробь на сумму простых дробей:
 
<br><tex>
 
<br><tex>
G(z) = \frac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\frac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}.
+
G(z) = \dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}.
 
</tex><br>
 
</tex><br>
  
 
Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
 
Дальше мы знаем что делать со всеми этими дробями, кроме, разве лишь, первой. Рассмотрим её (без множителя) подробнее:
 
<br><tex>
 
<br><tex>
\frac{1}{(1-z)^2} =(1-z)^{-2} =\sum_{n=0}^{\infty}\binom{-2}{n}(-z)^n=\sum_{n=0}^{\infty}(-1)^n\binom{n+1}{1}(-z)^n =\sum_{n=0}^{\infty}(n+1)z^n.
+
\dfrac{1}{(1-z)^2} =(1-z)^{-2} =\sum_{n=0}^{\infty}\binom{-2}{n}(-z)^n=\sum_{n=0}^{\infty}(-1)^n\binom{n+1}{1}(-z)^n =\sum_{n=0}^{\infty}(n+1)z^n.
 
</tex><br>
 
</tex><br>
  
 
Теперь соберём ответ:
 
Теперь соберём ответ:
 
<br><tex>
 
<br><tex>
G(z) = \frac{1/3}{(1-z)^2}+\frac{7/9}{1-z}-\frac{1/2}{1-2z}+\frac{7/18}{1-4z}=\frac{1}{3}\sum_{n=0}^{\infty}(n+1)z^n+
+
G(z) = \dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=\dfrac{1}{3}\sum_{n=0}^{\infty}(n+1)z^n+
\frac{7}{9}\sum_{n=0}^{\infty}z^n-\frac{1}{2}\sum_{n=0}^{\infty}2^nz^n+\frac{7}{18}\sum_{n=0}^{\infty}4^nz^n.
+
\dfrac{7}{9}\sum_{n=0}^{\infty}z^n-\dfrac{1}{2}\sum_{n=0}^{\infty}2^nz^n+\dfrac{7}{18}\sum_{n=0}^{\infty}4^nz^n.
 
</tex><br>
 
</tex><br>
  
Строка 176: Строка 176:
 
<br><tex>
 
<br><tex>
 
a_n=
 
a_n=
\frac{n+1}{3}
+
\dfrac{n+1}{3}
+\frac{7}{9}
+
+\dfrac{7}{9}
-\frac{2^n}{2}
+
-\dfrac{2^n}{2}
+\frac{7\cdot4^n}{18}=
+
+\dfrac{7\cdot4^n}{18}=
\frac{7\cdot4^n+6n+20}{18} - 2^{n-1}.
+
\dfrac{7\cdot4^n+6n+20}{18} - 2^{n-1}.
 
</tex><br>
 
</tex><br>
  

Версия 20:01, 16 марта 2018

Определения

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


Во многих задачах полезно знать, есть ли у рекурсивной функции нерекурсивная или как еще говорят «замкнутая» форма, т.е. получение [math]f(n)[/math] в виде аналитически заданной функции. Например, рекурсивная функция, описывающая сумму чисел натурального ряда:

[math] f = \begin{cases} f(0)=0; \\ f(n) = n + f(n-1),\quad n \gt 0 \end{cases}[/math]

может быть переведена в замкнутую форму: [math]f = \dfrac{n(n+1)}{2}[/math]. Для этого можно использовать метод производящих функций.

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

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

  1. Записать рекуррентное соотношение и начальные данные для него в следующем виде (если порядок соотношения равен [math]k[/math]):
    [math]a_{0} = …, \\ a_{1} = …, \\ a_{k-1} = …, \\ a_{n} = …, n\geq k[/math]
  2. Домножить каждую строчку на [math]z[/math] в соответствующей степени и просуммировать строчки для всех [math]n\geq0[/math].
  3. В полученном уравнении привести все суммы [math]∑[/math] к замкнутому виду. Получить уравнение для производящей функции.
  4. Выразить [math]G(z)[/math] в явном виде (решить уравнение, полученное на предыдущем шаге) и разложить производящую функцию в ряд по степеням [math]z[/math].

Примеры

Числа Фибоначчи

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

Первый шаг алгоритма мы уже выполнили, записав рекуррентное соотношение. Выполним второй шаг:
[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.\\ \end{array} [/math]

Складываем все строчки:
[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]

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

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

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

Рассмотрим первую дробь и поделим в ней числитель и знаменатель на [math]z_1[/math]:
[math] \dfrac{z_1/(z_1-z_2)}{z_1-z} = \dfrac1{z_1-z_2}\dfrac{1}{1-\dfrac{z}{z_1}} = \dfrac1{z_1-z_2}\sum_{n=0}^{\infty}\dfrac{z^n}{z_1^n}. [/math]

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

Таким образом,
[math] G(z)=\sum_{n=0}^{\infty} f_nz^n = \sum_{n=0}^{\infty}\biggr(\dfrac{1}{z_1-z_2}\dfrac{1}{z_1^n} + \dfrac{1}{z_2-z_1}\dfrac{1}{z_2^n} \biggr)z^n, [/math]

и, следовательно,
[math] f_n = \dfrac1{z_1-z_2}\dfrac{1}{z_1^n} + \dfrac1{z_2-z_1}\dfrac{1}{z_2^n}. [/math]

Данное выражение можно упростить, если обратить внимание на то, что [math]1/z_1=-z_2[/math], [math]1/z_2=-z_1[/math] и [math]z_1-z_2=√5[/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]\begin{array}{rcl} a_0&{}={}&1,\\ a_1&{}={}&2,\\ a_n&{}={}&6a_{n-1}-8f_{n-2}+n, \quad n\geq2.\\ \end{array} [/math]

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

Вспомним, что
[math] (z^n)' = nz^{n-1}, [/math]

поэтому
[math] \sum_{n=2}^{\infty}nz^n=z\sum_{n=2}^{\infty}nz^{n-1}=z\sum_{n=2}^{\infty}(z^n)'=z\biggl(\sum_{n=2}^{\infty}z^n\biggr)'. [/math]

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

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

Таким образом, наше последнее уравнение примет вид
[math] G(z) = 1 -4z + 6zG(z)-8z^2G(z) + \dfrac{z^2(2-z)}{(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] G(z) = \dfrac{1-6z+11z^2-5z^3}{(1-6z+8z^2)(1-z)^2}=\dfrac{1-6z+11z^2-5z^3}{(1-2z)(1-4z)(1-z)^2}=\dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}. [/math]

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

Теперь соберём ответ:
[math] G(z) = \dfrac{1/3}{(1-z)^2}+\dfrac{7/9}{1-z}-\dfrac{1/2}{1-2z}+\dfrac{7/18}{1-4z}=\dfrac{1}{3}\sum_{n=0}^{\infty}(n+1)z^n+ \dfrac{7}{9}\sum_{n=0}^{\infty}z^n-\dfrac{1}{2}\sum_{n=0}^{\infty}2^nz^n+\dfrac{7}{18}\sum_{n=0}^{\infty}4^nz^n. [/math]

Значит,
[math] a_n= \dfrac{n+1}{3} +\dfrac{7}{9} -\dfrac{2^n}{2} +\dfrac{7\cdot4^n}{18}= \dfrac{7\cdot4^n+6n+20}{18} - 2^{n-1}. [/math]

См. также

Источники информации