$\mathbf{OGF}$ 的定义

对于一个序列 $a_{1},a_{2},\cdots$，我们称：

$$G(x)=\sum_{i=0}^{\infty}a_{i}x^{i}$$

为序列 $a$ 的 $\mathbf{OGF}$ 即普通生成函数 ($\texttt{Ordinary Generating Function}$)。

同时因为我们不关心 $x$ 的取值，因此 $\sum_{i=1}^{+\infty}a_{i}x^{i}$ 又称作以 $x$ 为自由元的形式幂级数。 -- 摘自 自为风月马前卒

§ 一个例子

举个例子，序列：

$$\left(^{n}_{0}\right),\left(^{n}_{1}\right),\cdots,\left(^{n}_{n}\right)$$

的 $\mathbf{OGF}$ 为（二项式定理）：

$$G(x)=(1+x)^{n}$$

由等比数列求和公式，有一个常用的等式：

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

因为指数为 $\infty$，所以 $x^{\infty}$ 趋近于 $0$，箭头方向随便打，因为我们并不关心 $x$ 的取值。

即

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

这个等式还有一个重要的运用，我们把 $x$ 替换成 $kx$ 即可得：

$$\sum_{i=0}^{\infty}(kx)^{i}=\frac{1}{1-kx}$$

后文的用 $\mathbf{OGF}$ 求序列的通项公式里面这个东西很有用的。

$\texttt{Fibonacci}$ 序列的生成函数求法

定义一个序列

$$F_{i}=\begin{cases} 1,i\in[0,1] \\ \displaystyle F_{i-1}+F_{i-2},i\in[2,\infty) \end{cases}$$

则我们称 $F$ 为 $\texttt{Fibonacci}$ 序列。

接下来我们来推导其生成函数：

$$\begin{aligned} G(x)&=\sum_{i=0}^{\infty}F_{i}x^{i} \\ G(x)&=1+x+2x^{2}+3x^{3}+\cdots \\ xG(x)&=x+x^{2}+2x^{3}+3x^{4}+\cdots \\ x^{2}G(x)&=x^{2}+x^{3}+2x^{4}+3x^{5}+\cdots \end{aligned}$$

这里运用初中数学中经常用的到错位相减这一小技巧，可得

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

即可得

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

至此，我们已经求出了 $\texttt{Fibonacci}$ 序列的 $\mathbf{OGF}$ 了。

§ 利用生成函数求数列通项

以前文提到的 $\texttt{Fibonacci}$ 为例。

首先我们知道其 $\mathbf{OGF}$ 为：

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

待定系数一下分母我们就可以得到：

$$G(x)=\frac{1}{(1-\frac{1+\sqrt{5}}{2}x)(1-\frac{1-\sqrt{5}}{2}x)}$$

后面的还没推出来，咕了