美籍匈牙利数学家 乔治・波利亚 说过
‘母函数’这一名称由拉普拉斯命名。然而，欧拉在拉普拉斯之前很久就已使用母函数这一工具，却未赋予其名称…… 母函数是一种类似袋子的工具。我们不必零散地携带许多小物件（这会令人不便），而是将它们全部放入一个袋子中，这样我们只需携带一件物品 —— 这个袋子本身。
美国数学家 赫伯特・维尔夫 也说过
母函数是一列挂衣架，我们将一串数字挂在上面展示。这根单独的挂衣架容纳了序列的所有元素，以及关于它们的全部信息。
就连邻居家小狗也曾发表重要言论
汪汪！
由此可见母函数这一工具对于数列研究的普适和方便。
虽然母函数非常泛用，但对于研究以等差，等比数列为核心的高中数列来说，这个方法确实有些大炮打蚊子，操作稍显繁琐。所以对于高中数列，我们不一定要去实际使用此方法，而是将它视为理解正常研究方法本质的工具和一个最后手段。
一些概念和基础操作
母函数
母函数，或是生成函数，其实与其说是函数，更像是借用了 “函数” 的概念，具体来讲，假设有数列 \{a_n\} ，那么多项式
T(x)=\sum_{i=0}^{n}a_{i+1}x^i
可以认为是 \{a_n\} 的母函数。
（其实我偏向于 0-index，但因为 whk 里好像规定数列都是从一项开始，所以就用 1-index 吧。）
如果是无穷数列，
T(x)=\sum_{i=0}^\infty a_{i+1}x^i
基础操作
- 后移 k 项（空出来的用 0 补）：即
a_n \leftarrow \left\{ \begin{aligned} &0,\;\;\; n\leq k\\ &a_{n-k},\;\;\; n>k \end{aligned} \right.
对应到母函数 T 就是 T(x)\leftarrow x^kT(x) 。
- 前移 k 项（多出来的舍掉，有限数列超出范围可用 0 ）：即
a_n \leftarrow a_{n+k}
对应到母函数 T 就是 T(x)\leftarrow x^{-k}(T(x)-\sum_{i=1}^ka_ix^i) 。
- 求差分：即
a_n\leftarrow a_n-a_{n-1}
认为 a_0=0 。
可以通过 T(x)\leftarrow (1-x)T(x) 实现。
- 求前缀和：即
a_n\leftarrow \sum_{i=1}^n a_i
注意到差分是前缀和的逆运算，所以通过 T(x)\leftarrow \frac{1}{1-x}T(x) 实现。
- 给每项乘上下标：即
a_n\leftarrow na_n
发现对多项式求导可以干这件事，即：T(x)\leftarrow T'(x)
封闭形式
考虑一个母函数 T(x)=\lim_{n\rightarrow \infty}\sum_{i=0}^n x^i ，我们似乎可以对它使用等比数列的求和公式，即 T(x)=\frac{1-x^n}{1-x} ，因为 x 可以随便取（这里感觉并不严谨，只是我自己的理解），所以直接认为 x 是小于 1 的，那么 T(x)=\frac{1}{1-x} ，这样给 T 导出的一个像 \frac{1}{1-x} 这样简单的式子就管它叫 T(x) 的封闭形式。
下面列举一些可能会用到的常用数列的封闭形式：
- \{1,1,1,1\dots\} \rightarrow \sum_{i=0}^\infty x^i \rightarrow \frac{1}{1-x}
- \{1,q,q^2,q^3\dots\} \rightarrow \sum_{i=0}^\infty q^ix^i \rightarrow \frac{1}{1-qx}
- \{0,1,\frac{1}{2},\frac{1}{3}\dots\} \rightarrow \sum_{i=0}^\infty \frac{x^i}{i} \rightarrow \ln\frac{1}{1-x}
- \{1,1,\frac{1}{2!},\frac{1}{3!}\dots\} \rightarrow \sum_{i=0}^\infty \frac{x^i}{i!} \rightarrow e^x
（说实话感觉前两个就挺够用
应用
目前只想到了能用来求通项，如有更多用途欢迎补充。
求通项
- 例 1
a_1=4,a_{n+1}=3a_n+4 ，求 a_n 。
算是入门经典题了。
先讲一个自己瞎搞出来的与母函数无关的做法：
先考虑另一个问题：a_1=2,a_{n+1}=3a_n+2
将 a_n 放到 3 进制下考虑，不难发现：
\begin{aligned} &a_1=(2)_3\\ &a_2=(22)_3\\ &a_3=(222)_3\\ &\dots \end{aligned}
可直接得出 a_n=3^n-1
那么这个问题是 4 的版本，即
\begin{aligned} &a_1=(4)_3\\ &a_2=(44)_3\\ &a_3=(444)_3\\ &\dots \end{aligned}
（虽然 4>3 ，但因为是求和所以无所谓。
怎么干？
直接 \frac{4}{2}(3^n-1) 就好啦。
那么母函数怎么做呢？
设 {a_n} 的母函数是 T(x) ，对递推式进行变形：
\begin{aligned} a_{n+1}&=3a_n+4\\ a_{n+1}-3a_n-4&=0\\ \sum_{i=0}^\infty (a_{n+2}-3a_{n+1}-4)x^i&=0\\ \sum_{i=0}^\infty a_{n+2}x^i-3\sum_{i=0}^\infty a_{n+1}x^i-4\sum_{i=0}^\infty x^i&=0\\ \frac{(T(x)-a_1)}{x}-3T(x)-\frac{4}{1-x}&=0\\ \end{aligned}
最后得到：
T(x)=\frac{4}{(1-3x)(1-x)}
到这该怎么往下走呢？
我们发现，如果分母上是 (1-3x) 或 (1-x) ，其封闭形式我们是知道的，所以我们可以直接裂项：
\frac{4}{(1-3x)(1-x)}=\frac{6}{1-3x}+\frac{-2}{1-x}
（如果分子无法瞪出可以待定系数解方程组。
要求的通项 a_n 就是 T(x) 的 x^{n-1} 的系数，也就是 \frac{6}{1-3x} 的 x^{n-1} 的系数和 \frac{-2}{1-x} 的 x^{n-1} 的系数之和，可以从封闭形式直接推回数列对应项相加，就是 6\cdot 3^{n-1}-2\cdot 1^{n-1}=2(3^n-1) 。
提炼一下方法：根据递推式解出母函数式子 \rightarrow 将母函数变形为可以用已知数列的封闭形式搞出来的形式 \rightarrow 还原回数列，求 x^{n-1} 的系数。
- 例 2
求斐波那契数列的通项公式，f_{n+2}=f_{n+1}+f_{n},f_1=f_2=1 。
有了 1. 的经验，同样尝试表达 f 的母函数 T(x) 。
\begin{aligned} f_{n+2}-f_{n+1}-f_n&=0\\ \sum_{i=0}^\infty f_{i+3} x^i-\sum_{i=0}^\infty f_{i+2} x^i-\sum_{i=0}^\infty f_{i+1} x^i&=0\\ \frac{T(x)-f_1-xf_2}{x^2}-\frac{T(x)-f_1}{x}-T(x)&=0\\ T(x)&=\frac{1}{1-x-x^2} \end{aligned}
然后是变形，记 p,q 为方程 1-x-x^2=0 的两根。
\begin{aligned} T(x)&=\frac{1}{1-x-x^2}\\ &=\frac{1}{(p-x)(q-x)}\\ &=\frac{1}{q-p}\cdot \frac{1}{p-x}+\frac{1}{p-q}\cdot \frac{1}{q-x}\\ &=\frac{1}{q-p}\cdot \frac{p^{-1}}{1-p^{-1}x}+\frac{1}{p-q}\cdot \frac{q^{-1}}{1-q^{-1}x} \end{aligned}
最后一步转化回来，就是：
\begin{aligned} f_n&=\frac{1}{p^n(q-p)}+\frac{1}{q^n(p-q)} \end{aligned}
- 例3
有一数列 a_n=n2^n ，求其前缀和 S_n 的通项
（我从我们班作业里挑出来的一道题，官方解法是 2S_n-S_n 。
设 \{a_n\} 的母函数为 A， \{S_n\} 的母函数为 T 。
如果我们知道 a_n ，那么 S_n 的封闭形式就可以用 T(x)=\frac{1}{1-x}A(x) 来表达，所以先看看 A 的封闭形式。
在操作那一栏讲了，乘上下标可以用求导干，所以
\begin{aligned} A(x)&=\sum_{i=0}^\infty (i+1)2^{i+1}x^{i}\\ &=\big[\sum_{i=0}^\infty 2^{i+1}x^{i+1}\big]'\\ &=\big(\frac{1}{1-2x}\big)'\\ &=\frac{2}{(1-2x)^2} \end{aligned}
那么 T(x)=\frac{2}{(1-2x)^2(1-x)}
分母变为 3 次也没关系，裂项两次就行。得到 T(x)=\frac{1}{1-x}+\frac{-1}{1-2x}+\frac{4}{(1-2x)^2}
前两项正常干就行，第三项就是 2A(x) 。
可以得到： S_n=2-4\cdot 2^{n-1}+4\cdot n2^{n-1}=(n-1)2^{n+1}+2 。
从这里也能看出，如果知道一个数列的封闭形式，那么它的任意阶前缀和或差分都能被表达。
后记
其实生成函数还能用于许多组合计数问题，但感觉不在高考范围内所以没写。
乘上下标那个最开始我怎么想也想不出来，最后花了一节数学课才注意到它和导数的关系。
其实生成函数在我初中的博客亦有记载，只不过那时理解并不深，写的有很多错误，就弃了。