Site Overlay

离散数学:利用生成函数求解递推关系

生成函数:一种形式幂级数,其每一项可以提供关于这个序列的信息。

普通生成函数 $\sum_{n=0}^{\infty}a_nx^n$

简单序列的生成函数

$1, 1, \cdots$ 常数列:

$$
\sum_{n=0}^{\infty} x^{n}=\frac{1}{1-x}
$$

$1, a, a^2, a^3, \cdots$ 序列

$$
\sum_{n=0}^{\infty}(a x)^{n}=\frac{1}{1-a x}
$$

生成函数求解汉诺塔递推关系

【例子】已知汉诺塔的递推公式

$$
H_{n}=2 H_{n-1}+1, \quad n>1
$$

$H_{0}=0, H_{1}=1$

【分析与解答】

设其生成函数是:

$$
G(x)=\sum_{n \geq 0} H_{n} x^{n}
$$

带入递推公式,则:

$$
G(x) = H_0 +(2H_{0}+1)x +\cdots (2H_{n-1}+1)x^n + \cdots
$$

分离 $H_n$ 与常数 1:

$$
\begin{align}
G(x)=x^1 &+ x^2 + \cdots + x^n\\
&+ (H_0 + 2H_0+2H_1+\cdots+2H_{n-1})
\end{align}
$$

整理:

$$
G(x) = \sum_{1\to n}x^i + 2x\cdot G(x)
$$

$\sum x^i = \dfrac{1}{1-x} - 1 = \dfrac{x}{1-x}$

所以

$$
(1-2x)G(x) =\dfrac{x}{1-x}
$$

所以

$$
G(x) = \dfrac{x}{(1-x)(1-2x)}
$$

而上述

$$
\begin{array}{l}
G(x) &= \dfrac{1}{1-2x} - \dfrac{1}{1-x}\\
&=\left(1+2 x+2^{2} x^{2}+2^{3} x^{3}+\cdots+2^{n} x^{n}\right)-\left(1+x^{1}+x^{2}+\cdots+x^{n}\right) \\
&=\left(2^{1}-1\right) x+\left(2^{2}-1\right) x^{2}+\cdots\left({\color{blue}2^{n}-1}\right) x^{n}
\end{array}
$$

$$
H_n = 2^n - 1
$$

生成函数求解斐波那契数列

【例子】求解:$F_{n}=F_{n-1}+F_{n-2}(n \geq 2)$$F_{0}=0, F_{1}=1$

【分析与解答】

生成函数:

$$
\begin{align}
G(x) &= \sum_{n\geq0}F_nx^n\\&=\sum_{n\geq2}(F_{n-1}+F_{n-2})x^n\\
\end{align}
$$

注意到:

$$
\begin{align}
xG(x)&=\sum_{n\geq0}F_nx^{n+1} = \sum_{n\geq1}F_{n-1}x^{n} = \sum_{n\geq2}F_{n-2}x^{n}\\
x^2G(x)&=\sum_{n\geq0}F_nx^{n+2} = \sum_{n\geq2}F_{n-2}x^{n}
\end{align}
$$

从而

$$
G(x) = xG(x) +x^2G(x)
$$

即:

$$
G(x) = \dfrac{1}{1-x-x^2}
$$

假设

$$
\begin{align}
G(x) &= \dfrac{1}{Ax-B}+\dfrac{1}{Cx-D}\\
&= \dfrac{(A+C)x-(B+D)}{ACx^2-(BC+AD)x+BD}\\
&= \dfrac{1}{1-x-x^2}
\end{align}
$$

比较系数:

$$
\left\{
\begin{align}
A+C&=0\\
B+D &=-1\\
AC&=-1\\
BC+AD&=1\\
BD&=-1
\end{align}
\right.
$$

一组解是:$[A,C,B,D] = [1,-1,\dfrac{1+\sqrt{5}}{2},\dfrac{1-\sqrt{5}}{2}]$

而由高数所学,可知

$$
y = \dfrac{1}{a-x} = \dfrac{1}{a}\dfrac{1}{1-x/a} \sum (\dfrac{x^n}{a^{n+1}})
$$

则:

$$
\begin{align}
G(x) &=\dfrac{1}{x+B}+\dfrac{1}{x+D}\\
&=\sum (\dfrac{x^n}{B^{n+1}})+\sum (\dfrac{x^n}{D^{n+1}})\\
&= \sum(\dfrac{1}{B^{n+1}}+\dfrac{1}{D^{n+1}})x^n
\end{align}
$$

所以

$$
\begin{align}
F(x) &=\dfrac{1}{B^{n+1}}+\dfrac{1}{D^{n+1}}\\
&= \dfrac{1}{\sqrt{5}}(\dfrac{1+\sqrt{5}}{2})^{n+1} - (\dfrac{1-\sqrt{5}}{2})^{n+1}
\end{align}
$$

From:

https://slidesplayer.com/slide/15071940/

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注