生成函数：一种形式幂级数，其每一项可以提供关于这个序列的信息。
普通生成函数 $\sum_{n=0}^{\infty}a_nx^n$
简单序列的生成函数
$1, 1, \cdots$ 常数列：
$$
\sum_{n=0}^{\infty} x^{n}=\frac{1}{1-x}
$$
\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}
$$
\sum_{n=0}^{\infty}(a x)^{n}=\frac{1}{1-a x}
$$
生成函数求解汉诺塔递推关系
【例子】已知汉诺塔的递推公式
$$
H_{n}=2 H_{n-1}+1, \quad n>1
$$
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)=\sum_{n \geq 0} H_{n} x^{n}
$$
带入递推公式，则：
$$
G(x) = H_0 +(2H_{0}+1)x +\cdots (2H_{n-1}+1)x^n + \cdots
$$
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}
$$
\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)
$$
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}
$$
(1-2x)G(x) =\dfrac{x}{1-x}
$$
所以
$$
G(x) = \dfrac{x}{(1-x)(1-2x)}
$$
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}
$$
\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
$$
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}
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}
$$
\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) = xG(x) +x^2G(x)
$$
即：
$$
G(x) = \dfrac{1}{1-x-x^2}
$$
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}
$$
\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.
$$
\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}})
$$
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}
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}
$$
\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：