递推式（Recurrence）与生成函数（Generating Function）
前言
原文写于2014年3月22日。修订于2018年7月14日。
也是终于完成了这个系列第二篇，在寻找良好素材的时候也无意中发现了不少相关方面的优秀资料，一时兴起而做的决定为自己也带来了诸多益处，这实在令人欣慰.
用生成函数求解递推式是一个非常机械的过程，按照流程一步步做就能得到答案。不过大多数时候也并不像听上 去那么容易—如之前组合恒等式的证明那样，我们需要注意和处理令人厌烦的角标。
本文不期望读者能够掌握什么具体的知识，但如若能够为诸君于某刻解决问题时作一份参考，亦或是能有些许思路上的共鸣，之于我都将是莫大的荣誉。
0.符号约定
$[z^n]R(z)$意为多项式$R(z)$中$z^n$的系数。
我们以$<a_n>$作为数列$<a_1, a_2, \cdots, a_n, \cdots>$的缩写。
若$condition$为真，则我们有$[condition] = 1$，否则为$0$。
没有明确说明的情况下，$G(z),F(z)$意为数列$<g_n>,<f_n>$的生成函数。
1.定义与基本性质
一般来说，给定一个序列$<g_n>$，其生成函数(Ordinary Generating Function)$G(z)$定义如下：
\[G(z) = g_0 + g_1 z + g_2 z^2 + \cdots = \sum_{n \ge 0}^{\infty} g_n z^n\]尽管定义中的$z$并没有被指明是一个什么样的东西，它仅仅只是一个符号，或者某种特征的替代表示，但为了讨论方便，也为了迎合我们的需要，我们视$G(z)$为一个复变量的函数且$\lvert z \rvert <1$。
设$F(z),G(z)$分别为序列$<g_n>,<f_n>$的生成函数，通过一些简单的计算—加法，积分，数乘等，我们可以发现：
\[\alpha F(z) + \beta G(z) = \sum_n(\alpha f_n + \beta g_n)z^n\] \[z^mG(z) = \sum_n g_{n-m}z^n\] \[G(cz) = \sum_n c^n g_n z^n\] \[G'(z) = \sum_n (n+1) g_{n+1} z^n\] \[\int_0^z G(t)dt = \sum_{n \ge 1}{1 \over n}g_{n-1}z^n\] \[F(z)G(z) = \sum_n(\sum_k f_k g_{n-k})z^n\]最后一个等式看起来非常的熟悉，在样式上似乎是我们在前一篇所提到过的卷积，应用前面曾提到的些许结论，我们令数列$<f_k>$为$<1,1,\cdots>$，则可得到
\[\begin{align} (1 + z + z^2 + ...)G(z) &= \sum_n(\sum_{k \le n}g_k)z^n \\ \frac{1-z^n}{1-z}G(z) &= \sum_n(\sum_{k \le n}g_k)z^n \\ \frac{1}{1-z}G(z) &= \sum_n(\sum_{k \le n}g_k)z^n \end{align}\]这是一个非常有用的等式，他告诉我们用$1 \over 1-z$来乘以一个生成函数，会得到其数列的自累加的生成函数。
注意到我们这里用了一些幂级数的基本知识（即$F(x)$的计算部分），实际上，这也正是我们引入生成函数的原因—通过一些分析的手段去解决离散的，有关于数列的问题。
在这里我们不会用到什么深奥的幂级数知识，但即便如此，生成函数作为工具也已经十分强大。
简单的关于幂级数的知识可以让我们得到许多生成函数的封闭形式，例如调和数列$H_n = <0,1,{1 \over 2},{1 \over 3},{1 \over 4},\cdots>$的生成函数
\[\sum_{n \ge 1}{1 \over n}z^n = ln{1 \over 1-z}\]2.与递推式
我们希望借助幂级数来解决一些关于数列的问题，例如通过数列的递推式去求解通项公式，这也是我们引入生成函数的原因，那么它能够胜任么？
我们首先来看一个简单的例子。
ex.2.1 一个经典问题
假设我们有$n$个数$a_1,\cdots,a_n$，这$n$个数的乘积需要通过$n-1$次乘法来加以确定，因而我们要问，在乘积$a_1\cdots a_n$中有多少种插入括号的方法 $g_n$，使得乘法的次序被完全指定（我们假定交换律并不成立）。
我们这样来思考这个问题，我们为这$n$个数不断的添置括号（当然是合法的嵌套形式），直到置完成$n$个括号，这时候已经不存在游离于括号之外的因子，让我们来看看添置第$n-1$个括号的情形，由于在添置第$n-1$个括号之前我们已经添置了$n-2$个括号，由于每一个括号将两个因子（形式上的）“合成”了一个因子，在添置$n-2$个括号之后，$n$个因子必然已经被分裂成这样的形式$(a_1a_2\cdots a_k)(a_{k+1}\cdots a_n)$，进而我们就能够确定一个关于$g_n$的递推式
\[g_n = g_1g_{n-1}+g_2g_{n-2}+\cdots +g_{n-1}g_1 = \sum_{k=1}^{n-1} g_kg_{n-k}, n \ge 2, g_1 = 1\]由于递推式并没有$g_0$，因而生成函数以$g_1$作为第一项，即有
\[G(z) = g_1 + g_2z + \cdots = \sum_{k=1}^{\infty} g_k z^{k-1}\]数列$g_n$的递推式是一个卷积式，初看并没有什么头绪，不过我们可以做一些简单的尝试，很容易观察到，如果我们对$G(z)$进行平方，就能够得到$g_ig_j$此类的项。
\[\begin{align} G^2(z) &= g_1g_1 + g_1g_2z + g_2g_1z + \cdots + g_ng_nz^{2(n-1)} + \cdots \\ G^2(z) &= \sum_{k=1}^1 g_kg_{2-k} + \sum_{k=1}^2 g_kg_{3-k}z + \cdots + \sum_{k=1}^{n-1} g_kg_{n-k}z^{n-2} + \cdots \\ &= {1 \over z}(g_2z + \cdots g_nz^{n-1} + \cdots) \end{align}\]这样我们很容易就能看出
\[G(z) = zG^2(z) + g_1 = zG^2(z) + 1\]经由一些简单的代数运算，我们就能得到
\[G(z) = {1 - \sqrt {1-4z} \over 2z}\]实际上求解上面的代数方程我们会得到关于$G(z)$的两个封闭表达式，然而其中有一个在$z\rightarrow 0$时得到$\infty$，尽管我们没有定义$n=0$的情形，但是对于没有因子的情形，一个空的括号应该表示一种添置括号的方法，因而$G(0)=1$更加符合我们的逻辑。且有
\[\lim_{x \to 0} {1 - \sqrt {1-4z} \over 2z} = 1\]之后，只需要运用你在高数课上习得的知识，将$G(z)$展开为的某一幂级数的形式，其每一项的系数即为数列$<g_n>$的值。
ex.2.2 源于快速排序
我们都知道快排的平均时间复杂度是$O(nlog_2 n)$，对于这个结果的分析在许多算法相关的书籍上都有介绍，不过今天让我们来看看对于$n$个随机数进行快速排序总的比较次数的平均情况。
我们假设待排序数列为
\[a_1,\cdots,a_n\]选定枢纽元之后，设比枢纽元小的元素数量为$k$，由于数列完全随机，我们可以认为$k$是从$[1, n-1]$中均匀采样的。因此，令$n$个数进行快速排序总的比较次数$c_n$，我们能够建立如下递推式
\[c_n = n-1 + {1 \over n}\sum_{k=1}^{n}(c_k+c_{n-k}) = n-1 + {2 \over n}\sum_{k=1}^{n}c_k\]其中第一项的$n-1$为与枢纽元进行比较的开销，而$c_k$与$c_{n-k}$分别代表分割之后的子问题所对应的答案。 总的平均比较次数则为不同大小的子问题的平均比较数量。
令$C(z)$为$<c_n>$的生成函数，我们发现递推式中有一个自累加的项，因而结合第一节中的结论，我们有
\[\begin{align} C(z) &= c_1 + \sum_{n=2}^\infty (n-1 + {2 \over n}\sum_{k=1}^{n}c_k)z^{n-1} \\ C'(z) &= \sum_{n=2}^\infty ((n-1)n+2\sum_{k=1}^{n}c_k)z^{n-1} \\ &= \sum_{n=2}^\infty n(n-1)z^{n-1} + 2\sum_{n=2}^\infty \sum_{k=1}^{n} c_k z^{n-1}\\ &= z({1 \over 1-z})'' + {2C(z) \over 1-z}\\ &= {2z \over (1-z)^3} + {2C(z) \over 1-z} \end{align}\]求解这个微分方程,我们就能得到
\[C(z) = {-2ln(1-z)-2x \over (1-z)^2}\]来看看我们是怎么处理上面这个递推式的，在我们发现可能可以用到之前某些已经得到的结论的时候，${2 \over n}\sum_{k=1}^{n}c_k$项上的$1/n$就变成了最大的障碍，因此我们需要消除它，而对$C(z)$求导无疑就是最直接的选择。
ex.2.3 它看起来奇怪而熟悉
或许更多时候我们遇到的递推式会是这样的
\[a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1, a_0 = a_1 = 1, n \ge 2\]线性的递推项，和一个可能比较奇怪的尾项，运用我们之前所提到的技术，设$A(x)$为$<a_n>$的生成函数，则我们有
\[\begin{align} a_n-4 a_{n-1}+4 a_{n-2}&=n(n-1)2^{n-1}+1 \\ \sum_{n=2}^{\infty} (a_n-4 a_{n-1}+4 a_{n-2}) x^n &= \sum_{n=2}^{\infty} n(n-1)2^{n-1} x^n + \sum_{n=2}^{\infty} x^n \end{align}\]把边界加入进去，我们得到
\[\sum_{n=0}^{\infty} a_n x^n - (a_0+a_1x ) - 4 x \left (\sum_{n=0}^{\infty} a_n x^n - a_0\right ) + 4 x^2 \sum_{n=0}^{\infty} a_n x^n\] \[= (1-4 x+4 x^2)g(x) - (1+x) + 4 x\]再来看看右边的情况
\[\begin{align} \sum_{n=2}^{\infty} n(n-1)2^{n-1} x^n &= \frac{x^2}{2}\sum_{n=2}^{\infty} n(n-1)2^n x^{n-2} \\ &= \frac{x^2}{2} \frac{d^2}{dx^2} \frac{1}{1-2 x} \end{align}\]且有
\[\sum_{n=2}^{\infty} x^n = \frac{1}{1-x}-(1+x)\]因而我们得到
\[(1-4 x+4 x^2)g(x) - (1+x) + 4 x = \frac{4 x^2}{(1-2 x)^3} + \frac{1}{1-x} - (1+x)\] \[g(x) = \frac{1-10 x+44 x^2-84 x^3+80 x^4-32 x^5}{(1-x)(1-2 x)^3 (1-4 x+4 x^2)}\]这结果简直让人菊花一紧。
2.1 到此为止？
细心一点的读者可能发现，我们可能可以使用在算数・二项式系数与组合恒等式中提到的二项式定理来求解这个ex2.1，注意到
\[\sqrt{1-4z} = \sum_{k \ge 0}{1/2 \choose k}(-4z)^k =1+ \sum_{k \ge 1}{1 \over 2k}{-1/2 \choose k-1}(-4z)^k\]从而有
\[\begin{align} {1-\sqrt{1-4z} \over 2z} &= \sum_{k \ge 1}{1 \over k}{-1/2 \choose k-1}(-4z)^{k-1} \\ &=\sum_{n \ge 0}{-1/2 \choose n}{(-4z)^n \over n+1} \\ &= \sum_{n \ge 0}{2n \choose n}{z^n \over n+1} \end{align}\]因而得到
\[g_n = {2n \choose n}{1 \over n+1}\]而快速排序所得到的式子看起来更麻烦一些，因为其中有对数，但事实上这真是它简单的地方，因为我们知道
\[-ln(1-z) = \sum_k {z^k \over k}\]加以之前惯用的技术，我们有
\[\begin{align} C(z) &= {-2ln(1-z)-2x \over (1-z)^2} \\ & =\sum_{k \ge 2}\frac{2z^k}{k} \sum_{k \ge 0}(k+1)z^k \\ \end{align}\]经过略显繁琐的代数运算与系数比对，我们能够得到
\[c_n = 2(n+1)\sum_{k=1}^n {1 \over k} -4n = 2(n+1)H_n -4n\]这也揭示了快速排序的平均时间复杂度为$O(nlog_2 n)$。
3.一般策略
很多时候，将一个复杂的生成函数展开为幂级数形式是非常困难的，这让人感到沮丧。不过，通过上面的计算我们发现，我们能够经常得到一些形如$P(x)/Q(x)$，其中$P(x)$与$Q(x)$是两个多项式的生成函数。多项式经常是一种特殊的结构，那么在这里我们是否也有一些特殊的性质呢？
幸运的是，混凝土数学（《具体数学》 by Knuth）上，有一个如下叙述的定理：
若生成函数$R(z) = P(z)/Q(z)$，其中$Q(z) = q_0 (1-p_1z)^{d_1} \cdots (1-p_lz)^{d_l}$，$\{p_1,\cdots,p_l\}$是不同的实数，且有$degree(P(z)) < d_1 + \cdots + d_l$，则有
\[[z^n]R(z) = f_1(n)p_1^n + \cdots +f_l(n)p_l^n\ \forall n \ge 0\]其中$f_k(n)$是首项系数$a_k$满足以下等式的$d_k-1$次多项式
\[a_k = {P(1/p_k) \over (d_k-1)!q_0 \prod_{j \neq k}(1-p_j / p_k)^{d_j}}\]但书中并没有给出证明，因此我试着证明了一下。
在初等的代数书中介绍了多项式的带余除法的概念，借助带余除法，我们知道上述有理函数$R(z)$可以分解成以下形式
\[\begin{align} R(z) &= {P(x) \over {q_0 (1-p_1z)^{d_1} \cdots (1-p_lz)^{d_l}}} \\ &= {1 \over q_0}({A_1(z) \over (1-p_1z)^{d_1}}+\cdots+{A_l(z) \over (1-p_lz)^{d_l}}) \end{align}\]其中$A_k(z)$是低于$d_k$次的多项式。我们将上式通分，即可得到
\[\sum_j A_j(z) \prod_{k \neq j}(1-p_kz)^{d_k} = P(z)\] \[\Rightarrow \sum_j A_j(1/p_j) \prod_{k \neq j}(1-p_k/p_j)^{d_k} = P(1/p_j)\]由${1 \over 1-pz} = 1 + pz + \cdots + p^nz^n + \cdots$逐次微分，即可得到
\[\begin{align} \frac{(d_i-1)!}{(1-p_iz)^{d_i}} = (d_i-1)! + \cdots + (d_i+n-1)! p^n z^n + \cdots \\ \frac{1}{(1-p_i z)^{d_i}} = 1 + d_ipz + \cdots + \frac{d_i^{\overline n}}{n!} p^nz^n + \cdots \end{align}\]因而将
\[R(z) = \frac{1}{q_0}(\frac{A_1(z)}{(1-p_1z)^{d_1}}+\cdots+\frac{A_l(z)}{(1-p_lz)^{d_l}})\]逐项进行幂级数展开，则对于每一个展开式中的$z^n$项，其系数为
\[\frac{1}{q_0} A_k(z)\frac{d_k^{\overline n}}{n!}p_k^n\]即
\[\frac{1}{q_0} \frac{1}{(d_k-1)!} A_k(z)\frac{(d_k+n-1)!}{n!}p_k^n\]因而我们能够知道其系数$f_k(n)$是一个次数为$d_k-1$的关于n的多项式。则其首项系数(即 $n^{d_k-1}$的系数)$a_k$为
\[\frac{1}{q_0} \frac{1}{(d_k-1)!}A_k(z)\]而由
\[\sum_j A_j(1/p_j) \prod_{k \neq j}(1-p_j/p_k)^{d_j} = P(1/p_j)\]可以看出，对于每一个确定的$p_j$，含有$A_k\ k \neq j$项的连乘因子中必有取$z=p_j$的项， 使得乘积为0，因而有
\[A_j(1/p_j) = \frac{P(1/p_j)}{\prod_{k \neq j}(1-p_j/p_k)^{d_j}}\]最终在
\[\frac{1}{q_0} \frac{1}{(d_k-1)!}A_k(z)\]取$z=1/p_k$，得到
\[a_k =\frac{P(1/p_k)}{(d_k-1)!q_0 \prod_{j \neq k}(1-p_j / p_k)^{d_j}}\]我们来简单演示一下这个定理的用法，譬如递推式
\[g_n=g_{n-1}+2g_{n-2}+(-1)^n[n\ge 0]+[n=1]\]我们很容易就可求得其生成函数是
\[G(z) = {1+z+z \over (1-2z)(1+z)^2}\]所以根据定理,我们知道对于某个常数$c$，有
\[g_n = a_1 2^n + (a_2 n+c)(-1)^n\]其中
\[a_1 = {1+1/2+1/4 \over (1+1/2)^2} = 7/9, a_2 = {1-1+1 \over 1-2/(-1)} = 1/3\]再将$n=0$的情形代入，即可得到通项公式为
\[g_n = {7 \over 9}2^n +({1 \over 3}n + {2 \over 9})(-1)^n\]4.后记
生成函数是一项非常实用的工具，在这里我仅仅介绍了其冰山一角。更多的有关于生成函数的知识，只有等到我们遇到相关问题之时再做介绍了。
在这篇部分问题的解答过程中，我也曾走入歧途，一度执迷于创造新奇的方法而忽略了现有的工具，于定理证明上挣扎许久。实际上，如果你无法解出一个问题，那么要么是有一个更简单的问题你未能解决，要么是你仍有工具还未使用。