生成函数
普通生成函数（ordinary generating function，OGF）
定义序列 \(a\) 的普通生成函数为：
\[F(x) = \sum_n a_n x^n \]\(a\) 既可以是有穷序列，也可以是无穷序列。
例子：
1、序列 \(a=\langle 1,2,3\rangle\) 的 OGF 为 \(1 + 2x + 3x^2\)；
2、序列 \(a=\langle 1,1, 1, \cdots\rangle\) 的 OGF 为 \(\sum_{n=0}x^n\)；
封闭形式
在运用生成函数的过程中，我们不会一直使用形式幂级数的形式，而会适时地转化为封闭形式以更好地化简。
例子：
1、序列 \(a=\langle 1,1, 1, \cdots\rangle\) 的 OGF 的封闭形式为：
\[xF(x)+1=F(x) \\ F(x) = \frac{1}{1-x} \]2、序列 \(a=\langle a,a, a, \cdots\rangle\) 的 OGF 的封闭形式为：
\[xF(x)+a=F(x) \\ F(x) = \frac{a}{1-x} \]3、序列 \(a=\langle 1,p, p^2, \cdots\rangle\) 的 OGF 的封闭形式为：
\[pxF(x)+1=F(x) \\ F(x) = \frac{1}{1-px} \]4、序列 \(a=\langle \binom{m}{0},\binom{m}{1}, \binom{m}{2}, \cdots\rangle\) 的 OGF 的封闭形式为：
\[F(x)=\sum_{n=0}^m\binom{m}{n}x^n=(1+x)^m \]斐波那契数列的生成函数
斐波那契数列定义为：
\[a_0=0 \\ a_1 = 1 \\ a_n = a_{n-1} + a_{n-2} (n \geq 2) \]斐波那契数列 \(a=\langle 0, 1, 1, 2, \cdots\rangle\) 的 OGF 的封闭形式为：
\[F(x)=xF(x)+x^2F(x)+x \\ F(x) = \frac{x}{1-x-x^2} \]现在需要额外思考的是，如何将 \(F(x)\) 从封闭形式再一次转化为形式幂级数的形式，进而求出斐波那契的通项公式。
考虑求解一个待定系数的方程：
\[\frac{A}{1-ax}+\frac{B}{1-bx}= \frac{x}{1-x-x^2} \]通分得到：
\[\frac{A-Abx+B-aBx}{(1-ax)(1-bx)} = \frac{x}{1-x-x^2} \]待定项系数相等，我们得到：
\[\begin{cases} A+B=0\\ -Ab-aB=1\\ a+b=1\\ ab=-1 \end{cases} \]解得：
\[\begin{cases} A=\frac{1}{\sqrt{5}}\\ B=-\frac{1}{\sqrt{5}}\\ a=\frac{1+\sqrt{5}}{2}\\ b=\frac{1-\sqrt{5}}{2} \end{cases} \]得到斐波那契数列的通项公式：
\[\frac{x}{1-x-x^2}=\sum_{n\ge 0}x^n \frac{1}{\sqrt{5}}\left( \left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n \right) \]基本运算
加减
考虑两个序列 \(a,b\) 的普通生成函数，分别为 \(F(x),G(x)\)。那么有：
\[F(x)\pm G(x)=\sum_n (a_n\pm b_n)x^n \]因此 \(F(x)\pm G(x)\) 是序列 \(\langle a_n\pm b_n\rangle\) 的普通生成函数。
乘法
考虑乘法运算，也就是卷积：
\[F(x)G(x)=\sum_n x^n \sum_{i=0}^na_ib_{n-i} \]因此 \(F(x)G(x)\) 是序列 \(\langle \sum_{i=0}^n a_ib_{n-i} \rangle\) 的普通生成函数。
若令 \(G(x) = \frac{1}{1-x}\)，那么 \(F(x)G(x)\) 所对应的序列为序列 \(a\) 的前缀和序列。
其他
\(x F(x)\) 对应的序列为序列 \(a\) 右移一位后所对应的序列。
\(\frac{F(x)-a_0}{x}\) 对应的序列为序列 \(a\) 左移一位后所对应的序列。
标签：langle,frac,函数,sum,生成,序列,rangle,OGF From： https://www.cnblogs.com/chzhc-/p/18381470