$\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)} $$
~后面的还没推出来，咕了~