5 二项式系数 BINOMIAL COEFFICIENTS
Laoshan_PLUS
·
2024-09-03 19:08:31
·
科技·工程
5 二项式系数 BINOMIAL COEFFICIENTS
让我们小憩一会儿。对于包含底、顶、模、\varphi 函数以及 \mu 函数的和式，我们在前面几章里已经看到了其中之艰难。现在我们来研究二项式系数，事实证明它在应用中更加重要，又比所有其他的量更容易处理。
我们真幸运！
5.1 基本恒等式 BASIC IDENTITIES
符号 \dbinom nk 就是二项式系数，之所以这样称呼它，是因为在这一节后面我们要考察的一个重要的性质，即二项式定理。我们将此符号读作 “n 选取 k ”。这种常用说法来自于它的组合解释——它是从一个有 n 个元素的集合中选取 k 个元素作成子集的方法数。例如，我们可以用 6 种方式从集合 \{1,2,3,4\} 中选取两个元素，
也可以说成是 n 件物品中一次取 k 件的组合。
\{1,2\}~,\quad\{1,3\}~,\quad\{1,4\}~,\quad\{2,3\}~,\quad\{2,4\}~,\quad\{3,4\}~;
所以 \dbinom42=6 。
要用更熟悉的东西来表示数 \dbinom nk ，最容易的做法是，首先确定从有 n 个元素的集合中选取 k 个元素的序列 （而不是子集）的个数。对序列来说，要考虑元素的次序。我们利用在第 4 章里用过的相同方法来证明 n! 是 n 个物体的排列数。对该序列的第一个元素有 n 种选择；对第一个元素的每一种选择，对第二个元素有 n-1 种选择；如此下去，直到对第 k 个元素有 n-k+1 种选择，这总共给出 n(n-1)\cdots(n-k+1)=n^{\underline k} 种选择。由于每 k 个元素组成的子集都恰好有 k! 种不同的排序，所以序列 的个数对每一个子集 恰好计算了 k! 次。为得到答案，只需要直接用 k! 来除：
\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k(k-1)\cdots(1)}~.
例如，
\binom42=\frac{4\times3}{2\times1}=6~,
这与我们前面的计数吻合。
我们称 n 是上指标 （upper index），而称 k 是下指标 （lower index）。根据组合解释，指标仅限于取非负整数，因为集合的元素个数不为负数或者分数。但是，除了组合解释之外，二项式系数还有许多用途，所以我们要去掉对它的某些限制。事实表明，最有用的是允许上指标取任意的实数（甚至复数），下指标取任意的整数。这样一来，正式的定义就取如下的形式：
\binom rk=\begin{cases}\dfrac{r(r-1)\cdots(r-k+1)}{k(k-1)\cdots(1)}=\dfrac{r^{\underline k}}{k!}~,&\text{整数 }k\geqslant0~;\\[1ex]~0~,&\text{整数 }k<0~.\end{cases}\tag{5.1}
这一定义有若干值得关注的特点。首先，上指标称为 r ，而不是 n ；字母 r 强调这样的事实：这个位置上出现任意实数，二项式系数都是有意义的。例如 \dbinom{-1}3=(-1)(-2)(-3)/(3\times2\times1)=-1 。这里不存在组合解释，但是事实表明 r=-1 是一个重要的特殊情形。事实也表明，像 r=-1/2 这样的非整数指标是有用的。
第二，我们可以把 \dbinom rk 看成是关于 r 的一个 k 次多项式。我们将会看到，这种观点常常是有用的。
第三，我们并没有对非整数的下指标定义二项式系数。对此也可以给出一个合理的定义，但实际应用很少，我们把这种推广放到本章后面再给出。
最后的注记：我们在定义的右边给出了 “整数 k\geqslant0 ” 以及 “整数 k<0 ” 的限制。这样的限制会出现在我们要研究的所有恒等式中，从而使得可应用的范围清晰明了。一般来说，限制得越少越好，因为没有限制的恒等式是最有用的；再者，任何适用的限制都是该恒等式的重要部分。处理二项式系数时，暂时忽略难以记住的限制条件，再来检查违反了什么没有，这样做会更容易一些。但核查是必不可少的。
例如，几乎每一次我们遇到 \dbinom nn 时它都等于 1 ，所以我们可能会错误地认为它永远是 1 。但是仔细观察定义 (5.1) 就会明白，\dbinom nn 仅当 n\geqslant0 时才等于 1 （假设 n 是整数）；而当 n<0 时有 \dbinom nn=0 。这样的陷阱可以（也应该）使生活有点冒险性。
在得到用来驾驭二项式系数的恒等式之前，我们稍微观察一下较小的值。表 5-1 中的数构成了帕斯卡三角形 的开始部分，它是根据布莱士 · 帕斯卡（1623—1662）的名字命名的，因为他就此写了一部很有影响的专著。表中的空条目实际上是 0 ，因为 (5.1) 中的分子是零，例如 \dbinom12=(1\times0)/(2\times1)=0 。留出这些空条目是为了强调表中其余的数。
在中国，称它为贾宪三角形或者杨辉三角形。1050 ~ 1100 年，北宋数学家贾宪就发现了这个三角形，而南宋数学家杨辉则在它所著的《详解九章算法》（1261 年）一书中再次给出了这个三角形，并说明此图来自贾宪出版于 11 世纪的著作《释锁算术》。他们的发现都远早于帕斯卡（1623—1662）以及其他国家的数学家。帕斯卡在他所著的 Traité du triangle arithmétique （1655 年）一书中介绍了这个三角形（据说帕斯卡在 13 岁即 1636 年时就发现了这个三角形）。目前世界数学家已逐渐承认这一历史事实，并改称它为 “中国三角”。
在帕斯卡出生之前的许多世纪，二项式系数在亚洲就已经为人所熟知，不过他当时无法了解这一情形。
\def\arraystretch{1.25}\begin{matrix}\textbf{表 5-1}\qquad\textbf{帕斯卡三角形}\\\begin{array}{l|ccccccccccc}\hline\hline n\hspace{1.5em}&\dbinom n0&\dbinom n1&\dbinom n2&\dbinom n3&\dbinom n4&\dbinom n5&\dbinom n6&\dbinom n7&\dbinom n8&\dbinom n9&\dbinom n{10}\\\hline0&1\\1&1&1\\2&1&2&1\\3&1&3&3&1\\4&1&4&6&4&1\\5&1&5&10&10&5&1\\6&1&6&15&20&15&6&1\\7&1&7&21&35&35&21&7&1\\8&1&8&28&56&70&56&28&8&1\\9&1&9&36&84&126&126&84&36&9&1\\10&1&10&45&120&210&252&210&120&45&10&1\\\hline\hline\end{array}\end{matrix}
记住前三列的公式是有意义的
\binom r0=1~,\quad\binom r1=r~,\quad\binom r2=\frac{r(r-1)}2~,\tag{5.2}
这些公式对任意实数都成立。（记住：\dbinom{n+1}2=\dfrac12n(n+1) 是我们在第 1 章里对三角形数推导出来的公式；三角形数明白无误地出现在表 5-1 的 \dbinom n2 列中。）记住帕斯卡三角形的大约前五行是很好的，这样在当模式 1,4,6,4,1 出现在某个问题中时，我们就会得到线索：二项式系数可能就隐藏在附近。
在意大利，称它为 Tartaglia 三角形。
实际上，帕斯卡三角形中的数满足无穷多个恒等式，所以通过仔细观察就能发现某些令人惊讶的关系，这不足为奇。例如，有一个奇特的 “六边形性质”，它可以由表 5-1 中右下角处围绕 84 的六个数 56,28,36,120,310,216 来描述。由这个六边形的这些数交错相乘就得出相同的乘积：56\times36\times210=28\times120\times126=423~360 。如果我们从帕斯卡三角形的任何其他部分抽取这样一个六边形，同样的结论也成立。
“它有那么丰富的性质，这真是令人奇怪的事。” ——帕斯卡
现在讨论恒等式。这一节的目的是学习几个简单的法则，利用它们就能解决绝大多数与二项式系数有关的实际问题。
一般情形中可以根据阶乘来重新改写定义 (5.1) ，上指标 r 是整数 n ，它大于或等于下指标 k ：
\binom nk=\frac{n!}{k!(n-k)!}~,\quad\text{整数 }n\geqslant k\geqslant0~.\tag{5.3}
为了得到这个公式，我们只要用 (n-k)! 来乘 (5.1) 的分子和分母即可。有时候，将一个二项式系数展开成这种阶乘的形式是有用的，例如证明六边形性质时，我们则常常希望另辟蹊径，将阶乘改变成二项式系数。
阶乘表达式暗示在帕斯卡三角形中有对称性：每一行从左向右读和从右向左读都是相同的。反映出这个性质的恒等式称为对称 （symmetry）恒等式，可以通过将 k 改变成 n-k 得到：
\binom nk=\binom n{n-k}~,\quad\text{整数 }n\geqslant0~,\quad k\text{ 是整数.}\tag{5.4}
这个公式有组合意义，因为从 n 件物品中指定选取 k 件物品就相当于指定 n-k 件物品不被选取。
在恒等式 (5.4) 中，限制 n 和 k 为整数是显然的，因为每一个下指标必须是整数。但是为什么 n 不能是负数呢？例如，假设 n=-1 ，那么等式
\binom{-1}k\stackrel?=\binom{-1}{-1-k}
成立吗？不。例如，k=0 时左边得到 1 ，而右边得到 0 。事实上，对任何整数 k\geqslant0 ，左边都是
\binom{-1}k=\frac{(-1)(-2)\cdots(-k)}{k!}=(-1)^k~,
它或者是 1 ，或者是 -1 。所以等式 \dbinom{-1}k=\dbinom{-1}{-1-k} 总是错误的！
对称恒等式对所有其他的负整数 n 也都不成立。但是不幸的是，这个限制太容易被忘掉了，因为上指标中的表达式有时候仅仅对其变量的不明确（但合法的）值是负的。每一个处理过二项式系数的人都会掉进这个陷阱里，至少三次。
我只希望在期中考试时不要掉进这个陷阱里。
但是，对称恒等式的确有很大的可取之处：它对所有的 k 值，甚至对 k<0 或 k>n 都成立。（因为在这些情形下两边都为零。）反之，当 0\leqslant k\leqslant n 时，对称性立即由 (5.3) 推出：
\binom nk=\frac{n!}{k!(n-k)!}=\frac{n!}{\big(n-(n-k)\big)!(n-k)!}=\binom n{n-k}~.
下一个重要的恒等式，能让我们将一些东西移进或者移出二项式系数：
\binom rk=\frac rk\binom{r-1}{k-1}~,\quad\text{整数 }k\ne0~.\tag{5.5}
这里对 k 的这个限制，防止了用 0 做除数。我们把 (5.5) 称为吸收 （absorption）恒等式，因为一个变量在二项式系数的外面成为 “累赘” 时，我们常常利用这个恒等式把这个变量吸收到二项式系数的内部。由定义 (5.1) 可以推出这个等式，因为当 k>0 时有 r^{\underline k}=r(r-1)^{\underline{k-1}} 以及 k!=k(k-1)! ；而当 k<0 时两边都等于零。
如果用 k 乘以 (5.5) 的两边，就得到一个甚至在 k=0 时也成立的吸收恒等式：
k\binom rk=r\binom{r-1}{k-1}~,\quad k\text{ 是整数.}\tag{5.6}
这个恒等式也有一个保持下指标不变的相伴恒等式：
(r-k)\binom rk=r\binom{r-1}k~,\quad k\text{ 是整数.}\tag{5.7}
我们可以在两次应用对称性之间使用 (5.6) ，从而推导出 (5.7) ：
\begin{aligned}(r-k)\binom rk&=(r-k)\binom r{r-k}&&\text{（根据对称性）}\\&=r\binom{r-1}{r-k-1}&&\text{（根据 }(5.6)\text{）}\\&=r\binom{r-1}k~.&&\text{（根据对称性）}\end{aligned}
稍等一会儿。我们已经声称这个恒等式对所有实的 r 都成立，然而刚刚给出的推导却仅当 r 是正整数时成立。（如果我们打算安然无恙地利用对称性质 (5.4) ，上指标 r-1 必须是非负整数。）我们违背数学规则了吗？不。这一推导仅对正整数 r 成立，这一结论是正确的，但是我们可以断定，这个恒等式对 r 所有的值都成立，因为 (5.7) 的两边是关于 r 的 k+1 次多项式。一个非零的 d 次或更低次数的多项式至多能有 d 个不同的零点，因此两个这样的多项式（它们也有 d 次或者更低的次数）之差不可能在多于 d 个点处为零，除非这个差恒为零。换句话说，如果两个 d 次或更低次数的多项式在多于 d 个点处的值相同，那么它们必定处处取值相同。我们已经证明了，只要 r 是一个正整数，就有 (r-k)\dbinom rk=r\dbinom{r-1}k ，所以这两个多项式在无穷多个点处取相同的值，它们必定是完全相等的。
（是的，无论如何我们在这里没有违反数学规则。）
我们称上一段中陈述的证明方法为多项式推理法 （polynomial argument），这一方法对于将许多恒等式从整数推广到实数的情形都是有用的，我们将会多次看到它。某些等式，像对称式 (5.4) ，并不是多项式之间的恒等式，所以我们不可能利用这个方法。但是有一些恒等式的确有所需要的形式。
例如这里的另一个多项式恒等式，它几乎是最为重要的二项恒等式，称为加法公式 （addition formula）：
\binom rk=\binom{r-1}k+\binom{r-1}{k-1}~,\quad k\text{ 是整数.}\tag{5.8}
当 r 是正整数时，加法公式告诉我们：帕斯卡三角形中的每一个数都是它上一行中两个数的和，其中一个数直接在它的上方，另一个则恰好在它的左边。当 r 是负数、实数或者复数时这个公式仍然适用，仅有的限制是 k 是一个整数，这就使得这些二项式系数是有定义的。
证明加法公式的一种方法是假设 r 是一个正整数并利用组合解释。回想一下，\dbinom rk 是从一个有 r 个元素的集合中选取可能的 k 个元素的子集的个数。如果我们有 r 个鸡蛋组成的集合，它恰好包含一个坏的鸡蛋，那么就有 \dbinom rk 种方式选取 k 个鸡蛋。这些选取方法中恰好有 \dbinom{r-1}k 种只选好的鸡蛋，而其中 \dbinom{r-1}{k-1} 种选取方法则都含有那个坏的鸡蛋，因为这样的选法是从 r-1 个好鸡蛋中选取 k-1 个。把这两个数加在一起就给出 (5.8) 。这个推导假设了 r 是正整数，且 k\geqslant0 。但是当 k<0 时这个恒等式的两边都是零，多项式推理法就在所有剩下的情形确立了 (5.8) 的正确性。
我们还可以通过将两个吸收恒等式 (5.7) 和 (5.6) 相加来导出 (5.8) ：
(r-k)\binom rk+k\binom rk=r\binom{r-1}k+r\binom{r-1}{k-1}~,
左边是 r\dbinom rk ，我们用 r 来除整个等式。这个推导对除了 r=0 之外的每个值都成立，而剩下的情形也容易验证。
我们当中那些不大可能发现这种巧妙证明的人，或者是那些感到厌倦的人，或许更愿意直接用定义来得出 (5.8) 。如果 k>0 ，则有
\begin{aligned}\binom{r-1}k+\binom{r-1}{k-1}&=\frac{(r-1)^{\underline k}}{k!}+\frac{(r-1)^{\underline{k-1}}}{(k-1)!}\\&=\frac{(r-1)^{\underline{k-1}}(r-k)}{k!}+\frac{(r-1)^{\underline{k-1}}k}{k!}\\&=\frac{(r-1)^{\underline{k-1}}r}{k!}=\frac{r^{\underline k}}{k!}=\binom rk~.\end{aligned}
这里 k\leqslant0 的情形仍然容易处理。
我们刚刚看到了加法公式的三种截然不同的证明。这并不令人惊讶，二项式系数有许多有用的性质，其中有一些必定会用来导出某个恒等式的证明。
加法公式本质上是关于帕斯卡三角形中的数的递归式，所以我们将会看到，它对用归纳法证明其他的恒等式是特别有用的。将这个递归式展开，我们还能立即得到一个新的恒等式。例如，
\begin{aligned}\binom53&=\binom43+\binom42\\&=\binom43+\binom32+\binom31\\&=\binom43+\binom32+\binom21+\binom20\\&=\binom43+\binom32+\binom21+\binom10+\binom1{-1}~.\end{aligned}
由于 \dbinom1{-1}=0 ，这一项就消失了，我们可以停止。这一方法导出了下面的一般的公式
\begin{align}\sum_{k\leqslant n}\binom{r+k}k&=\binom r0+\binom{r+1}1+\cdots+\binom{r+n}n\notag\\&=\binom{r+n+1}n~,\quad n\text{ 是整数.}\tag{5.9}\end{align}
注意，在求和的指标中我们不需要下限 k\geqslant0 ，因为 k<0 的项都是零。
这个公式将一个二项式系数表示成其他的那些上下指标保持同样差距的二项式系数之和。我们可以通过反复展开具有最小下指标的二项式系数来求出它：首先是 \dbinom53 ，然后是 \dbinom42 ，再后是 \dbinom31 ，接下来是 \dbinom20 。如果我们用另一种方法展开，即反复展开具有最大下指标的项，又会发生什么呢？我们得到
\begin{aligned}\binom53&=\binom43+\binom42\\&=\binom33+\binom32+\binom42\\&=\binom23+\binom22+\binom32+\binom42\\&=\binom13+\binom12+\binom22+\binom32+\binom42\\&=\binom03+\binom02+\binom12+\binom22+\binom32+\binom42~.\end{aligned}
现在 \dbinom03 是零（\dbinom02 和 \dbinom12 亦然，但保留它们使得该恒等式更为妥帖），我们就能联想到一般的模式：
\begin{align}\sum_{0\leqslant k\leqslant n}\binom km&=\binom0m+\binom1m+\cdots+\binom nm\notag\\&=\binom{n+1}{m+1}~,\quad\text{整数 }m,n\geqslant0~.\tag{5.10}\end{align}
这个恒等式称为关于上指标求和 （summation on the upper index），它将一个二项式系数表示成为那些下指标是常数的二项式系数之和。在这种情形，和式要求下限 k\geqslant0 ，因为 k<0 的项不是零。同样地，一般来说 m 和 n 不可能是负数。
恒等式 (5.10) 有一个有趣的组合解释。如果我们想要从一个有 n+1 张票（标号从 0 直到 n ）的集合中选取 m+1 张票，当选取的最大号码是数 k 时就有 \dbinom km 种取法。
我们可以利用加法公式，通过归纳法来证明 (5.9) 和 (5.10) ，我们也可以由它们相互给出证明。例如，我们来从 (5.10) 证明 (5.9) ，我们的证明将描述某些二项式系数的共同处理方法。总的计划是：处理 (5.9) 的左边 \sum\dbinom{r+k}k ，从而使得它看起来像 (5.10) 的左边 \sum\dbinom km ；然后使用那个恒等式，用一个单独的二项式系数代替这个和式；最后将那个系数变换成 (5.9) 的右边。
为方便起见，我们可以假设 r 和 n 是非负整数，利用多项式推理法，(5.9) 的一般情形可以从这个特殊情形得出。我们用 m 代替 r ，使得这个变量看起来更像是一个非负整数。现在可以将此计划系统地执行如下：
\begin{aligned}\sum_{k\leqslant n}\binom{m+k}k&=\sum_{-m\leqslant k\leqslant n}\binom{m+k}k\\&=\sum_{-m\leqslant k\leqslant n}\binom{m+k}m\\&=\sum_{0\leqslant k\leqslant m+n}\binom km\\&=\binom{m+n+1}{m+1}=\binom{m+n+1}n~.\end{aligned}
我们来非常仔细地观察这个推导。关键的一步在于第二行，这里我们应用对称法则 (5.4) ，用 \dbinom{m+k}m 代替了 \dbinom{m+k}k 。仅当 m+k\geqslant0 时才可以这样做，所以第一步将 k 的范围限制在去掉 k<-m 的项。（这是合法的，因为去掉的那些项都是零。）现在可以差不多应用 (5.10) 了，第三行对此进行准备，用 k-m 代替 k 并对求和范围进行了整理。这一步像第一步一样，仅仅对 \Sigma 符号做了点小小的变形。现在 k 本身已经出现在上指标中，而且求和的界限也已表示成合适的形式，故而第四行就应用 (5.10) 。再用一次对称性就完成了任务。
在第 1 章以及第 2 章里，我们处理过的某些和式实际上是 (5.10) 的特殊情形，或者是这个恒等式的 “变脸”。例如，m=1 的情形给出直到 n 的非负整数之和：
\binom01+\binom11+\cdots+\binom n1=0+1+\cdots+n=\frac{(n+1)n}2=\binom{n+1}2~.
而如果用 m! 来除这个公式的两边，一般的情形与第 2 章里的法则
\sum_{0\leqslant k\leqslant n}k^{\underline m}=\frac{(n+1)^{\underline{m+1}}}{m+1}~,\quad\text{整数 }m,n\geqslant0
等价。事实上，如果分别用 x+1 和 m 代替 r 和 k ，由加法公式 (5.8) 知
\Delta\hspace{-0.1em}\Bigg(\hspace{-0.25em}\binom xm\hspace{-0.25em}\Bigg)=\binom{x+1}m-\binom xm=\binom x{m-1}~,
于是，第 2 章里的方法给我们提供了方便适用的不定求和公式
\sum\binom xm\delta x=\binom x{m+1}+C~.\tag{5.11}
二项式系数是因为二项式定理 （binomial theorem）得名的，二项式定理处理二项式 x+y 的幂。我们来观察这个定理的最小的一些情形：
“在 21 岁时，他（莫里亚蒂）写了一部有关二项式定理的专著，这部书在欧洲风行一时。由于这部书带来的声望，他在我们一所较小的大学获得了数学职位。” ——夏洛克 · 福尔摩斯
\begin{aligned}(x+y)^0&=1x^0y^0\\(x+y)^1&=1x^1y^0+1x^0y^1\\(x+y)^2&=1x^2y^0+2x^1y^1+1x^0y^2\\(x+y)^3&=1x^3y^0+3x^2y^1+3x^1y^2+1x^0y^3\\(x+y)^4&=1x^4y^0+4x^3y^1+6x^2y^2+4x^1y^3+1x^0y^4\end{aligned}
不难看出这些系数为什么与帕斯卡三角形中的数相同：当我们将乘积
(x+y)^n=\overbrace{(x+y)(x+y)\cdots(x+y)}^{n\text{个因子}}
展开时，每一项本身都是 n 个因子的乘积，这里的因子或者是 x ，或者是 y 。有 k 个因子 x 和 n-k 个因子 y 的项的个数就是合并同类项之后 x^ky^{n-k} 的系数。这恰好就是从 n 个二项式中选取 k 个（它们都提供一个 x ）的方法数，也就是说，它等于 \dbinom nk 。
某些教科书没有定义量 0^0 ，因为当 x 递减地趋向于零时，函数 x^0 与 0^x 有不同的极限值。但是，这是一个错误。如果我们打算让二项式定理在 x=0 ，y=0 以及 x=-y 时成立，必须定义
x^0=1~,\quad\text{对所有 }x~.
这个定理太重要了，我们不能对它随意加以限制！相比之下，函数 0^x 就不那么重要了。（进一步的讨论见参考文献[220]。）
确切地说，二项式定理究竟是什么呢？它最一般性的结果是下面的恒等式：
(x+y)^r=\sum_k\binom rkx^ky^{r-k}~,\quad\text{整数 }r\geqslant0\text{ 或者 }|x/y|<1~.\tag{5.12}
这个和式对所有的整数 k 求和，但是，当 r 是一个非负整数时，它实际上是一个有限和式，因为除了 0\leqslant k\leqslant r 的那些项之外，其他所有的项都等于零。另一方面，当 r 是负数或者是一个任意（不是非负整数的）实数或复数时，这个定理也成立。在这种情形下，和式实际上是无限的，我们必须有 |x/y|<1 以确保该和式绝对收敛。
二项式定理的两个特殊情形尽管极其简单，但特别值得关注。如果 x=y=1 且 r=n 是非负的，我们就得到
2^n=\binom n0+\binom n1+\cdots+\binom nn~,\quad\text{整数 }n\geqslant0~.
这个等式告诉我们，帕斯卡三角形的第 n 行的和是 2^n 。而当 x 是 -1 而不是 +1 时，我们得到
0^n=\binom n0-\binom n1+\cdots+(-1)^n\binom nn~,\quad\text{整数 }n\geqslant0~.
例如，1-4+6-4+1=0 。除了最上面一行（此时 n=0 ，0^0=1 ），如果它们的符号是交错的，则第 n 行的和为零。
当 r 不是非负整数时，我们最常在 y=1 这一特殊情形使用二项式定理。我们来将这一特殊情形明确地表述出来，用 z 代替 x 以强调这里可以涉及任意复数的事实：
(1+z)^r=\sum_k\binom rkz^k~,\quad|z|<1~.\tag{5.13}
如果在这个公式中令 z=x/y 并用 y^r 乘以两边，就能由这个公式得出一般的公式 (5.12) 。
我们仅在 r 是非负整数的情形用组合解释证明了二项式定理。利用多项式推理法，我们不可能从非负整数的情形推导出一般的情形，因为在一般情形下和式是无限的。但是当 r 为任意数值时，我们可以利用泰勒级数以及复变量的理论：
\begin{aligned}f(z)&=\frac{f(0)}{0!}z^0+\frac{f'(0)}{1!}z^1+\frac{f''(0)}{2!}z^2+\cdots\\&=\sum_{k\geqslant0}\frac{f^{(k)}(0)}{k!}z^k~.\end{aligned}
函数 f(z)=(1+z)^r 的导数容易计算，事实上有 f^{(k)}(z)=r^{\underline k}(1+z)^{r-k} 。取 z=0 就给出 (5.13) 。
我们还需要证明这个无限和式当 |z|<1 时是收敛的。的确如此，因为根据后面的等式 (5.83) 可知，\dbinom rk=O(k^{-1-r}) 。
（第 9 章要谈到 O 的意义。）
现在，我们来更仔细地观察 n 是负整数时 \dbinom nk 的值。得到这些值的一种方法是利用加法定律 (5.8) 将表 5-1 向上扩展，这样就得到表 5-2。例如，我们必定有 \dbinom{-1}0=1 ，因为 \dbinom00=\dbinom{-1}0+\dbinom{-1}{-1} 以及 \dbinom{-1}{-1}=0 ，然后就必定有 \dbinom{-1}1=-1 ，因为 \dbinom01=\dbinom{-1}1+\dbinom{-1}0 ，如此等等。
\def\arraystretch{1.25}\def\h{\hspace{0.5em}}\begin{matrix}\textbf{表 5-2}\qquad\textbf{向上扩展的帕斯卡三角形}\\\begin{array}{r|lllllllllll}\hline\hline n\hspace{1em}&\dbinom n0&\dbinom n1&\dbinom n2&\dbinom n3&\dbinom n4&\dbinom n5&\dbinom n6&\dbinom n7&\dbinom n8&\dbinom n9&\dbinom n{10}\\\hline -4\hspace{1em}&\h1\h&-4\h&\h10\h&-20\h&\h35\h&-56\h&\h84\h&-120&\h165\h&-220&\h286\h\\-3\hspace{1em}&\h1\h&-3\h&\h6\h&-10\h&\h15\h&-21\h&\h28\h&-36\h&\h45\h&-55\h&\h66\h\\-2\hspace{1em}&\h1\h&-2\h&\h3\h&-4\h&\h5\h&-6\h&\h7\h&-8\h&\h9\h&-10\h&\h11\h\\-1\hspace{1em}&\h1\h&-1\h&\h1\h&-1\h&\h1\h&-1\h&\h1\h&-1\h&\h1\h&-1\h&\h1\h\\0\hspace{1em}&\h1\h&\h0\h&\h0\h&\h0\h&\h0\h&\h0\h&\h0\h&\h0\h&\h0\h&\h0\h&\h0\h\\\hline\hline\end{array}\end{matrix}
所有这些数都很熟悉。的确，表 5-2 的行和列出现在表 5-1 中（但没有负号）。所以对于取负数值的 n 和取正数值的 n ，其 \dbinom nk 的值之间必定有一种联系。一般的规则是
\binom rk=(-1)^k\binom{k-r-1}k~,\quad k\text{ 是整数.}\tag{5.14}
这很容易证明，因为当 k\geqslant0 时有
\begin{aligned}r^{\underline k}&=r(r-1)\cdots(r-k+1)\\&=(-1)^k(-r)(1-r)\cdots(k-1-r)=(-1)^k(k-r-1)^{\underline k}~,\end{aligned}
而当 k<0 时两边都是零。
恒等式 (5.14) 特别有价值，因为它的成立无需任何限制条件。（当然，下指标必须是整数，这样二项式系数才有定义。）(5.14) 中的变换称为反转上指标 （negating the upper index）或者上指标反转 （upper negation）。
我们怎样记住这个重要的公式呢？我们已经看到的对称恒等式、吸收恒等式和加法公式等都极其简单，但是这个恒等式却有点凌乱。不过仍然有一种不算差的记忆方法：要反转上指标，首先写下 (-1)^k ，其中 k 是下指标（下指标不改变）；然后立即重新写下 k ，写两次，分别写在下指标和上指标两处地方；再后从新的上指标中减去原来的上指标，使得原来的上指标取相反数，再多减去 1 即告完成（永远是减，而不是加，因为这是一个反转的过程）。
你把这称为帮助记忆的方法？我愿意把它称为充气轮胎——言过其实。不管怎么说，它的确帮助我记忆。
我们来练习一下，连续反转上指标两次。这样就得到
（现在是做热身题 4 的大好时机。）
\begin{aligned}\binom rk&=(-1)^k\binom{k-r-1}k\\&=(-1)^{2k}\binom{k-(k-r-1)-1}k=\binom rk~,\end{aligned}
这样正好回到出发点。这可能并不是这个恒等式的构造者所期望的，但是这让我们很欣慰，没有误入歧途。
如果我们试图得到其他新结果，这也会令人沮丧。
当然，(5.14) 的某些应用比这个更有用。例如，我们可以用上指标反转在上下指标位置之间移动量。这个恒等式有一个对称的表述形式
(-1)^m\binom{-n-1}m=(-1)^n\binom{-m-1}n~,\quad\text{整数 }m,n\geqslant0~;\tag{5.15}
它成立是因为两边都等于 \dbinom{m+n}n 。
利用上指标反转，也能推导出如下有趣的和式：
\begin{align}\sum_{k\leqslant m}\binom rk(-1)^k&=\binom r0-\binom r1+\cdots+(-1)^m\binom rm\notag\\&=(-1)^m\binom{r-1}m~,\quad m\text{ 是整数.}\tag{5.16}\end{align}
其思想是，对上指标做反转，然后应用 (5.9) ，再做反转：
\begin{aligned}\sum_{k\leqslant m}\binom rk(-1)^k&=\sum_{k\leqslant m}\binom{k-r-1}k\\&=\binom{-r+m}m\\&=(-1)^m\binom{r-1}m~.\end{aligned}
（双重反转很有用，因为我们已经在它们中间插入了另一种运算。）
这个公式给出了帕斯卡三角形中第 r 行的部分和，只要这一行的元素被赋予交错的符号。例如，如果 r=5 且 m=2 ，则该公式就给出 1-5+10=6=(-1)^2\dbinom42 。
注意：如果 m\geqslant r ，则 (5.16) 就给出了整个这一行的交错和，且当 r 是正整数时这个和式为零。以前我们对此做过证明，那时是用二项式定理对 (1-1)^r 进行展开。这个表达式的部分和也可以用封闭形式计算其值，知道这一点是很有意义的。
更简单的部分和
\sum_{k\leqslant m}\binom nk=\binom n0+\binom n1+\cdots+\binom nm\tag{5.17}
又如何呢？能否确信，如果我们能计算对应的有交错符号的和式，就应该能计算这个和式？但是不能，帕斯卡三角形中一行的部分和不存在封闭形式。我们可以对列操作，这就是 (5.10) ，但不能对行操作。不过，令人感兴趣的是，如果一行的元素均被乘以它们离开中心的距离，那就有一种方法对一行的元素进行部分求和：
\sum_{k\leqslant m}\binom rk\Big(\frac r2-k\Big)=\frac{m+1}2\binom r{m+1}~,\quad m\text{ 是整数.}\tag{5.18}
（对 m 应用归纳法，容易验证这个公式。）在求和项中含有以及不含有因子 (r/2-k) 的这些部分和式之间的关系类似于积分
\int_{-\infty}^\alpha x\mathrm e^{-x^2}\mathrm dx=-\frac12\mathrm e^{-\alpha^2}\text{ 和 }\int_{-\infty}^\alpha\mathrm e^{-x^2}\mathrm dx
之间的关系。左边看似更为复杂的积分（带有因子 x ）有封闭形式，而右边看似更简单的积分（没有这个因子）却没有。外表可能有欺骗性。
（是的，右边的积分是 \dfrac12\sqrt\pi(1+\mathrm{erf}\alpha) ，即一个常数加上 \alpha 的 “误差函数” 的一个倍数，如果我们愿意将它当作一个封闭的形式接受。）
在本章末，我们将要研究一个方法，利用它有可能确定在较为一般的情况下，一个包含二项式系数的级数的部分和是否有封闭形式。借助这种方法，我们能发现恒等式 (5.16) 和 (5.18) ，也将知道 (5.17) 是走不通的。
二项级数的部分和引导出另一种有意思的关系式：
\sum_{k\leqslant m}\binom{m+r}kx^ky^{m-k}=\sum_{k\leqslant m}\binom{-r}k(-x)^k(x+y)^{m-k}~,\quad m\text{ 是整数.}\tag{5.19}
这个恒等式用归纳法不难证明：当 m<0 时两边都是零，而当 m=0 时两边都是 1 。如果用 S_m 代表左边的和式，就能应用加法公式 (5.8) 且容易证明
S_m=\sum_{k\leqslant m}\binom{m-1+r}kx^ky^{m-k}+\sum_{k\leqslant m}\binom{m-1+r}{k-1}x^ky^{m-k}~;
以及
\begin{aligned}&\sum_{k\leqslant m}\binom{m-1+r}kx^ky^{m-k}=yS_{m-1}+\binom{m-1+r}mx^m~,\\&\sum_{k\leqslant m}\binom{m-1+r}{k-1}x^ky^{m-k}=xS_{m-1}~,\end{aligned}
（当 m>0 时）。从而
S_m=(x+y)S_{m-1}+\binom{-r}m(-x)^m~,
而 (5.19) 的右边也满足这个递归式。根据归纳法，两边必定相等。证明完毕。
还有一个更简洁的证明。当 r 是 0\geqslant r\geqslant-m 中的一个整数时，由二项式定理知 (5.19) 的两边都是 (x+y)^{m+r}y^{-r} 。又由于两边都是关于 r 的 m 次或者更低次的多项式，在 m+1 个不同的值处取值相等就足以（不过也刚刚够用）证明在一般情形下相等。
得到一个和式与另一个和式相等的恒等式看起来可能很愚蠢。没有哪一边是封闭形式。但是有时候事实证明有一边比另一边更容易计算。例如，如果令 x=-1 和 y=1 ，我们就得到
\sum_{k\leqslant m}\binom{m+r}k(-1)^k=\binom{-r}m~,\quad\text{整数 }m\geqslant0~,
这是恒等式 (5.16) 的另一种形式。而如果取 x=y=1 以及 r=m+1 ，我们就得到
\sum_{k\leqslant m}\binom{2m+1}k=\sum_{k\leqslant m}\binom{m+k}k2^{m-k}~.
左边正好对上指标为 2m+1 的二项式系数的一半进行了求和，而这些项等于它们在另一半中相似的项，因为帕斯卡三角形是左右对称的，因此左边正好等于 \dfrac122^{2m+1}=2^{2m} 。这就得到一个颇出人意料的公式
（这个公式有一个很好的组合证明。）
\sum_{k\leqslant m}\binom{m+k}k2^{-k}=2^m~,\quad\text{整数 }m\geqslant0~.\tag{5.20}
让我们在 m=2 时检验一下：\dbinom20+\dfrac12\dbinom31+\dfrac14\dbinom42=1+\dfrac32+\dfrac64=4 。令人惊讶！
到目前为止，我们研究的或者是用二项式系数本身来表示的二项式系数，或者是每项中仅含一个二项式系数的项所形成的和式。但是，我们遇到的许多富有挑战性的问题含有两个或者多个二项式系数的乘积，所以要在本节的其余部分考虑如何处理这样的情形。
这里有一个方便使用的法则，常常帮助我们简化两个二项式系数的乘积：
\binom rm\binom mk=\binom rk\binom{r-k}{m-k}~,\quad m,k\text{ 是整数.}\tag{5.21}
我们已经看到了 k=1 这一特殊情形，它就是吸收恒等式 (5.6) 。尽管 (5.21) 的两边都是二项式系数的乘积，但其中一边常常更容易求和，因为它与公式其余部分相互作用。例如，左边两次用到 m ，而右边仅用到一次。因此，当关于 m 求和时，我们通常就用 \dbinom rk\dbinom{r-k}{m-k} 代替 \dbinom rm\dbinom mk 。
等式 (5.21) 最初能成立，因为在 \dbinom rm 和 \dbinom mk 的阶乘表达式中诸个 m! 之间相互抵消。如果所有的变量都是整数且 r\geqslant m\geqslant k\geqslant0 ，我们就有
\begin{aligned}\binom rm\binom mk&=\frac{r!}{m!(r-m)!}\frac{m!}{k!(m-k)!}\\&=\frac{r!}{k!(m-k)!(r-m)!}\\&=\frac{r!}{k!(r-k)!}\frac{(r-k)!}{(m-k)!(r-m)!}=\binom rk\binom{r-k}{m-k}~.\end{aligned}
耶，正确。
这很容易。此外，如果 m<k 或者 k<0 ，那么 (5.21) 的两边都是零，所以这个恒等式对所有整数 m 和 k 都成立。最后，多项式推理法将它的正确性拓展到所有的实数 r 。
二项式系数 \dbinom rk=r!/(r-k)!k! 在适当地重新对变量命名后，可以写成 (a+b)!/a!b! 的形式。类似地，上面推导过程中间的量 r!/k!(m-k)!(r-m)! 可以写成 (a+b+c)!/a!b!c! 的形式。这是一个 “三项式系数”，它出现在 “三项式定理”（trinomial theorem）中：
\begin{aligned}(x+y+z)^n&=\sum_{\substack{0\leqslant a,b,c\leqslant n\\[0.5ex]a+b+c=n}}\frac{(a+b+c)!}{a!b!c!}x^ay^bz^c\\&=\sum_{\substack{0\leqslant a,b,c\leqslant n\\[0.5ex]a+b+c=n}}\binom{a+b+c}{b+c}\binom{b+c}cx^ay^bz^c~.\end{aligned}
“不仅是对二项式 x+y ，而且也对三项式 x+y+z ，实际上对任意的多项式，为它们的幂的系数都设计出了一套绝妙的法则，使得对于给定的任何幂（例如十次幂），我都能立即对 x^5y^3z^2 指定应有的系数，而无需依赖任何表格。” ——莱布尼茨
所以，\dbinom rm\dbinom mk 实际上是改头换面的三项式系数。三项式系数在应用中有时会突然出现，我们可以很方便地将它们写成
\binom{a+b+c}{a,b,c}=\frac{(a+b+c)!}{a!b!c!}
以强调其所呈现的对称性。
二项式系数和三项式系数可以推广到多项式系数 （multinomial coefficient），它总可以表示成二项式系数的乘积：
\begin{aligned}\binom{a_1+a_2+\cdots+a_m}{a_1,a_2,\cdots\,\!,a_m}&=\frac{(a_1+a_2+\cdots+a_m)!}{a_1!a_2!\cdots a_m!}\\&=\binom{a_1+a_2+\cdots+a_m}{a_2+\cdots+a_m}\cdots\binom{a_{m-1}+a_m}{a_m}~.\end{aligned}
这样一来，当我们遇到这样一个对象时，我们的标准技术就可以应用了。
\def\arraystretch{1.25}\begin{matrix}\textbf{表 5-3}\qquad\textbf{二项式系数的乘积之和}\\\begin{array}{lc}\hline\hline \displaystyle\hspace{2em}\sum_k\binom r{m+k}\binom s{n-k}=\binom{r+s}{m+n}~,\quad m,n\text{ 是整数}&\text{(5.22)}\\\displaystyle\hspace{2em}\sum_k\binom l{m+k}\binom s{n+k}=\binom{l+s}{l-m+n}~,\quad\text{整数 }l\geqslant0~,\quad m,n\text{ 是整数}&\text{(5.23)}\\\displaystyle\hspace{2em}\sum_k\binom l{m+k}\binom{s+k}n(-1)^k=(-1)^{l+m}\binom{s-m}{n-l}~,\quad\text{整数 }l\geqslant0~,\quad m,n\text{ 是整数}\hspace{5em}&\text{(5.24)}\\\displaystyle\hspace{2em}\sum_{k\leqslant l}\binom{l-k}m\binom s{k-n}(-1)^k=(-1)^{l+m}\binom{s-m-1}{l-m-n}~,\quad\text{整数 }l,m,n\geqslant0&\text{(5.25)}\\\displaystyle\hspace{2em}\sum_{-q\leqslant k\leqslant l}\binom{l-k}m\binom{q+k}n=\binom{l+q+1}{m+n+1}~,\quad\text{整数 }m,n\geqslant0~,\quad\text{整数 }l+q\geqslant0&\text{(5.26)}\\\hline\hline\end{array}\end{matrix}
现在我们来看表 5-3，它列出了标准技术中最为重要的一些恒等式。这些恒等式就是我们在解决含有两个二项式系数乘积的和式时需要依赖的工具。这些恒等式中，每一个都是对 k 求和的和式，k 在每个二项式系数中都出现一次；还有四个几乎独立的参数 m 、n 、r 等，在每个指标的位置上有一个参数。根据 k 是否出现在上指标或者下指标中，以及 k 带有正号或者负号，会出现不同的情形。有时会有一个额外的因子 (-1)^k ，它在使得这些项可以用封闭形式求和时需要用到。
表 5-3 太过复杂，不可能完全记得住，它只是提供参考。这个表里的第一个恒等式最值得注意，而且应该记住它。它说的是：两个二项式系数的乘积的（对所有整数 k 求和的）和式（其中，上指标是常数，而对所有的 k ，下指标的和是一个常数）是对下指标以及上指标两者求和所得到的二项式系数。这个恒等式称为范德蒙德卷积 （vardermonde convolution），因为 18 世纪后期亚历山大 · 范德蒙德对此写了一篇有意义的论文；然而，中国的朱世杰早在 1303 年就已经知道它了。表 5-3 中的其他的恒等式都可以通过反转上指标或者应用对称定律等方法，细心地从范德蒙德卷积得到，因而范德蒙德卷积就是所有恒等式中最基本的结果。
给这一页折个角，这样你就能很快找到这张表。你将会需要它！
通过对范德蒙德卷积给出一个很好的组合解释，我们就可以证明它。如果用 k-m 代替 k ，用 n-m 代替 n ，我们就能假设 m=0 ，从而要证明的恒等式就是
\sum_k\binom rk\binom s{n-k}=\binom{r+s}n~,\quad n\text{ 是整数.}\tag{5.27}
设 r 和 s 是非负整数，那么一般情形就由多项式推理法得出。在右边，\dbinom{r+s}n 是从 r 个男人和 s 个女人中选取 n 个人的方法数。在左边，和式的每一项都是选取 k 个男人和 n-k 个女人的方法数。对所有的 k 求和就把每一种可能恰好计算了一次。
性别歧视者！你们首先提到了男人。
我们经常是从左向右应用这些恒等式，因为这是简化的方向。但不时也会反向应用它们，暂时使得一个表达式变得更加复杂。当这样做有成效时，我们通常会造出一个二重和式，对它可以交换求和的次序，然后进行化简。
在介绍新的内容之前，让我们再来观察表 5-3 中另外两个恒等式的证明。(5.23) 容易证明，我们要做的就是用 \dbinom l{l-m-k} 代替第一个二项式系数，接下来应用范德蒙德的 (5.22) 式。
下一个恒等式 (5.24) 稍微困难一些。我们可以通过一系列变换将它转化为范德蒙德卷积，不过也可以只求助于数学归纳法技术，同样容易地证明它。只要没有什么其他明显的东西跳出来可用，归纳法就是我们可以尝试的首选方法，而在这里对 l 用归纳法正是有效的。
对于基础 l=0 ，除了 k=-m 时，所有其他的项都是零，所以等式的两边都是 (-1)^m\dbinom{s-m}n 。现在假设这个恒等式对小于某个固定数 l 的所有值都成立，其中 l>0 。我们能利用加法公式，用 \dbinom{l-1}{m+k}+\dbinom{l-1}{m+k-1} 代替 \dbinom l{m+k} ，原来的和式现在就分裂成两个和式，它们中的每一个都能用归纳假设进行计算：
\def\arraystretch{1.25}\begin{array}{c}\displaystyle\sum_k\binom{l-1}{m+k}\binom{s+k}n(-1)^k+\sum_k\binom{l-1}{m+k-1}\binom{s+k}n(-1)^k\\\displaystyle=(-1)^{l-1+m}\binom{s-m}{n-l+1}+(-1)^{l+m}\binom{s-m+1}{n-l+1}~.\end{array}
如果我们再一次应用加法公式，这就简化成 (5.24) 的右边。
关于这个推导有两件事值得关注。第一，我们再一次看到了对所有整数 k 求和而不是仅仅在某个范围内求和的巨大便利，因为没有必要过分关注边界条件。第二，加法公式与数学归纳法能很好地协调，因为它是二项式系数的递归式。上指标是 l 的二项式系数可以用两个上指标为 l-1 的二项式系数表示出来，而这恰好就是我们需要应用归纳假设之处。
表 5-3 就谈这么多。关于含有三个或者更多的二项式系数的和式呢？如果求和指标分布在所有的系数上，我们求出封闭形式的机会就不大了：对于这种类型的和式只知道为数不多的封闭形式，故而我们所需要的和式或许与给定的种类不相符合。在习题 43 中证明的一个罕见的结果是
\sum_k\binom{m-r+s}k\binom{n+r-s}{n-k}\binom{r+k}{m+n}=\binom rm\binom sn~,\quad m,n\text{ 是整数.}\tag{5.28}
这里是另外一个给更加对称的例子：
\sum_k\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+a}{c+k}(-1)^k=\frac{(a+b+c)!}{a!b!c!}~,\quad\text{ 整数 }a,b,c\geqslant0~.\tag{5.29}
这个公式有一种两个二项式系数的相似结果
\sum_k\binom{a+b}{a+k}\binom{b+a}{b+k}(-1)^k=\frac{(a+b)!}{a!b!}~,\quad\text{整数 }a,b\geqslant0~,\tag{5.30}
它恰巧没有出现在表 5-3 中。类似的四个系数和式没有封闭形式，不过一个相似的和式的确有封闭形式：
\begin{aligned}&\sum_k(-1)^k\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+d}{c+k}\binom{d+a}{d+k}\bigg/\binom{2a+2b+2c+2d}{a+b+c+d+k}\\&\hphantom{\sum(\,}=\frac{(a+b+c+d)!(a+b+c)!(a+b+d)!(a+c+d)!(b+c+d)!}{(2a+2b+2c+2d)!(a+c)!(b+d)!a!b!c!d!}~,\quad\text{整数 }a,b,c,d\geqslant0~.\end{aligned}
这可以由 20 世纪早期 John Dougall 所发现的一个五参数恒等式得出。
Dougall 的恒等式是已知的最令人恐怖的关于二项式系数的恒等式吗？不！到目前为止，冠军是
\begin{align}&\sum_{k_{ij}}(-1)^{\sum_{i<j}k_{ij}}\Bigg(\hspace{-0.15em}\prod_{1\leqslant i<j<n}\hspace{-0.25em}\binom{a_i+a_j}{a_j+k_{ij}}\hspace{-0.15em}\Bigg)\hspace{-0.15em}\Bigg(\hspace{-0.15em}\prod_{1\leqslant j<n}\hspace{-0.25em}\binom{a_j+a_n}{a_n+\sum_{i<j}k_{ij}-\sum_{i>j}k_{ji}}\hspace{-0.15em}\Bigg)\notag\\&\hphantom{\sum(\,}=\binom{a_1+\cdots+a_n}{a_1,a_2,\cdots\,\!,a_n}~,\quad\text{整数 }a_1,a_2,\cdots\,\!,a_n\geqslant0~.\tag{5.31}\end{align}
这里的和式是对 \dbinom{n-1}2 个指标变量 k_{ij}~(1\leqslant i<j<n) 求和的。等式 (5.29) 是 n=3 时的特例；n=4 时的特殊情形可以表述如下：如果用 (a,b,c,d) 代替 (a_1,a_2,a_3,a_4) ，用 (i,j,k) 代替 (k_{12},k_{13},k_{23}) ，那么有
\begin{aligned}&\sum_{i,j,k}(-1)^{i+j+k}\binom{a+b}{b+i}\binom{a+c}{c+j}\binom{b+c}{c+k}\binom{a+d}{d-i-j}\binom{b+d}{d+i-k}\binom{c+d}{d+j+k}\\&\hphantom{\sum(\,}=\frac{(a+b+c+d)!}{a!b!c!d!}~,\quad\text{整数 }a,b,c,d\geqslant0~.\end{aligned}
$$
\prod_{\substack{1\leqslant i,j\leqslant n\\[0.5ex]i\ne j}}\hspace{-0.25em}\left(1-\frac{z_i}{z_j}\right)^{a_i}
$$
完全展开成诸个 $z$ 的正的或负的幂时，$z_1^0z_2^0\cdots z_n^0$ 的系数。$(5.31)$ 的右边是由 Freeman Dyson 于 1962 年猜想并在此后不久被若干个人所证明了的。习题 86 对 $(5.31)$ 给出了一个 “简单的” 证明。
另一个值得注意的含有许多二项式系数的恒等式是
$$
\begin{align}&\sum_{j,k}(-1)^{j+k}\binom{j+k}{k+l}\binom rj\binom nk\binom{s+n-j-k}{m-j}\notag\\&\hphantom{\sum(\,}=(-1)^l\binom{n+r}{n+l}\binom{s-r}{m-n-l}~,\quad l,m,n\text{ 是整数}~;\quad n\geqslant0~.\tag{5.32}\end{align}
$$
这个恒等式的证明在习题 83 中。它甚至有可能在实际应用中出现。我们偏离 “基本恒等式” 这个主题已经太远了，所以最好停下来，并对已经学习的东西做一番评估。
我们已经看到，二项式系数满足几乎使人迷惑的大量恒等式。幸运的是，其中有一些容易记忆，而且我们可以用这些容易记住的恒等式经过几步就推导出其他大部分恒等式。表 5-4 搜集了其中十个最有用的公式，这些是最好需要了解的最好的恒等式。
$$
\def\arraystretch{2}\begin{matrix}\textbf{表 5-4}\qquad\textbf{最重要的十个二项式系数恒等式}\\\hline\hline\begin{aligned}\hspace{7em}\binom nk&=\frac{n!}{k!(n-k)!}~,\quad\text{整数 }n\geqslant k\geqslant0\hspace{7em}&&\text{阶乘展开式}\hspace{5em}\\\binom nk&=\binom n{n-k}~,\quad\text{整数 }n\geqslant0~,\quad k\text{ 是整数}&&\text{对称恒等式}\\\binom rk&=\frac rk\binom{r-1}{k-1}~,\quad\text{整数 }k\ne0&&\text{吸收/提取恒等式}\\\binom rk&=\binom{r-1}k+\binom{r-1}{k-1}~,\quad k\text{ 是整数}&&\text{加法/归纳恒等式}\\\binom rk&=(-1)^k\binom{k-r-1}k~,\quad k\text{ 是整数}&&\text{上指标反转}\\\binom rm\binom mk&=\binom rk\binom{r-k}{m-k}~,\quad m,k\text{ 是整数}&&\text{三项式版恒等式}\\\sum_k\binom rkx^ky^{r-k}&=(x+y)^r~,\quad\text{整数 }r\geqslant0\text{ 或者 }|x/y|<1&&\text{二项式定理}\\\sum_{k\leqslant n}\binom{r+k}k&=\binom{r+n+1}n~,\quad n\text{ 是整数}&&\text{平行求和法}\\\sum_{0\leqslant k\leqslant n}\binom km&=\binom{n+1}{m+1}~,\quad\text{整数 }m,n\geqslant0&&\text{上指标求和法}\\\sum_k\binom rk\binom s{n-k}&=\binom{r+s}n~,\quad n\text{ 是整数}&&\text{范德蒙德卷积公式}\\\hline\hline\end{aligned}\end{matrix}
$$
## 5.2 基本练习 BASIC PRACTICE
在上一节里，通过处理和式以及插入其他的恒等式，我们得出了一批恒等式。得出那些的推导过程并不太困难——我们知道要证明什么，所以可以叙述一个一般的计划，不必费大周折就能将细节补充完全。然而，通常在真实的世界里还没有遇到一个要证明的恒等式，我们面对的往往是一个要简化的和式。而且我们并不知道简化的形式可能是什么样子（或者它是否存在）。在这一节以及下一节里，通过处理许多这样的和式，我们将会把二项式系数的工具打磨锐利。
首先，我们来亲手尝试几个包含单个二项式系数的和式。
> 自学算法：
>
> 1. 阅读问题
> 2. 尝试求解问题
> 3. 浏览书中答案
> 4. $\underline{\text{if}}$ 尝试失败
> $\underline{\text{goto}}$ 步骤 1
> $\underline{\text{else}}~\underline{\text{goto}}$ 下一个问题
**问题 1：比值的和式**
我们希望
$$
\sum_{k=0}^m\binom mk\bigg/\binom nk~,\quad\text{整数 }n\geqslant m\geqslant0
$$
有一个封闭形式。初看之下，这个和式会令人惊恐不安，因为我们尚未见过处理二项式系数的商的恒等式。（此外，这个和式还含有两个二项式系数，这似乎与这个问题前面的那句话有矛盾。）然而，正如我们能用阶乘将二项式系数的一个乘积表示成另一个乘积那样，即得到恒等式 $(5.21)$ 的方法，我们可以对商类似地去做。事实上，我们可以通过设 $r=n$ 并用 $\dbinom nk\dbinom nm$ 除等式 $(5.21)$ 的两边来避免面目可憎的阶乘表示法，这就得到
> 不幸的是，那个算法会使你陷入无穷循环。
> 推荐补丁：
> $0~\underline{\text{set}}~c\gets0
\text{3a}~\underline{\text{set}}~c\gets c+1
3b~\underline{\text{if}}~c=N
\binom mk\bigg/\binom nk=\binom{n-k}{m-k}\bigg/\binom nm~.
所以我们用右边的商来代替左边的那个商，左边的商出现在我们的和式中，这样和式就变成
\sum_{k=0}^m\binom{n-k}{m-k}\bigg/\binom nm~.
还有一个商，但是分母中的这个二项式系数不包含求和指标 k ，所以我们可以从和式中把它移走。以后我们会恢复它。
我们也能通过对所有的 k\geqslant0 求和来简化其边界条件，满足 k>m 的项都是零。剩下的和式就不那么吓人了：
\sum_{k\geqslant0}\binom{n-k}{m-k}~.
（此处省略一张图） ——E. W. Dijkstra
Dijkstra 认为，在计算机程序中使用 goto 语句是有害的。
它类似于恒等式 (5.9) ，因为指标 k 带同样的符号出现了两次。但是在这里它是 -k ，而在 (5.9) 里它不是。这样一来，下一步就应该很明显了，只有一件合理的事要做：
……但是这一节就称为基本练习。
\begin{aligned}\sum_{k\geqslant0}\binom{n-k}{m-k}&=\sum_{m-k\geqslant0}\binom{n-(m-k)}{m-(m-k)}\\&=\sum_{k\leqslant m}\binom{n-m+k}k~.\end{aligned}
现在我们能应用平行求和法恒等式，即 (5.9) ：
\sum_{k\leqslant m}\binom{n-m+k}k=\binom{(n-m)+m+1}m=\binom{n+1}m~.
最后，我们将恢复早先从和式中去掉的分母中的 \dbinom nm ，然后应用 (5.7) 得到所要的封闭形式：
\binom{n+1}m\bigg/\binom nm=\frac{n+1}{n+1-m}~.
这一推导实际上对取任意实数值的 n 都成立，只要不出现用零做除数，也就是说，只要 n 不是整数 0,1,\cdots\,\!,m-1 中的一个。
推导过程越是复杂，对答案进行检查就越是重要。这一推导并不太复杂，但是无论如何我们都要检查一番。在小数值 m=2 和 n=4 的情形，我们有
\binom20\bigg/\binom40+\binom21\bigg/\binom41+\binom22\bigg/\binom42=1+\frac12+\frac16=\frac53~,
是的，这与封闭形式 (4+1)/(4+1-2) 完全吻合。
问题 2：来自排序文献
下一个和式出现于 20 世纪 70 年代早期，那时人们还不能熟练地使用二项式系数。一篇介绍改进的合并技术的论文以下面的注解结束：“可以证明，所期望节省的转移的个数……由表达式
T=\sum_{r=0}^nr\frac{_{m-r-1}C_{m-n-1}}{_mC_n}
给出。这里 m 和 n 定义如上，而 _mC_n 是表示从 m 个物体中一次取 n 个的组合数……作者感谢审稿人将有关期望节省的转移的一个更复杂的等式简化成了这里给出的形式。”
我们将会看到，这肯定不是关于作者的问题的最后答案，它甚至也不是一个中间阶段的答案。
请不要提醒我要期中考试了。
“中间阶段” 与 “期中考试” 都是同一个英文单词 midterm。
首先我们应该将这个和式转变成某种我们能对它处理的东西，恐怖的记号 _{m-r-1}C_{m-n-1} 除了使那位热情的审稿人感到高兴外，足以让任何人望而却步。用我们的语言可以将其写成
T=\sum_{k=0}^nk\binom{m-k-1}{m-n-1}\bigg/\binom mn~,\quad\text{整数 }m>n\geqslant0~.
分母中的二项式系数不包含求和指标，所以我们可以将它移走并处理新的和式
S=\sum_{k=0}^nk\binom{m-k-1}{m-n-1}~.
接下来是什么？求和指标出现在二项式系数的上指标中，但不出现在下指标中。所以，如果没有另外那个 k ，我们就能修改这个和式并应用对上指标的求和法 (5.10) 。可是有了多出来的那个 k ，我们无法这样做。如果可以利用某个吸收恒等式通过某种方法把那个 k 吸收到二项式系数中去，那么我们就能对上指标求和了。不幸的是，那些恒等式在这里都不能用。但是，如果用 m-k 代替 k ，我们就能应用吸收恒等式 (5.6) ：
(m-k)\binom{m-k-1}{m-n-1}=(m-n)\binom{m-k}{m-n}~.
所以关键在于：我们将把 k 改写成 m-(m-k) ，并将 S 分裂成两个和式：
\begin{aligned}\sum_{k=0}^nk\binom{m-k-1}{m-n-1}&=\sum_{k=0}^n\big(m-(m-k)\big)\binom{m-k-1}{m-n-1}\\&=\sum_{k=0}^nm\binom{m-k-1}{m-n-1}-\sum_{k=0}^n(m-k)\binom{m-k-1}{m-n-1}\\&=m\sum_{k=0}^n\binom{m-k-1}{m-n-1}-\sum_{k=0}^n(m-n)\binom{m-k}{m-n}\\&=mA-(m-n)B~,\end{aligned}
其中
A=\sum_{k=0}^n\binom{m-k-1}{m-n-1}~,\quad B=\sum_{k=0}^n\binom{m-k}{m-n}~.
剩下的和式 A 以及 B 是我们的老朋友，在其中上指标变动而下指标保持不变。我们先来解决 B ，因为它看起来更简单。稍加改动即足以使得其中的求和项与 (5.10) 的左边相符：
\begin{aligned}\sum_{0\leqslant k\leqslant n}\binom{m-k}{m-n}&=\sum_{0\leqslant m-k\leqslant n}\binom{m-(m-k)}{m-n}\\&=\sum_{m-n\leqslant k\leqslant m}\binom k{m-n}\\&=\sum_{0\leqslant k\leqslant m}\binom k{m-n}~.\end{aligned}
在最后一步，我们在和式中加入了满足 0\leqslant k<m-n 的项，它们全都是零，因为它们的上指标都小于下指标。现在关于上指标求和，利用 (5.10) 得到
B=\sum_{0\leqslant k\leqslant m}\binom k{m-n}=\binom{m+1}{m-n+1}~.
对另一个和式 A 的做法相同，不过要用 m-1 代替 m 。这样我们就给出了给定和式 S 的一个封闭形式，这个和式还可以进一步简化：
\begin{aligned}S=mA-(m-n)B&=m\binom m{m-n}-(m-n)\binom{m+1}{m-n+1}\\&=\bigg(m-(m-n)\frac{m+1}{m-n+1}\bigg)\binom m{m-n}\\&=\bigg(\frac n{m-n+1}\bigg)\binom m{m-n}~.\end{aligned}
而这就给出了原来和式的一个封闭形式：
\begin{aligned}T&=S\bigg/\binom mn\\&=\frac n{m-n+1}\binom m{m-n}\bigg/\binom mn\\&=\frac n{m-n+1}~.\end{aligned}
即便是审稿人也不可能对它进行简化了。
我们再次利用小数值的情形检查答案。当 m=4 以及 n=2 时，我们有
T =0\times\binom31\bigg/\binom42+1\times\binom21\bigg/\binom42+2\times\binom11\bigg/\binom42=0+\frac26+\frac26=\frac23~,
它与公式 2/(4-2+1) 吻合。
问题 3：来自以往的考试题
我们再做一个和式，它包含一个二项式系数。这个和式与上面源于学术殿堂的问题不同，它是一个可以在家测试的问题。我们想求 Q_{1~000~000} 的值，这里
以往的考试没有生命力了吗？
Q_n=\sum_{k\leqslant2^n}\binom{2^n-k}k(-1)^k~,\quad\text{整数 }n\geqslant0~.
这个问题比其他问题更难一些，不可能应用到目前为止我们所见到过的任何恒等式。而且我们面对的是一个有 2^{1~000~000}+1 项的和式，所以不是只把它们相加起来就能奏效的。求和指标 k 在上下两个指标中都出现，不过带有相反的符号。反转上指标也没有什么效果：它去掉了因子 (-1)^k ，却在上指标中加入一个 2k 。
当没有什么方法明显有用时，我们知道最好是来观察小数值的情形。即使不能得到一个模式并用归纳法证明它，至少也有一些数据来核查我们的结果。下表是前四个 n 值的非零项以及它们的和。
\def\arraystretch{2}\begin{array}{c|lll}\hspace{1em}n\hspace{1em}&&&Q_n\hspace{1.5em}\\\hline0&\dbinom10&=1&=1\\1&\dbinom20-\dbinom11&=1-1&=0\\2&\dbinom40-\dbinom31+\dbinom22&=1-3+1&=-1\\3&\dbinom80-\dbinom71+\dbinom62-\dbinom53+\dbinom44&=1-7+15-10+1&=0\end{array}
我们最好不要尝试下一个情形 n=4 ，这样极有可能产生算术误差。（手工计算 \dbinom{12}4 和 \dbinom{11}5 这样的项，仅仅是在迫不得已时才值得一试的，更不要提将它们和其他东西组合在一起了。）
所以其模式的开始部分是 1,0,-1,0 。即使我们知道了下一项或者下面两项，其封闭形式也不会显现。但是如果我们能找到并且证明关于 Q_n 的一个递归式，就有可能猜到并且证明它的封闭形式。为了找到一个递归式，我们需要将 Q_n 与 Q_{n-1} （或者与 Q_{\text{较小的值}} ）联系起来，但这样做就需要将一个像 \dbinom{128-13}{13} 的项（它在 n=7 和 k=13 时出现）与像 \dbinom{64-13}{13} 的项联系起来。这似乎看不出希望，我们不知道在帕斯卡三角形中相距 64 行的元素之间有什么样简洁明了的关系。加法公式作为归纳法证明的主要工具，仅仅将相距一行的元素联系在一起。
但是，这引出了一个关键点：不需要处理相距 2^{n-1} 行的元素。变量 n 从来就没有以本来面目出现，而总是以 2^n 的形式出现。所以 2^n 用额外增加的复杂度转移了我们的注意力！如果用 m 代替 2^n ，我们所需做的就是对更加一般性的（也更容易的）和式
哦，这是为那场考试出题的教员泄的密。
R_m=\sum_{k\leqslant m}\binom{m-k}k(-1)^k~,\quad\text{整数 }m\geqslant0
求出封闭形式，这样也就对 Q_n=R_{2^n} 给出了封闭形式。而且很有可能，加法公式将对序列 R_m 给出一个递归式。
从表 5-1 可以知道小的 m 和 R_m 的值，如果我们将出现在西南到东北这条对角线上的值交错地做加法和减法。其结果是
\def\arraystretch{1.25}\begin{array}{c|ccccccccccc}\hspace{1em}m\hspace{1em}&\hspace{0.5em}0\hspace{0.5em}&\hspace{0.5em}1\hspace{0.5em}&\hspace{0.5em}2\hspace{0.5em}&\hspace{0.5em}3\hspace{0.5em}&\hspace{0.5em}4\hspace{0.5em}&\hspace{0.5em}5\hspace{0.5em}&\hspace{0.5em}6\hspace{0.5em}&\hspace{0.5em}7\hspace{0.5em}&\hspace{0.5em}8\hspace{0.5em}&\hspace{0.5em}9\hspace{0.5em}&\hspace{0.5em}10\hspace{0.5em}\\\hline R_m&1&1&0&-1&-1&0&1&1&0&-1&-1\end{array}
看起来要进行多次抵消。
现在来看关于 R_m 的公式，并研究它是否定义一个递归式。我们的策略是应用加法公式 (5.8) ，并在得到的表达式中求形如 R_k 的和式，这有点像在第 2 章的扰动法中所做的那样：
\begin{aligned}R_m&=\sum_{k\leqslant m}\binom{m-k}k(-1)^k\\&=\sum_{k\leqslant m}\binom{m-1-k}k(-1)^k+\sum_{k\leqslant m}\binom{m-1-k}{k-1}(-1)^k\\&=\sum_{k\leqslant m}\binom{m-1-k}k(-1)^k+\sum_{k+1\leqslant m}\binom{m-2-k}k(-1)^{k+1}\\&=\sum_{k\leqslant m-1}\binom{m-1-k}k(-1)^k+\binom{-1}m(-1)^m-\sum_{k\leqslant m-2}\binom{m-2-k}k(-1)^k-\binom{-1}{m-1}(-1)^{m-1}\\&=R_{m-1}+(-1)^{2m}-R_{m-2}-(-1)^{2(m-1)}=R_{m-1}-R_{m-2}~.\end{aligned}
倒数第二步利用了公式 \dbinom{-1}m=(-1)^m ，我们知道它对 m\geqslant0 为真。）这个推导对 m\geqslant2 成立。
至少，做了热身题第 4 题的人知道它。
由这个递归式可以快速生成 R_m 的值，而且我们很快就会发现这个序列是周期性的。的确，
R_m=\begin{cases}1\\1\\0\\-1\\-1\\0\end{cases}~,\quad\text{如果 }m\bmod6=\begin{cases}0\\1\\2\\3\\4\\5\end{cases}~.
用归纳法的证明就是要检验。或者，如果我们必须给出一个更学术性的证明，就可以将此递归式再展开一步，得到：只要 m\geqslant3 ，就有
R_m=(R_{m-2}-R_{m-3})-R_{m-2}=-R_{m-3}~.
因此，只要 m\geqslant6 ，就有 R_m=R_{m-6} 。
最后，由于 Q_n=R_{2^n} ，我们可以通过确定 2^m\bmod6 并利用 R_m 的封闭形式来确定 Q_n 。当 n=0 时有 2^0\bmod6=1 ，此后一直用 2~(\bmod6) 来相乘，这样模式 2,4 就会重复出现。从而
Q_n=R_{2^n}=\begin{cases}R_1=1&,~n=0~;\\R_2=0&,~n\text{ 是奇数 };\\R_4=-1&,~n>0\text{ 是偶数.}\end{cases}
**问题 4：包含两个二项式系数的和式**
我们的下一个任务是对
$$
\sum_{k=0}^nk\binom{m-k-1}{m-n-1}~,\quad\text{整数 }m>n\geqslant0
$$
求封闭形式。请等一会儿。这个问题的标题中所暗示的第二个二项式系数在哪儿？为什么我们要试图将一个已经简化的和式再简化？（这就是问题 2 中的 $S$。）
如果我们把求和项视为两个二项式系数的乘积，然后再利用表 5-3 中某个一般恒等式，它就成为一个容易简化的和式。当我们将 $k$ 改写成 $\dbinom k1$ 时，第二个二项式系数就出现了：
$$
\sum_{k=0}^nk\binom{m-k-1}{m-n-1}=\sum_{0\leqslant k\leqslant n}\binom k1\binom{m-k-1}{m-n-1}~.
$$
恒等式 $(5.26)$ 就是一个要应用的公式，因为它的求和指标出现在两个上指标中且带有相反的符号。
但是我们的和式还不具有正确的形式。如果要使它与 $(5.26)$ 完全匹配，求和的上限应该是 $m-1$。这没有问题，因为满足 $n<k\leqslant m-1$ 的项都是零。所以我们可以用 $(l,m,n,q)\gets(m-1,m-n-1,1,0)$ 代入，答案就是
$$
S=\binom m{m-n+1}~.
$$
这比我们以前得到的公式更加简洁。利用 $(5.6)$ 和 $(5.7)$ 可以将它变回上一个公式：
$$
\binom m{m-n+1}=\frac n{m-n+1}\binom m{m-n}~.
$$
类似地，通过将特殊的值代入我们见过的其他一般恒等式，可以得到一些有趣的结果。例如，假设在 $(5.26)$ 中令 $m=n=1$，$q=0$。这样，该恒等式就变成
$$
\sum_{0\leqslant k\leqslant l}(l-k)k=\binom{l+1}3~.
$$
左边是 $l\big((l+1)l/2\big)-(1^2+2^2+\cdots+l^2)$，所以这就对在第 2 章里弄得我们筋疲力尽的平方和问题给出了一个独特的新方法。
这个故事的教益是：非常一般的和式的特殊情形有时最好是在一般形式下处理。学习一般形式时，聪明的做法是学习它们的简单特例。
**问题 5：有三个因子的和式**
这是另一个不太坏的和式。我们希望简化
$$
\sum_k\binom nk\binom skk~,\quad\text{整数 }n\geqslant0~.
$$
求和指标 $k$ 出现在两个下指标中且带有同样的符号，这样一来，表 5-3 中的恒等式 $(5.23)$ 看起来接近于我们所需要的东西。再稍加处理，我们应该能使用它。
$(5.23)$ 与我们所有和式之间存在的最大区别是，我们的和式中有一个额外的 $k$。但是，利用吸收恒等式中的一个公式，我们可以将 $k$ 吸收到二项式系数的内部：
$$
\begin{aligned}\sum_k\binom nk\binom skk&=\sum_k\binom nk\binom{s-1}{k-1}s\\&=s\sum_k\binom nk\binom{s-1}{k-1}~.\end{aligned}
$$
我们并不关心当 $k$ 消失时会出现 $s$，因为 $s$ 是常数。现在我们已经准备应用这个恒等式并得到封闭形式
$$
s\sum_k\binom nk\binom{s-1}{k-1}=s\binom{n+s-1}{n-1}~.
$$
如果我们在第一步就选择将 $k$ 吸收进 $\dbinom nk$，而不是吸收进 $\dbinom sk$，就不能直接应用 $(5.23)$ 了，因为 $n-1$ 或许会是负的，而这个恒等式要求在至少一个上指标中取非负值。
**问题 6：一个令人惊悚的和式**
下一个和式更具挑战性。我们要对
$$
\sum_{k\geqslant0}\binom{n+k}{2k}\binom{2k}k\frac{(-1)^k}{k+1}~,\quad\text{整数 }n\geqslant0
$$
寻求封闭形式。度量和式困难程度的一个有用方法是看看其求和指标出现的次数。根据这个度量，可以知道我们深陷麻烦之中——$k$ 出现 $6$ 次。此外，在前面的问题中起关键作用的一步——将某个处在二项式系数外面的东西吸收到其中一个二项式系数的内部——在这里不起作用了。如果我们吸收 $k+1$，在它的位置上就会得到另外一个 $k$。不仅如此，在一个二项式系数的内部，我们的指标 $k$ 已经两次与系数 $2$ 捆绑在了一起。乘一个常数通常要比加一个常数更难去掉。
> 所以我们应该将这个和式挖地三尺埋葬掉，对吗？
尽管如此，我们这一次还是很幸运的。这些 $2k$ 都正好是在应用恒等式 $(5.21)$ 时需要它们的地方出现的，所以我们得到
$$
\sum_{k\geqslant0}\binom{n+k}{2k}\binom{2k}k\frac{(-1)^k}{k+1}=\sum_{k\geqslant0}\binom{n+k}k\binom nk\frac{(-1)^k}{k+1}~.
$$
这样两个 $2$ 就消失了，而且一个 $k$ 也消失了。解决了这个困难，下面五步就可以进行下去了。
分母中的 $k+1$ 是剩下来的最令人头疼的，现在可以利用恒等式 $(5.5)$ 将它吸收进 $\dbinom nk$：
$$
\begin{aligned}\sum_{k\geqslant0}\binom{n+k}k\binom nk\frac{(-1)^k}{k+1}&=\sum_k\binom{n+k}k\binom{n+1}{k+1}\frac{(-1)^k}{n+1}\\&=\frac1{n+1}\sum_k\binom{n+k}k\binom{n+1}{k+1}(-1)^k~.\end{aligned}
$$
（记住 $n\geqslant0$。）排除了两个障碍，下面四步就畅通无阻了。
为了消除另外一个 $k$，我们有两种有希望的选择。我们可以对 $\dbinom{n+k}k$ 利用对称性，或者反转上指标 $n+k$，这样就在消除那个 $k$ 的同时也消除了因子 $(-1)^k$。我们来探讨这两种可能性，首先选择对称性：
$$
\frac1{n+1}\sum_k\binom{n+k}k\binom{n+1}{k+1}(-1)^k=\frac1{n+1}\sum_k\binom{n+k}n\binom{n+1}{k+1}(-1)^k~.
$$
排除了三个障碍，还剩三步。现在我们已经能通过代入 $(5.24)$ 取得大的进展：用 $(n+1,1,n,n)$ 代替 $(l,m,n,s)$，得到
> 有那么一分钟，我曾想我们还是放弃算了。
$$
\frac1{n+1}\sum_k\binom{n+k}n\binom{n+1}{k+1}(-1)^k=\frac1{n+1}(-1)^n\binom{n-1}{-1}=0~.
$$
呃，等于零？终于有效果了？我们用 $n=2$ 进行核查：$\dbinom20\dbinom00\dfrac11-\dbinom32\dbinom21\dfrac12+\dbinom44\dbinom42\dfrac13=1-\dfrac62+\dfrac63=0$。结果相符。
只是为了尝试一下，我们来探讨另一种选择，即反转 $\dbinom{n+k}k$ 的上指标：
$$
\frac1{n+1}\sum_k\binom{n+k}k\binom{n+1}{k+1}(-1)^k=\frac1{n+1}\sum_k\binom{-n-1}k\binom{n+1}{k+1}~.
$$
现在对 $(l,m,n,s)\gets(n+1,1,0,-n-1)$ 应用 $(5.23)$，就有
$$
\frac1{n+1}\sum_k\binom{-n-1}k\binom{n+1}{k+1}=\frac1{n+1}\binom0m~.
$$
嘿，等一等。当 $n>0$ 时此式等于零，而当 $n=0$ 时它等于 $1$。求出其解的其他途径告诉我们，这个和式在所有情形都等于零！是什么原因造成这样的结果呢？当 $n=0$ 时，事实表明这个和式实际上等于 $1$，所以正确的答案是 “$[n=0]$”。我们在前面那个推导过程中一定出错了。
我们快速重演 $n=0$ 时的推导，以便看出不相符之处首先在哪儿出现。啊，是的，我们掉进了早先提及的陷阱中：当上指标可能是负数时我们试图运用对称性！当 $k$ 取遍所有整数时，我们用 $\dbinom{n+k}n$ 代替 $\dbinom{n+k}k$ 并不合法，因为在 $k<-n$ 时，这会将零变换成一个非零的值。（对此抱歉。）
> 尝试二叉搜索：首先重新运用中间的公式，来看错误是出在此前还是此后。
事实表明，和式中的另一个因子 $\dbinom{n+1}{k+1}$ 当 $k<-n$ 时为零，除了当 $n=0$ 以及 $k=-1$ 的情形之外。因此，当我们核查 $n=2$ 的情形时没有出现这样的错误。习题 6 解释了我们本应该做什么。
**问题 7：新的障碍**
这个和式更加棘手，我们想对
$$
\sum_{k\geqslant0}\binom{n+k}{m+2k}\binom{2k}k\frac{(-1)^k}{k+1}~,\quad\text{整数 }m,n>0
$$
求出封闭形式。如果 $m$ 是零，我们恰好就得到前一问题中的和式。但事实并非如此，我们陷入一个真正的困境——问题 6 中用过的任何方法在这里都不起作用。（特别是关键的第一步不起作用。）
然而，如果有办法避开 $m$，就能利用刚刚得到的结果。所以我们的策略就是：用像 $\dbinom{l+k}{2k}$（对某个非负整数 $l$）这样的项组成一个和式代替 $\dbinom{n+k}{m+2k}$，这样一来，求和项看起来就像问题 6 中的求和项，我们就能交换求和次序了。
我们应该用什么来代替 $\dbinom{n+k}{m+2k}$？仔细检查这一章早先得到的恒等式，我们发现仅有一个合适的候选者，即表 5-3 中的恒等式 $(5.26)$。利用它的一种方式是用 $(n+k-1,2k,m-1,0,j)$ 分别代替 $(l,m,n,q,k)$：
$$
\begin{aligned}&\phantom{=~}\sum_{k\geqslant0}\binom{n+k}{m+2k}\binom{2k}k\frac{(-1)^k}{k+1}\\&=\sum_{k\geqslant0}\sum_{0\leqslant j\leqslant n+k-1}\binom{n+k-1-j}{2k}\binom j{m-1}\binom{2k}k\frac{(-1)^k}{k+1}\\&=\sum_{j\geqslant0}\binom j{m-1}\sum_{\substack{k\geqslant j-n+1\\[0.5ex]k\geqslant0}}\binom{n+k-1-j}{2k}\binom{2k}k\frac{(-1)^k}{k+1}~.\end{aligned}
$$
在最后一步，我们改变了求和的次序，按照第 2 章里的法则处理 $\Sigma$ 下方的条件。
我们还不能用问题 6 的结果完全代替内层的和式，因为它有一个额外的条件 $k\geqslant j-n+1$；不过除了 $j-n+1>0$，也即除了 $j\geqslant n$ 之外，这个额外的条件是多余的。而当 $j\geqslant n$ 时，内层和式的第一个二项式系数是零，因为它的上指标介于 $0$ 和 $k-1$ 之间，从而它严格小于下指标 $2k$。这样一来，或许我们可以在外层和式上增加一个限制 $j<n$，这不会影响到它所包含的非零的项。这就使得限制条件 $k\geqslant j-n+1$ 成为多余，我们可以利用问题 6 的结果了。现在这个二重和式就从我们的视线中淡出了：
$$
\begin{aligned}&\phantom{=~}\sum_{j\geqslant0}\binom j{m-1}\sum_{\substack{k\geqslant j-n+1\\[0.5ex]k\geqslant0}}\binom{n+k-1-j}{2k}\binom{2k}k\frac{(-1)^k}{k+1}\\&=\sum_{0\leqslant j<n}\binom j{m-1}\sum_{k\geqslant0}\binom{n+k-1-j}{2k}\binom{2k}k\frac{(-1)^k}{k+1}\\&=\sum_{0\leqslant j<n}\binom j{m-1}[n-1-j=0]=\binom{n-1}{m-1}~. \end{aligned}
$$
内层和式除了当 $j=n-1$ 时不为零，其余取值都为零，所以我们就得到了一个简单的封闭形式。
**问题 8：不同的障碍**
考虑和式
$$
S_m=\sum_{k\geqslant0}\binom{n+k}{2k}\binom{2k}k\frac{(-1)^k}{k+1+m}~,\quad\text{整数 }m,n\geqslant0~,
$$
我们就能以另外一种方式从问题 6 中引出一个新的发展方向。当 $m=0$ 时，我们又得到以前得到的和式，不过 $m$ 出现在了不同的地方。这个问题比问题 7 还要难一点，幸运的是我们在求解方面正在取得进步。我们可以像在问题 6 中那样从
$$
S_m=\sum_{k\geqslant0}\binom{n+k}k\binom nk\frac{(-1)^k}{k+1+m}
$$
开始。如同在问题 7 中那样，我们现在尝试将与 $m$ 有关的部分展开成我们知道如何处理的项。当 $m$ 是零时，将 $k+1$ 吸收到 $\dbinom nk$ 中；如果 $m>0$，只要将 $1/(k+1+m)$ 展开成可以吸收的项，我们就能同样去做。好运依然还在：在问题 1 中，我们证明了一个合适的恒等式
$$
\sum_{j=0}^m\binom mj\binom rj^{-1}=\frac{r+1}{r+1-m}~,\quad\text{整数 }m\geqslant0~,\quad r\notin\{0,1,\cdots\,\!,m-1\}~.\tag{5.33}
$$
用 $-k-2$ 代替 $r$ 就给出所要的展开式
$$
S_m=\sum_{k\geqslant0}\binom{n+k}k\binom nk\frac{(-1)^k}{k+1}\sum_{j\geqslant0}\binom mj\binom{-k-2}j^{-1}~.
$$
现在 $(k+1)^{-1}$ 可以吸收到 $\dbinom nk$ 中，如计划的那样。事实上，也可以把它吸收到 $\dbinom{-k-2}j^{-1}$ 之中。双重吸收表明暗中可能会有更多的抵消。是的，将新的求和项中的每一部分都展开成阶乘，并回到二项式系数，就给出了一个可以对 $k$ 求和的公式：
$$
\begin{aligned}S_m&=\frac{m!n!}{(m+n+1)!}\sum_{j\geqslant0}(-1)^j\binom{m+n+1}{n+1+j}\sum_k\binom{n+1+j}{k+j+1}\binom{-n-1}k\\&=\frac{m!n!}{(m+n+1)!}\sum_{j\geqslant0}(-1)^j\binom{m+n+1}{n+1+j}\binom jn~. \end{aligned}
$$
> 他们指望我们在一页便条纸上对此加以验证。
根据 $(5.24)$，对所有整数 $j$ 求和的和式为零。因此 $-S_m$ 是对应 $j<0$ 时的和式。
为了对 $j<0$ 计算 $-S_m$，我们用 $-k-1$ 代替 $j$ 并对 $k\geqslant0$ 求和：
$$
\begin{aligned}S_m&=\frac{m!n!}{(m+n+1)!}\sum_{k\geqslant0}(-1)^k\binom{m+n+1}{n-k}\binom{-k-1}n\\&=\frac{m!n!}{(m+n+1)!}\sum_{k\leqslant n}(-1)^{n-k}\binom{m+n+1}k\binom{k-n-1}n\\&=\frac{m!n!}{(m+n+1)!}\sum_{k\leqslant n}(-1)^k\binom{m+n+1}k\binom{2n-k}n\\&=\frac{m!n!}{(m+n+1)!}\sum_{k\leqslant2n}(-1)^k\binom{m+n+1}k\binom{2n-k}n~. \end{aligned}
$$
最后应用 $(5.25)$，就得到答案：
$$
S_m=(-1)^n\frac{m!n!}{(m+n+1)!}\binom mn=(-1)^nm^{\underline n}m^{\underline{-n-1}}~.
$$
我们最好还是验证一下。当 $n=2$ 时，得到
$$
S_m=\frac1{m+1}-\frac6{m+2}+\frac6{m+3}=\frac{m(m-1)}{(m+1)(m+2)(m+3)}~.
$$
我们的推导要求 $m$ 是一个整数，但是其结果对所有实数 $m$ 都成立，因为量 $(m+1)^{\overline{n+1}}S_m$ 是关于 $m$ 的次数 $\leqslant n$ 的多项式。
## 5.3 处理的技巧 TRICKS OF THE TRADE
接下来，我们观察三种技术，它们大大强化了我们已经学习过的一些方法。
**技巧 1：取一半**
> 这真应该称作 $1/2$ 技巧。
许多恒等式都包含一个任意实数 $r$。当 $r$ 为 “整数减去二分之一” 时，二项式系数 $\dbinom rk$ 可以写成外表很不相同的二项式系数的乘积。这将会导致一类新的恒等式，它们极其容易处理。
研究这是如何奏效的一种方法是从**加倍公式**（duplication formula）
$$
r^{\underline k}\bigg(r-\frac12\bigg)^{\underline k}=(2r)^{\underline{2k}}/2^{2k}~,\quad\text{整数 }k\geqslant0\tag{5.34}
$$
开始。如果我们将下降幂展开并将左边的因子交替书写，则此恒等式就是显然的：\
$$
\begin{aligned}&\phantom{=~}r\bigg(r-\frac12\bigg)(r-1)\bigg(r-\frac32\bigg)\cdots(r-k+1)\bigg(r-k+\frac12\bigg)\\&=\frac{(2r)(2r-1)\cdots(2r-2k+1)}{2\times2\times\cdots\times2}~.\end{aligned}
$$
现在我们可以在两边除以 $k!^2$，这就得到
$$
\binom rk\binom{r-1/2}k=\binom{2r}{2k}\binom{2k}k\bigg/2^{2k}~,\quad k\text{ 是整数.}\tag{5.35}
$$
如果令 $k=r=n$，其中 $n$ 是一个整数，这就得到
$$
\binom{n-1/2}n=\binom{2n}n\bigg/2^{2n}~,\quad n\text{ 是整数.}\tag{5.36}
$$
而反转上指标又给出另外一个有用的公式：
$$
\binom{-1/2}n=\bigg(\frac{-1}4\bigg)^n\binom{2n}n~,\quad n\text{ 是整数.}\tag{5.37}
$$
例如，当 $n=4$ 时有
> ……我们对半分……
$$
\begin{aligned}\binom{-1/2}4&=\frac{(-1/2)(-3/2)(-5/2)(-7/2)}{4!}\\&=\bigg(\frac{-1}2\bigg)^4\frac{1\times3\times5\times7}{1\times2\times3\times4}\\&=\bigg(\frac{-1}4\bigg)^4\frac{1\times3\times5\times7\times2\times4\times6\times8}{1\times2\times3\times4\times1\times2\times3\times4}=\bigg(\frac{-1}4\bigg)^4\binom84~. \end{aligned}
$$
注意我们是如何将奇数的乘积变成阶乘的。
恒等式 $(5.35)$ 有一个有趣的推论。设 $r=\dfrac12n$，并对所有整数 $k$ 求和。根据 $(5.23)$，其结果就是
$$
\begin{align}\sum_k\binom n{2k}\binom{2k}k2^{-2k}&=\sum_k\binom{n/2}k\binom{(n-1)/2}k\notag\\&=\binom{n-1/2}{\lfloor n/2\rfloor}~,\quad\text{整数 }n\geqslant0~,\tag{5.38}\end{align}
$$
因为要么 $n/2$ 等于 $\lfloor n/2\rfloor$，要么 $(n-1)/2$ 等于 $\lfloor n/2\rfloor$，这是一个非负整数！
我们还可以利用范德蒙德卷积 $(5.27)$ 来导出
$$
\sum_k\binom{-1/2}k\binom{-1/2}{n-k}=\binom{-1}n=(-1)^n~,\quad\text{整数 }n\geqslant0~.
$$
将 $(5.37)$ 的值代入就给出
$$
\begin{aligned}\binom{-1/2}k\binom{-1/2}{n-k}&=\bigg(\frac{-1}4\bigg)^k\binom{2k}k\bigg(\frac{-1}4\bigg)^{n-k}\binom{2(n-k)}{n-k}\\&=\frac{(-1)^n}{4^n}\binom{2k}k\binom{2n-2k}{n-k}~;\end{aligned}
$$
这就是和为 $(-1)^n$ 者。因此我们就有一个关于帕斯卡三角形的 “中间的” 元素的惊人性质：
$$
\sum_k\binom{2k}k\binom{2n-2k}{n-k}=4^n~,\quad\text{整数 }n\geqslant0~.\tag{5.39}
$$
例如，$\dbinom00\dbinom63+\dbinom21\dbinom42+\dbinom42\dbinom21+\dbinom63\dbinom00=1\times20+2\times6+6\times2+20\times1=64=4^3$。
对第一个技巧的这些阐释表明了，明智的做法是将形如 $\dbinom{2k}k$ 的二项式系数改变成形如 $\dbinom{n-1/2}k$ 的二项式系数，其中 $n$ 是某个适当的整数（通常是 $0$、$1$ 或者 $k$），这样所得到的公式可能会简单很多。
**技巧 2：高阶差分**
我们早先看到了，有可能计算级数 $\dbinom nk(-1)^k$ 而不是 $\dbinom nk$ 的部分和。事实表明，带有交错符号的二项式系数 $\dbinom nk(-1)^k$ 有许多重要的应用。其中一个原因是：这样的系数与 2.6 节中定义的差分算子 $\Delta$ 有密切的关系。
函数 $f$ 在点 $x$ 的差分 $\Delta f$ 是
$$
\Delta f(x)=f(x+1)-f(x)~;
$$
如果再次应用 $\Delta$，我们就得到二阶差分
$$
\begin{aligned}\Delta^2f(x)=\Delta f(x+1)-\Delta f(x)&=\big(f(x+2)-f(x+1)\big)-\big(f(x+1)-f(x)\big)\\&=f(x+2)-2f(x+1)+f(x)~,\end{aligned}
$$
这与二阶导数类似。类似地，我们有
$$
\begin{aligned}&\Delta^3f(x)=f(x+3)-3f(x+2)+3f(x+1)-f(x)~,\\&\Delta^4f(x)=f(x+4)-4f(x+3)+6f(x+2)-4f(x+1)+f(x)~;\end{aligned}
$$
如此等等。带有交错符号的二项式系数出现在这些公式之中。
一般来说，$n$ 阶差分是
$$
\Delta^nf(x)=\sum_k\binom nk(-1)^{n-k}f(x+k)~,\quad\text{整数 }n\geqslant0~.\tag{5.40}
$$
这个公式容易用归纳法证明，但是，还有一个很好的方法可以直接证明它，就是利用初等算子理论。回想 2.6 节我们曾经用规则
$$
\mathrm Ef(x)=f(x+1)
$$
定义了平移算子 $\mathrm E$，从而算子 $\Delta$ 就是 $E-1$，其中 $1$ 是由法则 $1f(x)=f(x)$ 定义的恒等算子。根据二项式定理，
$$
\Delta^n=(\mathrm E-1)^n=\sum_k\binom nk\mathrm E^k(-1)^{n-k}~.
$$
这是一个以算子作为元素的等式，它等价于 $(5.40)$，因为 $\mathrm E^k$ 就是将 $f(x)$ 变成 $f(x+k)$ 的算子。
当我们考虑负的下降幂时，就会出现一个有趣而重要的情形。设 $f(x)=(x-1)^{\underline{-1}}=1/x$。那么，根据法则 $(2.45)$ 就有 $\Delta f(x)=(-1){x-1}^{\underline{-2}}$，$\Delta^2f(x)=(-1)(-2)(x-1)^{\underline{-3}}$，一般地有
$$
\Delta^n\big((x-1)^{\underline{-1}}\big)=(-1)^{\underline n}(x-1)^{\underline{-n-1}}=(-1)^n\frac{n!}{x(x+1)\cdots(x+n)}~.
$$
现在等式 $(5.40)$ 告诉我们
$$
\sum_k\binom nk\frac{(-1)^k}{x+k}=\frac{n!}{x(x+1)\cdots(x+n)}=x^{-1}\binom{x+n}n^{-1}~,\quad x\notin\{0,-1,\cdots\,\!,-n\}~.\tag{5.41}
$$
例如，
$$
\begin{aligned}&\phantom{=~}\frac1x-\frac4{x+1}+\frac6{x+2}-\frac4{x+3}+\frac1{x+4}\\&=\frac{4!}{x(x+1)(x+2)(x+3)(x+4)}=1\bigg/x\binom{x+4}4~.\end{aligned}
$$
$(5.41)$ 中的这个和式就是 $n!/\big(x(x+1)\cdots(x+n)\big)$ 的部分分式展开。
从正的下降幂也能得到有意义的结果。如果 $f(x)$ 是一个 $d$ 次多项式，则差分 $\Delta f(x)$ 是一个 $d-1$ 次多项式，于是 $\Delta^df(x)$ 是一个常数，而当 $n>d$ 时有 $\Delta^nf(x)=0$。这个极端重要的事实简化了许多公式。
更仔细的观察能得到更多的信息。设
$$
f(x)=a_dx^d+a_{d-1}x^{d-1}+\cdots+a_1x^1+a_0x^0
$$
是任意一个 $d$ 次多项式。在第 6 章里我们将会看到，能将通常幂表示成为下降幂的和式（例如，$x^2=x^{\underline2}+x^{\underline1}$）。从而存在系数 $b_d,b_{d-1},\cdots\,\!,b_1,b_0$，使得
$$
f(x)=b_dx^{\underline d}+b_{d-1}x^{\underline{d-1}}+\cdots+b_1x^{\underline1}+b_0x^{\underline0}~.
$$
（事实表明 $b_d=a_d$ 且 $b_0=a_0$，但是介于它们之间的系数以更为复杂的方式联系在一起。）对 $0\leqslant k\leqslant d$ 设 $c_k=k!b_k$。那么
$$
f(x)=c_d\binom xd+c_{d-1}\binom x{d-1}+\cdots+c_1\binom x1+c_0\binom x0~;
$$
从而，任何多项式都可以表示成二项式系数的倍数之和。这样一个展开式称为 $f(x)$ 的**牛顿级数**，因为艾萨克 · 牛顿广泛地使用过它。
在这一章的前面我们曾经注意到，加法公式意味着
$$
\Delta\Bigg(\hspace{-0.25em}\binom xk\hspace{-0.25em}\Bigg)=\binom x{k-1}~.
$$
这样一来，根据归纳法，牛顿级数的 $n$ 阶差分是非常简单的：
$$
\Delta^nf(x)=c_d\binom x{d-n}+c_{d-1}\binom x{d-1-n}+\cdots+c_1\binom x{1-n}+c_0\binom x{-n}~.
$$
如果现在令 $x=0$，那么除了满足 $k-n=0$ 的项之外，右边所有的项 $c_k\dbinom x{k-n}$ 都是零。从而
$$
\Delta^nf(0)=\begin{cases}c_n~,&n\leqslant d~;\\0~,&n>d~.\end{cases}
$$
于是 $f(x)$ 的牛顿级数就是
$$
f(x)=\Delta^df(0)\binom xd+\Delta^{d-1}f(0)\binom x{d-1}+\cdots+\Delta f(0)\binom x1+f(0)\binom x0~.
$$
例如，假设 $f(x)=x^3$。容易计算出
$$
\def\arraystretch{1.25}\begin{matrix}f(0)=0~,\quad f(1)=1~,\quad f(2)=8~,\quad f(3)=27~;\\\Delta f(0)=1~,\quad\Delta f(1)=7~,\quad\Delta f(2)=19~;\\\Delta^2f(0)=6~,\quad\Delta^2f(1)=12~;\\\Delta^3f(0)=6~.\end{matrix}
$$
所以其牛顿级数是 $x^3=6\dbinom x3+6\dbinom x2+1\dbinom x1+0\dbinom x0$。
对 $x=0$ 利用 $(5.40)$，公式 $\Delta^nf(0)=c_n$ 也可以表述成下面的方式：
$$
\sum_k\binom nk(-1)^k\Bigg(c_0\binom k0+c_1\binom k1+c_2\binom k2+\cdots\Bigg)=(-1)^nc_n~,\quad\text{整数 }n\geqslant0~.
$$
这里 $\big<c_0,c_1,c_2,\cdots\big>$ 是一个任意的系数序列，对所有 $k\geqslant0$，无限和式 $c_0\dbinom k0+c_1\dbinom k1+c_2\dbinom k2+\cdots$ 实际上都是有限的，所以收敛性不成问题。特别地，我们可以证明重要的恒等式
$$
\sum_k\binom nk(-1)^k\big(a_0+a_1k+\cdots+a_nk^n\big)=(-1)^nn!a_n~,\quad\text{整数 }n\geqslant0~,\tag{5.42}
$$
因为多项式 $a_0+a_1k+\cdots+a_nk^n$ 总可以写成牛顿级数 $c_0\dbinom k0+c_1\dbinom k1+\cdots+c_n\dbinom kn$（其中 $c_n=n!a_n$）。
许多初看起来毫无希望求解的和式，实际上可以利用 $n$ 阶差分的思想几乎不费什么力气就能求和。例如，我们来考虑恒等式
$$
\sum_k\binom nk\binom{r-sk}n(-1)^k=s^n~,\quad\text{整数 }n\geqslant0~.\tag{5.43}
$$
这看起来真不错，因为它与我们迄今所见过的任何恒等式都迥然不同。但是，一旦我们注意到求和项中对问题有影响的因子 $\dbinom nk(-1)^k$，实际上就容易理解了，因为函数
$$
f(k)=\binom{r-sk}n=\frac1{n!}(-n)^ns^nk^n+\cdots=(-1)^ns^n\binom kn+\cdots
$$
是关于 $k$ 的一个 $n$ 次多项式，其首项系数为 $(-1)^ns^n/n!$。于是 $(5.43)$ 不过就是 $(5.42)$ 的一个应用而已。
我们在假设 $f(x)$ 是一个多项式的条件下讨论了牛顿级数，还看到了无穷的牛顿级数
$$
f(x)=c_0\binom x0+c_1\binom x1+c_2\binom x2+\cdots
$$
也是有意义的，因为当 $x$ 是非负整数时，这样的和式总是有限的。正如在多项式的情形一样，我们对公式 $\Delta^nf(0)=c_n$ 的推导在无限的情形依然成立，所以我们有一般的恒等式
$$
f(x)=f(0)\binom x0+\Delta f(0)\binom x1+\Delta^2f(0)\binom x2+\Delta^3f(0)\binom x3+\cdots~,\quad\text{整数 }x\geqslant0~.\tag{5.44}
$$
这个公式对任何定义在非负整数 $x$ 上的函数 $f(x)$ 都成立。此外，如果右边对其他的 $x$ 的值收敛，它就以一种自然的方式定义了 “插入” $f(x)$ 的函数。（有无穷多种方式插入函数值，所以我们不可能断言 $(5.44)$ 对所有使得该无穷级数收敛的 $x$ 均为真。例如，如果我们令 $f(x)=\sin(\pi x)$，则在所有整数点处都有 $f(x)=0$，所以 $(5.44)$ 的右边恒为零，但是其左边在所有非整数的 $x$ 处都不等于零。）
牛顿级数是有限微积分对无限微积分中的泰勒级数的回应。恰如泰勒级数可以写成
$$
g(a+x)=\frac{g(a)}{0!}x^0+\frac{g'(a)}{1!}x^1+\frac{g''(a)}{2!}x^2+\frac{g'''(a)}{3!}x^3+\cdots
$$
一样，$f(x)=g(a+x)$ 的牛顿级数也可以写成
$$
g(a+x)=\frac{g(a)}{0!}x^{\underline0}+\frac{\Delta g(a)}{1!}x^{\underline1}+\frac{\Delta^2g(a)}{2!}x^{\underline2}+\frac{\Delta^3g(a)}{3!}x^{\underline3}+\cdots~.\tag{5.45}
$$
> （由于 $\mathrm E=1+\Delta$，$\mathrm E^x=\sum_k\dbinom xk\Delta^k$，$\mathrm E^xg(a)=g(a+x)$。）
（这与 $(5.44)$ 相同，因为当 $f(x)=g(a+x)$ 时对所有 $n\geqslant0$ 都有 $\Delta^nf(0)=\Delta^ng(a)$。）当 $g$ 是一个多项式或者当 $x=0$ 时，泰勒级数和牛顿级数都是有限的。此外，当 $x$ 是正整数时，牛顿级数是有限的。而在相反的情形，这个和式对特殊的 $x$ 的值有可能收敛，也有可能不收敛。如果当 $x$ 不是非负整数时牛顿级数收敛，它实际上也可能收敛于一个**异于** $g(a+x)$ 的值，因为牛顿级数 $(5.45)$ 仅仅依赖于间隔开的函数值 $g(a),g(a+1),g(a+2),\cdots$。
二项式定理提供了收敛的牛顿级数的一个例子。设 $g(x)=(1+z)^x$，其中 $z$ 是一个固定的复数，它满足 $|z|<1$。那么 $\Delta g(x)=(1+z)^{x+1}-(1+z)^x=z(1+z)^x$，故而 $\Delta^ng(x)=z^n(1+z)^x$。在这种情形，无穷的牛顿级数
$$
g(a+x)=\sum_n\Delta^ng(a)\binom xn=(1+z)^a\sum_n\binom xnz^n
$$
对所有的 $x$ 都收敛于 “正确的” 值 $(1+z)^{a+x}$。
詹姆斯 · 斯特林曾试图利用牛顿级数来将阶乘函数推广到非整数的值。首先他找到了系数 $S_n$，使得
$$
x!=\sum_nS_n\binom xn=S_0\binom x0+S_1\binom x1+S_2\binom x2+\cdots\tag{5.46}
$$
是对 $x=0,x=1,x=2,\cdots$ 成立的恒等式。但是他发现，得到的级数除了当 $x$ 是非负整数之外均不收敛。所以他再次尝试，这一次他记
> “由于这些项增加得非常快，它们的差也将构成一个发散的级数，它阻碍了抛物线的纵坐标趋向于真实；于是在这种及类似的情形中，我插入这些项的对数，它们的差构成一个收敛得很快的级数。” ——斯特林
$$
\ln x!=\sum_ns_n\binom xn=s_0\binom x0+s_1\binom x1+s_2\binom x2+\cdots~.\tag{5.47}
$$
现在 $\Delta(\ln x!)=\ln(x+1)!-\ln x!=\ln(x+1)$，从而由 $(5.40)$ 有
$$
\begin{aligned}s_n&=\Delta^n(\ln x!)\Big|_{x=0}\\&=\Delta^{n-1}(\ln(x+1))\Big|_{x=0}\\&=\sum_k\binom{n-1}k(-1)^{n-1-k}\ln(k+1)~. \end{aligned}
$$
于是其系数就是 $s_0=s_1=0$，$s_2=\ln2$，$s_3=\ln3-2\ln2=\ln\dfrac34$，$s_4=\ln4-3\ln3+3\ln2=\ln\dfrac{32}{27}$ 等。按照这种方法，斯特林得到了一个的确收敛的级数（尽管他没有证明这点）。实际上，他的级数对所有 $x>-1$ 都收敛。这样他就能满意地计算出 $\dfrac12!$。习题 88 讲述了余下的故事。
> （直到 19 世纪才建立了收敛性的证明。）
**技巧 3：反演**
我们刚刚对牛顿级数所得到的法则 $(5.45)$ 的一种特殊情形，可以用下面的方式改写：
$$
g(n)=\sum_k\binom nk(-1)^kf(k)\iff f(n)=\sum_k\binom nk(-1)^kg(k)~.\tag{5.48}
$$
$f$ 和 $g$ 之间的这种对偶关系称为**反演公式**（inversion formula），它有点像我们在第 4 章里遇到的默比乌斯反演公式 $(4.56)$ 和 $(4.61)$。反演公式告诉我们如何求解 “隐式递归式”，其中一个未知的序列嵌入在一个和式中。
> 对它做反演：“$\text{zmb ppo}$”。
例如，$g(n)$ 可能是一个已知的函数，而 $f(n)$ 则可能是未知的，我们或许找到了一种方法来证明 $g(n)=\sum_k\dbinom nk(-1)^kf(k)$。这样，$(5.48)$ 就使得我们可以将 $f(n)$ 表示成已知数值的和式。
利用本章开头的基本方法，我们能直接证明 $(5.48)$。如果对所有 $n\geqslant0$ 有 $g(n)=\sum_k\dbinom nk(-1)^kf(k)$，那么
$$
\begin{aligned}\sum_k\dbinom nk(-1)^kg(k)&=\sum_k\binom nk(-1)^k\sum_j\binom kj(-1)^jf(j)\\&=\sum_jf(j)\sum_k\binom nk(-1)^{k+j}\binom kj\\&=\sum_jf(j)\sum_k\binom nj(-1)^{k+j}\binom{n-j}{k-j}\\&=\sum_jf(j)\binom nj\sum_k(-1)^k\binom{n-j}k\\&=\sum_jf(j)\binom nj[n-j=0]=f(n)~. \end{aligned}
$$
当然，另一个方向的证明是同样的，因为 $f$ 与 $g$ 之间的这种关系是对称的。
我们将它应用于 “足球胜利问题”，以此作为例子对 $(5.48)$ 加以描述。获胜足球队的 $n$ 个球迷将他们的帽子高高抛向空中，这些帽子随机落下来，每一顶帽子落向这 $n$ 个球迷中的一个。有多少种方式 $h(n,k)$ 使得恰好有 $k$ 个球迷得到他们自己的帽子？
例如，如果 $n=4$ 且帽子和球迷被命名为 $A,B,C,D$，帽子落下的 $4!=24$ 种方式生成了下面的合法拥有者的个数：
$$
\begin{aligned}\mathrm{ABCD\quad}&4&\mathrm{BACD\quad}&2&\mathrm{CABD\quad}&1&\mathrm{DABC\quad}&0\\\mathrm{ABDC\quad}&2&\mathrm{BADC\quad}&0&\mathrm{CADB\quad}&0&\mathrm{DACB\quad}&1\\\mathrm{ACBD\quad}&2&\mathrm{BCAD\quad}&1&\mathrm{CBAD\quad}&2&\mathrm{DBAC\quad}&1\\\mathrm{ACDB\quad}&1&\mathrm{BCDA\quad}&0&\mathrm{CBDA\quad}&1&\mathrm{DBCA\quad}&2\\\mathrm{ADBC\quad}&1&\mathrm{BDAC\quad}&0&\mathrm{CDAB\quad}&0&\mathrm{DCAB\quad}&0\\\mathrm{ADCB\quad}&2&\mathrm{BDCA\quad}&1&\mathrm{CDBA\quad}&0&\mathrm{DCBA\quad}&0 \end{aligned}
$$
于是 $h(4,4)=1$；$h(4,3)=0$；$h(4,2)=6$；$h(4,1)=8$；$h(4,0)=9$。
注意，选取 $k$ 个幸运的帽子拥有者的方法数（即 $\dbinom nk$）乘以剩下的 $n-k$ 顶帽子均回不到其合法拥有者手中的方法数，即 $h(n-k,0)$，我们就能确定 $h(n,k)$ 的值。如果一个排列移动了每一项，那么这个排列称为**重排**（derangement），$n$ 个物体的重排个数有时就用符号 “$n¡$” 来表示，读作 “$n$ `倒阶乘`（$n$ subfactorial）。于是 $h(n-k,0)=(n-k)¡$，我们就有一般的公式
$$
h(n,k)=\binom nkh(n-k,0)=\binom nk(n-k)¡.
$$
（倒阶乘记号并非是标准的，也并不是一个好想法，不过让我们尝试用它一段时间，看看能否逐渐喜欢上它。如果 “$n¡$” 不合适，我们总可以求助于 “$D_n$” 或者其他什么东西。）
如果对 $n¡$ 有一个封闭形式，我们的问题就能解决，所以来看看我们能发现什么。有一个得到递归式的简便方法，因为对所有的 $k$，$h(n,k)$ 的和式就是 $n$ 顶帽子的排列总数：
$$
n!=\sum_kh(n,k)=\sum_k\binom nk(n-k)¡=\sum_k\binom nkk¡,\quad\text{整数 }n\geqslant0~.\tag{5.49}
$$
（在最后一步我们将 $k$ 变成了 $n-k$，将 $\dbinom n{n-k}$ 变成了 $\dbinom nk$。）利用这个隐式递归式，我们可以计算所有想要的 $h(n,k)$：
$$
\def\arraystretch{1.25}\begin{array}{c|llllll}\hspace{0.5em}n\hspace{0.5em}&h(n,0)\hspace{1em}&h(n,1)\hspace{1em}&h(n,2)\hspace{1em}&h(n,3)\hspace{1em}&h(n,4)\hspace{1em}&h(n,5)\hspace{1em}&h(n,6)\hspace{1em}\\\hline0&\hspace{0.5em}1\\1&\hspace{0.5em}0&\hspace{0.5em}1\\2&\hspace{0.5em}1&\hspace{0.5em}0&\hspace{0.5em}1\\3&\hspace{0.5em}2&\hspace{0.5em}3&\hspace{0.5em}0&\hspace{0.5em}1\\4&\hspace{0.5em}9&\hspace{0.5em}8&\hspace{0.5em}6&\hspace{0.5em}0&\hspace{0.5em}1\\5&\hspace{0.5em}44&\hspace{0.5em}45&\hspace{0.5em}20&\hspace{0.5em}10&\hspace{0.5em}0&\hspace{0.5em}1\\6&\hspace{0.5em}265&\hspace{0.5em}264&\hspace{0.5em}135&\hspace{0.5em}40&\hspace{0.5em}15&\hspace{0.5em}0&\hspace{0.5em}1\end{array}
$$
例如，这里给出怎样计算 $n=4$ 这一行的过程：最右边两个数字是显然的——恰只有一种方法使所有的帽子正确地落到其所有者头上，且没有任何方法能使得正好有三顶帽子落到其所有者的头上。（那第四个球迷得到谁的帽子呢？）当 $k=2$ 以及 $k=1$ 时，我们可以利用关于 $h(n,k)$ 的等式给出 $h(4,2)=\dbinom42h(2,0)=6\times1=6$ 以及 $h(4,1)=\dbinom41h(3,0)=4\times2=8$。对 $h(4,0)$ 我们无法利用这个等式；说得更准确些，我们可以用这个等式，但是它给出 $h(4,0)=\dbinom40h(4,0)$，此式为真但无用。另取一法，我们可以利用关系式 $h(4,0)+8+6+0+1=4!$ 得出 $h(4,0)=9$，这就是 $4¡$ 的值。类似地，$n¡$ 依赖于 $k¡$ 的值（$k<n$）。
> 与生活的艺术相同，数学的艺术是知道哪些真理是无用的。
我们怎样来求解像 $(5.49)$ 这样的递归式呢？这很容易：它有 $(5.48)$ 的形式，在其中取 $g(n)=n!$ 以及 $f(k)=(-1)^kk¡$。故而其解为
$$
n¡=(-1)^n\sum_k\binom nk(-1)^kk!~.
$$
不过，这并不真的是解；它是一个和式，如果有可能应该表达成封闭形式。不过它比递归式要更好。这个和式可以简化，因为 $k!$ 可以和 $\dbinom nk$ 中的一个隐藏的 $k!$ 抵消，所以我们来尝试这样做，得到
$$
n¡=\sum_{0\leqslant k\leqslant n}\frac{n!}{(n-k)!}(-1)^{n+k}=n!\sum_{0\leqslant k\leqslant n}\frac{(-1)^k}{k!}~.\tag{5.50}
$$
剩下的这个和式快速收敛于 $\sum_{k\geqslant0}(-1)^k/k!=\mathrm e^{-1}$。事实上，从这个和式中被排除的项是
$$
\begin{aligned}n!\sum_{k>n}\frac{(-1)^k}{k!}&=\frac{(-1)^{n+1}}{n+1}\sum_{k\geqslant0}(-1)^k\frac{(n+1)!}{(k+n+1)!}\\&=\frac{(-1)^{n+1}}{n+1}\left(1-\frac1{n+2}+\frac1{(n+2)(n+3)}-\cdots\right)~,\end{aligned}
$$
而括号中的量介于 $1$ 和 $1-\dfrac1{n+2}=\dfrac{n+1}{n+2}$ 之间。于是，$n¡$ 与 $n!/\mathrm e$ 之间的差的绝对值大约是 $1/n$；更精确地说，它介于 $1/(n+1)$ 与 $1/(n+2)$ 之间。但 $n¡$ 是一个整数。于是，如果 $n>0$，那么它必定就是我们将 $n!/\mathrm e$ 舍入到最近的整数时所得到的数。这样就得到了所求的封闭形式：
$$
n¡=\left\lfloor\frac{n!}{\mathrm e}+\frac12\right\rfloor+[n=0]~.\tag{5.51}
$$
这就是没有任何球迷得到属于自己的帽子的方法数。当 $n$ 很大时，知道这个事件发生的概率更有意义。如果我们假设那 $n!$ 种排列中的每一个都是等可能的——因为帽子被抛得极高——这个概率是
$$
\frac{n¡}{n!}=\frac{n!/\mathrm e+O(1)}{n!}\sim\frac1{\mathrm e}=0.367\cdots~.
$$
> 棒球迷：$0.367$ 也是 Ty Cobb 职业生涯的平均击球率，这是一个空前的记录。这会是一个巧合吗？
故当 $n$ 变大时所有帽子没回到其合法拥有者手中的概率接近于 $37\%$。
顺便要提及的是，倒阶乘的递归式 $(5.49)$ 恰好与 $(5.46)$ 相同，这是斯特林在试图推广阶乘函数时所考虑过的第一个递归式。因此 $S_k=k¡$。这些系数是如此巨大，毫不奇怪，无穷级数 $(5.46)$ 对非整数的 $x$ 发散。
> （嗨，等一等，你夸大了事实。Cobb 的平均击球率是 $4191/11429\approx0.366~699$，而 $1/\mathrm e\approx0.367~879$。不过，如果 Wade Boggs 有几个真正好的赛季，或许……）
在结束这个问题之前，我们简要地介绍两个有趣的模式，它们是在小的 $h(n,k)$ 的表中跳入我们眼帘的。首先，看起来在表中全由数字 $0$ 组成的对角线的下方的数 $1,3,6,10,15,\cdots$ 就是三角形数。这个观察到的事实容易证明，由于表中那些元素都是 $h(n,n-2)$ 的值，故我们有
$$
h(n,n-2)=\binom n{n-2}2¡=\binom n2~.
$$
又看起来前面两列的数相差 $\pm1$。这是否总是正确的呢？是的，
$$
\begin{aligned}h(n,0)-h(n,1)&=n¡-n(n-1)¡\\&=\left(n!\sum_{0\leqslant k\leqslant n}\frac{(-1)^k}{k!}\right)-\left(n(n-1)!\sum_{0\leqslant k\leqslant n-1}\frac{(-1)^k}{k!}\right)\\&=n!\frac{(-1)^n}{n!}=(-1)^n~. \end{aligned}
$$
换句话说，$n¡=n(n-1)¡+(-1)^n$。对于重排数来说，这是一个比我们以前得到的所有递归式都要简单得多的递归式。
现在我们来做反演（invertion）。如果我们对在 $(5.41)$ 中得到的公式
> 但是逆温层（inversion）是有害烟雾的来源。
$$
\sum_k\binom nk\frac{(-1)^k}{x+k}=\frac1x\binom{x+n}n^{-1}
$$
做反演，就得到
$$
\frac x{x+n}=\sum_{k\geqslant0}\binom nk(-1)^k\binom{x+k}k^{-1}~.
$$
这个结果很有意思，但并不是真正意义上的新结果。如果我们在 $\dbinom{x+k}k$ 中反转上指标，不过是再次发现了恒等式 $(5.33)$。
## 5.4 生成函数 GENERATING FUNCTIONS
现在我们来讨论整本书中最重要的思想，即**生成函数**（generating functions）的概念。我们希望用某种方式处理的一个无限序列 $\big\langle a_0,a_1,a_2,\cdots\big\rangle$，可以很方便地表示成一个辅助变量 $z$ 的**幂级数**（power series）：
$$
A(z)=a_0+a_1z+a_2z^2+\cdots=\sum_{k\geqslant0}a_kz^k~.\tag{5.52}
$$
用字母 $z$ 作为这个辅助变量的名字是合适的，因为我们经常要把 $z$ 看成是复数。复变函数论在其公式中习惯用 “$\mathrm z$”，幂级数（又称为解析函数或者全纯函数）是这个理论的中心议题。
在接下来的几章里我们将会看到许多生成函数。的确，整个第 7 章都在讨论它们。我们现在的目标是直接引入基本概念，展示生成函数和二项式系数研究之间的关系。
生成函数是有用的，因为它是表示整个无限序列的单个量。我们常常建立一个或者多个生成函数，然后操控这些函数，直到了解许多关于它们的知识，最后再来观察系数，从而求解问题。凭着小小的运气，我们将会知道有关这种函数的足够多的知识，从而明白对于它的系数我们需要了解什么。
如果 $A(z)$ 是任意一个幂级数 $\sum\limits_{k\geqslant0}a_kz^k$，我们将会发现记
$$
[z^n]A(z)=a_n\tag{5.53}
$$
> （关于这个概念的历史和用途的讨论，见参考文献 [223]。）
是很方便的；换言之，$[z^n]A(z)$ 表示 $A(z)$ 中 $z^n$ 的系数。
如同 $(5.52)$，设 $A(z)$ 是 $\big\langle a_0,a_1,a_2,\cdots\big\rangle$ 的生成函数，$B(z)$ 是另一个序列 $\big\langle b_0,b_1,b_2,\cdots\big\rangle$ 的生成函数，那么乘积 $A(z)B(z)$ 就是幂级数
$$
\begin{aligned}&\phantom{=~}(a_0+a_1z+a_2z^2+\cdots)(b_0+b_1z+b_2z^2+\cdots)\\&=a_0b_0+(a_0b_1+a_1b_0)z+(a_0b_2+a_1b_1+a_2b_0)z^2+\cdots~; \end{aligned}
$$
这个乘积中 $z^n$ 的系数是
$$
a_0b_n+a_1b_{n-1}+\cdots+a_nb_0=\sum_{k=0}^na_kb_{n-k}~.
$$
这样一来，如果想要计算任何一个具有一般形式
$$
c_n=\sum_{k=0}^na_kb_{n-k}\tag{5.54}
$$
的和式，而且知道生成函数 $A(z)$ 和 $B(z)$，我们就有
$$
c_n=[z^n]A(z)B(z)~.
$$
由 $(5.54)$ 所定义的序列 $\big\langle c_n\big\rangle$ 称为序列 $\big\langle a_n\big\rangle$ 和 $\big\langle b_n\big\rangle$ 的**卷积**（convolution），两个序列的下标相加等于一个给定量的所有乘积之和，就得到它们的 “卷积”。前面的主要内容就是与其生成函数的乘法相对应的序列的卷积。
生成函数提供了强有力的方法来发现和证明恒等式。例如，二项式定理告诉我们 $(1+z)^r$ 是序列 $\Bigg<\dbinom r0,\dbinom r1,\dbinom r2,\cdots\Bigg>$ 的生成函数：
$$
(1+z)^r=\sum_{k\geqslant0}\binom rkz^k~.
$$
类似地，
$$
(1+z)^s=\sum_{k\geqslant0}\binom skz^k~.
$$
如果将这些等式相乘，我们就得到另外一个生成函数：
$$
(1+z)^r(1+z)^s=(1+z)^{r+s}
$$
现在激动人心的时刻到了：让这个等式的两边 $z^n$的系数相等就给出
$$
\sum_{k=0}^n\binom rk\binom s{n-k}=\binom{r+s}n~.
$$
我们就发现了范德蒙德卷积 $(5.27)!$。
> $(5.27)!=(5.27)(4.27)(3.27)(2.27)(1.27)(0.27)!$。
这种做法既优美也很容易，我们再尝试另外一个。这一次我们用 $(1-z)^r$，它是序列 $\Bigg<(-1)^n\dbinom rn\Bigg>=\Bigg<\dbinom r0,-\dbinom r1,\dbinom r2,\cdots\Bigg>$ 的生成函数。用 $(1+z)^r$ 来乘就得出另外一个生成函数，这个生成函数的系数是我们已知的：
$$
(1-z)^r(1+z)^r=(1-z^2)^r~.
$$
现在让两边 $z^n$ 的系数相等就给出等式
$$
\sum_{k=0}^n\binom rk\binom r{n-k}(-1)^k=(-1)^{n/2}\binom r{n/2}[n\text{ 是偶数}].\tag{5.55}
$$
我们应该用一两个小数值对此进行检查。例如，当 $n=3$ 时结果是
$$
\binom r0\binom r3-\binom r1\binom r2+\binom r2\binom r1-\binom r3\binom r0=0~.
$$
每一个正的项都和一个对应的负的项相互抵消。而且只要 $n$ 为奇数（在这样的情形下和式并不令人感兴趣），就会发生同样的事情。但是当 $n$ 是偶数（例如 $n=2$）时，我们得到一个与范德蒙德卷积不同的非平凡的和式：
$$
\binom r0\binom r2-\binom r1\binom r1+\binom r2\binom r0=2\binom r2-r^2=-r~.
$$
所以 $n=2$ 时，$(5.55)$ 也成立。事实证明，$(5.30)$ 是新恒等式 $(5.55)$ 的一个特殊情形。
二项式系数也出现在其他一些生成函数之中，最值得注意的是下面两个重要的恒等式，其中下指标保持不动而上指标变化：
$$
\begin{align}\frac1{(1-z)^{n+1}}&=\sum_{k\geqslant0}\binom{n+k}nz^k~,\quad\text{整数 }n\geqslant0~;\tag{5.56}\\\frac{z^n}{(1-z)^{n+1}}&=\sum_{k\geqslant0}\binom knz^k~,\quad\text{整数 }n\geqslant0~.\tag{5.57}\end{align}
$$
> 如果你有一支荧光笔，应该将这两个等式做上记号。
这里的第二个等式恰好是第一个等式乘以 $z^n$，也就是说 “向右移动” $n$ 位。第一个恒等式正好是稍加变形的二项式定理的一个特殊情形：如果我们用 $(5.13)$ 展开 $(1-z)^{-n-1}$，则 $z^k$ 的系数是 $\dbinom{-n-1}k(-1)^k$，它可以通过反转上指标改写成 $\dbinom{k+n}k$ 或者 $\dbinom{n+k}n$。这些特殊情形值得特别关注，因为它们在应用中出现得如此频繁。
当 $n=0$ 时，我们得到特殊情形的一个特例，即几何级数：
$$
\frac1{1-z}=1+z+z^2+z^3+\cdots=\sum_{k\geqslant0}z^k~.
$$
这是序列 $\big<1,1,1,\cdots\big>$ 的生成函数，它特别有用，因为其他任何序列与这个序列的卷积都是和式的序列：当对所有 $k$ 都有 $b_k=1$ 时，$(5.54)$ 就转化为
$$
c_n=\sum_{k=0}^na_k~.
$$
这样一来，如果 $A(z)$ 是求和项 $\big<a_0,a_1,a_2,\cdots\big>$ 的生成函数，那么 $A(z)/(1-z)$ 就是和式 $\big<c_0,c_1,c_2,\cdots\big>$ 的生成函数。
我们在与帽子和足球迷相关联的问题中用反演法解决了的重排问题，也能以一种有趣的方式用生成函数再次获得解答。基本递归式
$$
n!=\sum_k\binom nk(n-k)¡
$$
可以表达成卷积的形式，如果我们将 $\dbinom nk$ 展开成阶乘并在两边用 $n!$ 除：
$$
1=\sum_{k=0}^n\frac1{k!}\frac{(n-k)¡}{(n-k)!}~.
$$
序列 $\bigg<\dfrac1{0!},\dfrac1{1!},\dfrac1{2!},\cdots\bigg>$ 的生成函数就是 $\mathrm e^z$。所以，如果令
$$
D(z)=\sum_{k\geqslant0}\frac{k¡}{k!}z^k~,
$$
则由卷积（递归式）知
$$
\frac1{1-z}=\mathrm e^zD(z)~.
$$
对 $D(z)$ 求解就给出
$$
D(z)=\frac1{1-z}\mathrm e^{-z}=\frac1{1-z}\bigg(\frac1{0!}z^0-\frac1{1!}z^1+\frac1{2!}z^2+\cdots\bigg)~.
$$
现在让 $z^n$ 的系数相等就得到
$$
\frac{n¡}{n!}=\sum_{k=0}^n\frac{(-1)^k}{k!}~;
$$
这是我们早先曾经用反演法得到的公式。
到目前为止，我们对生成函数的探索已经对于我们用更加笨拙的方法获得的一些已知结果给出了巧妙的证明。但是除了 $(5.55)$，我们还没有用生成函数得到任何新的结果。现在我们已经准备好得出某些新的更加惊人的结果。有两类幂级数，它们能产生出特别丰富的关于二项式系数的恒等式。我们来定义**广义二项级数**（generalized binomial series）$\mathcal B_t(z)$ 以及**广义指数级数**（generalized exponential series）$\mathcal E_t(z)$ 如下：
$$
\mathcal B_t(z)=\sum_{k\geqslant0}(tk)^{\underline{k-1}}\frac{z^k}{k!}~;\quad\mathcal E_t(z)=\sum_{k\geqslant0}(tk+1)^{k-1}\frac{z^k}{k!}~.\tag{5.58}
$$
我们将在 7.5 节里证明：这些函数满足恒等式
$$
\mathcal B_t(z)^{1-t}-\mathcal B_t(z)^{-t}=z~;\quad\mathcal E_t(z)^{-t}\ln\mathcal E_t(z)=z~.\tag{5.59}
$$
在 $t=0$ 的特殊情形下，我们有
$$
\mathcal B_0(z)=1+z~;\quad\mathcal E_0(z)=\mathrm e^z~.
$$
这就解释了为什么带有参数 $t$ 的级数称为 “广义” 二项级数以及指数级数。
下面两对恒等式对所有实数 $r$ 都成立：
$$
\begin{align}&\begin{aligned}&\mathcal B_t(z)^r=\sum_{k\geqslant0}\binom{tk+r}k\frac r{tk+r}z^k~;\\&\hspace{12em}\mathcal E_t(z)^r=\sum_{k\geqslant0}r\frac{(tk+r)^{k-1}}{k!}z^k~;\end{aligned}\tag{5.60}\\&\begin{aligned}&\frac{\mathcal B_t(z)^r}{1-t+t\mathcal B_t(z)^{-1}}=\sum_{k\geqslant0}\binom{tk+r}kz^k~;\\&\hspace{12em}\frac{\mathcal E_t(z)^r}{1-zt\mathcal E_t(z)^t}=\sum_{k\geqslant0}\frac{(tk+r)^k}{k!}z^k~;\end{aligned}\tag{5.61}\end{align}
$$
> 广义二项级数 $\mathcal B_t(z)$ 是在 18 世纪 50 年代由约翰 · 海因里希 · 兰伯特发现的。几年以后，他注意到，它的幂满足 $(5.60)$ 中的第一个恒等式。
> 习题 84 说明了如何从 $(5.60)$ 推导出 $(5.61)$。
（当 $tk+r=0$ 时，对于如何理解 $z^k$ 的系数还得稍加小心，每个系数都是 $r$ 的一个多项式。例如，$\mathcal E_t(z)^r$ 的常数项是 $r(0+r)^{-1}$，即便 $r=0$ 时它也等于 $1$。）
由于等式 $(5.60)$ 和 $(5.61)$ 对所有的 $r$ 都成立，所以当我们把与不同的幂 $r$ 和 $s$ 对应的级数乘在一起时，就得到非常一般的恒等式。例如，
$$
\begin{aligned}\mathcal B_t(z)^r\frac{\mathcal B_t(z)^s}{1-t+t\mathcal B_t(z)^{-1}}&=\sum_{k\geqslant0}\binom{tk+r}k\frac r{tk+r}z^k\sum_{j\geqslant0}\binom{tj+s}jz^j\\&=\sum_{n\geqslant0}z^n\sum_{k\geqslant0}\binom{tk+r}k\frac r{tk+r}\binom{t(n-k)+s}{n-k}~. \end{aligned}
$$
这个幂级数必定等于
$$
\frac{\mathcal B_t(z)^{r+s}}{1-t+t\mathcal B_t(z)^{-1}}=\sum_{n\geqslant0}\binom{tn+r+s}nz^n~;
$$
于是我们可以令 $z^n$ 的系数相等，这就得到恒等式
$$
\sum_k\binom{tk+r}k\binom{t(n-k)+s}{n-k}\frac r{tk+r}=\binom{tn+r+s}n~,\quad n\text{ 是整数 },
$$
它对所有实数 $r$、$s$ 和 $t$ 都成立。当 $t=0$ 时，这个恒等式就化为范德蒙德卷积。（如果在这个公式中碰巧有 $tk+r$ 等于零，则分母的因子 $tk+r$ 应当视为与二项式系数的分子中的 $tk+r$ 抵消掉了。这个恒等式的两边都是关于 $r$、$s$ 和 $t$ 的多项式。）当我们用 $\mathcal B_t(z)^s$ 等等乘以 $\mathcal B_t(z)^r$ 时有类似的恒等式成立，表 5-5 给出了这些结果。
$$
\def\arraystretch{2}\begin{matrix}\textbf{表 5-5}\qquad\textbf{一般的卷积恒等式（对整数 }\boldsymbol{n\geqslant0}\textbf{ 成立）}\\\hline\hline\begin{align}&\sum_k\binom{tk+r}k\binom{tn-tk+s}{n-k}\frac r{tk+r}=\binom{tn+r+s}n\tag{5.62}\\[1ex]&\sum_k\binom{tk+r}k\binom{tn-tk+s}{n-k}\frac r{tk+r}\cdot\frac s{tn-tk+s}=\binom{tn+r+s}n\frac{r+s}{tn+r+s}~.\tag{5.63}\\[1ex]&\sum_k\binom nk(tk+r)^k(tn-tk+s)^{n-k}\frac r{tk+r}=(tn+r+s)^n~.\tag{5.64}\\[1ex]&\sum_k\binom nk(tk+r)^k(tn-tk+s)^{n-k}\frac r{tk+r}\cdot\frac s{tn-tk+s}=(tn+r+s)^n\frac{r+s}{tn+r+s}~.\tag{5.65}\end{align}\end{matrix}
$$
我们已经知道，观察一般结果的特殊情形一般来说是个好想法。例如，如果令 $t=1$ 会怎样呢？广义二项级数 $\mathcal B_t(z)$ 是很简单的，它正好是
$$
\mathcal B_1(z)=\sum_{k\geqslant0}z^k=\frac1{1-z}~;
$$
于是，$\mathcal B_1(z)$ 并没有给出任何从范德蒙德卷积还不知道的东西。但是 $\mathcal E_1(z)$ 是一个重要的函数
$$
\mathcal E(z)=\sum_{k\geqslant0}(k+1)^{k-1}\frac{z^k}{k!}=1+z+\frac32z^2+\frac83z^3+\frac{125}{24}z^4+\cdots,\tag{5.66}
$$
我们以前没见过它，它满足基本恒等式
$$
\mathcal E(z)=\mathrm e^{\mathrm z\varepsilon(z)}~.
$$
> 啊哈！这是迭代的幂函数 $\mathcal E(\ln z)=z^{z^{z^\cdots}}$，我对它时常感到好奇。$Z{\small Z}{\scriptsize Z}{\tiny Z}\cdots\,\!
这个函数首先是由欧拉和艾森斯坦研究的，它出现在大量的应用中。
广义二项级数的特殊情形 t=2 和 t=-1 特别重要，因为它们的系数一而再、再而三地在有递归构造的问题中出现。因此，显式展现这些级数以备将来参考是有用的：
\begin{align}\mathcal B_2(z)&=\sum_k\binom{2k}k\frac{z^k}{1+k}=\sum_k\binom{2k+1}k\frac{z^k}{1+2k}=\frac{1-\sqrt{1-4z}}{2z}\tag{5.68}\\\mathcal B_{-1}(z)&=\sum_k\binom{1-k}k\frac{z^k}{1-k}=\sum_k\binom{2k-1}k\frac{(-z)^k}{1-2k}=\frac{1+\sqrt{1+4z}}2\tag{5.69}\\\mathcal B_2(z)^r&=\sum_k\binom{2k+r}k\frac r{2k+r}z^k&\tag{5.70}\\\mathcal B_{-1}(z)^r&=\sum_k\binom{r-k}k\frac r{r-k}z^k\tag{5.71}\\\frac{\mathcal B_2(z)^r}{\sqrt{1-4z}}&=\sum_k\binom{2k+r}kz^k\tag{5.72}\\\frac{\mathcal B_{-1}(z)^{r+1}}{\sqrt{1+4z}}&=\sum_k\binom{r-k}kz^k\tag{5.73}\end{align}
$$
\def\arraystretch{1.25}\begin{array}{l|lllllllllll}n&0&1&2&3&4&5&6&7&8&9&10\\\hline C_n\hspace{0.5em}&1\hspace{0.5em}&1\hspace{0.5em}&2\hspace{0.5em}&5\hspace{0.5em}&14\hspace{0.5em}&42\hspace{0.5em}&132\hspace{0.5em}&429\hspace{0.5em}&1430\hspace{0.5em}&4862\hspace{0.5em}&16796\hspace{0.5em}\end{array}
$$
$\mathcal B_{-1}(z)$ 的系数本质上相同，不过在开头多出一个 $1$，且其他数的符号是交替的：$\langle1,1,-1,2,-5,14,\cdots\rangle$。从而 $\mathcal B_{-1}(z)=1+z\mathcal B_2(-z)$。我们还有 $\mathcal B_{-1}(z)=\mathcal B_2(-z)^{-1}$。
在本节最后，我们推导 $(5.72)$ 和 $(5.73)$ 的一个重要推论，这个推论是一种关系，它表明函数 $\mathcal B_{-1}(z)$ 和 $\mathcal B_2(-z)$ 之间有进一步的联系：
$$
\frac{\mathcal B_{-1}(z)^{n+1}-(-z)^{n+1}\mathcal B_2(-z)^{n+1}}{\sqrt{1+4z}}=\sum_{k\leqslant n}\binom{n-k}kz^k~.
$$
这个公式成立是因为当 $k>n$ 时 $(-z)^{n+1}\mathcal B_2(-z)^{n+1}\big/\sqrt{1+4z}$ 中 $z^k$ 的系数是
$$
\begin{aligned}[z^k]\frac{(-z)^{n+1}\mathcal B_2(-z)^{n+1}}{\sqrt{1+4z}}&=(-1)^{n+1}[z^{k-n-1}]\frac{\mathcal B_2(-z)^{n+1}}{\sqrt{1+4z}}\\&=(-1)^{n+1}(-1)^{k-n-1}[z^{k-n-1}]\frac{\mathcal B_2(z)^{n+1}}{\sqrt{1-4z}}\\&=(-1)^k\binom{2(k-n-1)+n+1}{k-n-1}\\&=(-1)^k\binom{2k-n-1}{k-n-1}=(-1)^k\binom{2k-n-1}k\\&=\binom{n-k}k=[z^k]\frac{\mathcal B_{-1}(z)^{n+1}}{\sqrt{1+4z}}~,\end{aligned}
$$
其中的项适当地相互抵消了，现在我们可以用 $(5.68)$ 和 $(5.69)$ 来得到封闭形式
$$
\sum_{k\leqslant n}\binom{n-k}kz^k=\frac1{\sqrt{1+4z}}\left(\left(\frac{1+\sqrt{1+4z}}2\right)^{n+1}-\left(\frac{1-\sqrt{1+4z}}2\right)^{n+1}\right),\quad\text{整数 }n\geqslant0~.\tag{5.74}
$$
（特殊情形 $z=-1$ 出现在 5.2 节的问题 3 中。由于数 $\dfrac12(1\pm\sqrt{-3})$ 是六次单位根，故而和式 $\sum_{k\leqslant n}\dbinom{n-k}k(-1)^k$ 有我们在该问题中观察到的周期性。）类似地，我们可以将 $(5.70)$ 和 $(5.71)$ 组合起来以抵消大的系数并得到
$$
\sum_{k<n}\binom{n-k}k\frac n{n-k}z^k=\left(\frac{1+\sqrt{1+4z}}2\right)^n+\left(\frac{1-\sqrt{1+4z}}2\right)^n~,\quad\text{整数 }n>0~.\tag{5.75}
$$
## 5.5 超几何函数 HYPERGEOMETRIC FUNCTIONS
我们对二项式系数所用的方法在运用时是非常有效的，但是我们也必须承认，它们常常显得是为某一特定目的而设计的，更像是技巧而不是通用的技术手段。当我们在解决一个问题时，常需要追寻多个方向，我们可能发现自己是在原地转圈，二项式系数就像变色龙一样，很容易改变它们的外表。因此我们自然要问，是不是并不存在某种统一的原理，可以用来一起系统地处理一大批二项式系数的求和。幸运的是，答案是肯定的。这种统一原理的基础是一种称为**超几何函数**（hypergeometric series）的无穷和式的理论。
> 它们甚至比变色龙更加变化多端，我们可以对它们进行剖析并用不同的方式将它们放回到一起。
对超几何函数的研究是许多年前由欧拉、高斯以及黎曼发起的，事实上，这样的级数现在仍然是重要的研究对象。但是超几何学有一个有点令人望而生畏的记号，我们需要花一点时间来适应它。
> 任何经受数百年考验而留存下来的令人敬畏的记号必定都是真正有用的。
一般的超几何函数是关于 $z$ 且带有 $m+n$ 个参数的幂级数，它用上升的阶乘幂定义如下：
$$
F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)=\sum_{k\geqslant0}\frac{a_1^{\overline k}\cdots a_m^{\overline k}z^k}{b_1^{\overline k}\cdots b_n^{\overline k}~k!}~.\tag{5.76}
$$
为避免用零作除数，诸个 $b$ 均不为零或者负整数。除此之外，诸个 $a$ 以及 $b$ 可以是我们希望取的任何数。记号 $F(a_1,\cdots\,\!,a_m;b_1,\cdots\,\!,b_n;z)$ 是 $(5.76)$ 中两行形式的表示法的一种替代表达方式，因为有时候一行的排印效果更好。诸个 $a$ 称为**上参数**（upper parameter），它们出现在 $F$ 的项的分子之中；诸个 $b$ 称为**下参数**（lower parameter），它们出现在分母之中。最后的量 $z$ 称为**自变量**（argument）。
标准的参考书常用 $_mF_n$ 而代替 $F$ 做为有 $m$ 个上参数和 $n$ 个下参数的超几何函数的名字。但是额外多出来的下标使公式变得凌乱，如果我们被强制一遍又一遍地写出这些下标，还会浪费时间。我们可以统计一下有多少个参数，这样我们通常并不需要额外增加不必要的累赘。
许多重要的函数都作为一般的超几何函数的特例出现。的确，这就是超几何级数为何如此强有力的原因。例如，当 $m=n=0$ 时最简单的情形出现：这里根本就没有参数，而我们则得到熟悉的级数
$$
F(~\big|z)=\sum_{k\geqslant0}\frac{z^k}{k!}=\mathrm e^z~.
$$
实际上当 $m$ 或者 $n$ 为零时这个记号有一点不整齐。我们可以在上面和下面额外加上 “$1$” 以避免这种情况：
$$
F\bigg(\begin{matrix}1\\1\end{matrix}\Bigg|z\bigg)=\mathrm e^z~.
$$
如果我们消除了在分子和分母中都出现的一个参数，或者插入两个完全相同的参数，那么一般来说，我们并没有改变这个函数。
下一个最简单的情形是 $m=1$，$a_1=1$ 以及 $n=0$。我们将参数变成 $m=2$，$a_1=a_2=1$，$n=1$ 以及 $b_1=1$，这样就有 $n>0$。因为 $1^{\overline k}=k!$，事实表明这个级数也是熟知的：
$$
F\bigg(\begin{matrix}1,1\\1\end{matrix}\Bigg|z\bigg)=\sum_{k\geqslant0}z^k=\frac1{1-z}~.
$$
它是我们的老朋友几何级数。$F(a_1,\cdots\,\!,a_m;b_1,\cdots\,\!,b_n;z)$ 称为超几何级数，因为它包含几何级数 $F(1,1;1;z)$ 这一个非常特殊的情形。
事实上，利用 $(5.13)$ 和 $(5.14)$，$m=1$ 以及 $n=0$ 时的一般情形容易求和成封闭形式
$$
F\bigg(\begin{matrix}a,1\\1\end{matrix}\Bigg|z\bigg)=\sum_{k\geqslant0}a^{\overline k}\frac{z^k}{k!}=\sum_k\binom{a+k-1}kz^k=\frac1{(1-z)^a}~.\tag{5.77}
$$
如果用 $-a$ 代替 $a$，用 $-z$ 代替 $z$，我们就得到二项式定理
$$
F\bigg(\begin{matrix}-a,1\\1\end{matrix}\Bigg|{-z}\bigg)=(1+z)^a~.
$$
用负整数作为上参数会使得无穷级数变成有限的，这是由于只要 $k>a\geqslant0$ 且 $a$ 是一个整数，就有 $(-a)^{\overline k}=0$。
$m=0$，$n=1$ 时的一般情形是另外一个有名的级数，但它在离散数学的文献中不是那么广为人知：
$$
F\bigg(\begin{matrix}1\\b,1\end{matrix}\Bigg|z\bigg)=\sum_{k\geqslant0}\frac{(b-1)!}{(b-1+k)!}\frac{z^k}{k!}=I_{b-1}(2\sqrt z)\frac{(b-1)!}{z^{(b-1)/2}}~.\tag{5.78}
$$
这个函数 $I_{b-1}$ 称为阶为 $b-1$ 的**修正贝塞尔函数**（modified Bessel function）。其特殊情形 $b=1$ 给出 $F\bigg(\begin{matrix}1\\1,1\end{matrix}\Bigg|z\bigg)=I_0(2\sqrt z)$，它就是有趣的级数 $\sum_{k\geqslant0}z^k/k!^2$。
$m=n=1$ 的特殊情形称为**合流超几何级数**（confluent hypergeometric series），它常用字母 $M$ 来表示：
$$
F\bigg(\begin{matrix}a\\b\end{matrix}\Bigg|z\bigg)=\sum_{k\geqslant0}\frac{a^{\overline k}}{b^{\overline k}}\frac{z^k}{k!}=M(a,b,z)~.\tag{5.79}
$$
这个在工程中有重要应用的函数是由恩斯特 · 库默尔给出的。
到目前为止，我们中少数人会对为什么没有讨论无穷级数 $(5.76)$ 的收敛性感到奇怪。其答案是，如果我们只是简单地将 $z$ 用做一个形式符号，就可以忽略收敛性。不难验证，如果其系数 $\alpha_k$ 在一个域中，那么形如 $\sum_{k\geqslant n}\alpha_kz^k$（其中 $-\infty<n<\infty$）的无限和式构成一个域。我们可以对这样的和式作加、减、乘、除、微分以及函数的复合，而不用担心其收敛性，我们得到的任何恒等式都将仍然形式地为真。例如，超几何函数 $F\bigg(\begin{matrix}1,1,1\\1\end{matrix}\Bigg|z\bigg)=\sum_{k\geqslant0}k!z^k$ 对任何非零的 $z$ 都不收敛、然而在第 7 章里我们将会看到，我们仍然能用它来求解问题。另一方面，只要我们用一个特别的数值代替 $z$，就的确需要确信这个无限和式是有良好定义的。
> 我们也没有讨论 $(5.56)$、$(5.57)$、$(5.58)$ 等的收敛性。
在复杂性上再提升一步，就是所有超几何级数中最著名的那个了。事实上，它就是在大约 1870 年之前人们所研究的超几何级数，而到了 1870 年，一切都推广到了任意的 $m$ 和 $n$。这个级数有两个上参数和一个下参数：
$$
F\bigg(\begin{matrix}a,b\\c\end{matrix}\Bigg|z\bigg)=\sum_{k\geqslant0}\frac{a^{\overline k}b^{\overline k}z^k}{c^{\overline k}k!}~.\tag{5.80}
$$
它常常被称为**高斯超几何级数**，因为它的许多精巧性质都是高斯在他 1812 年的博士论文中首先证明的，虽然欧拉和普法夫已经发现了它的一些重要性质。它的一个重要的特殊情形是
> “今天，在许多大学的物理学、工程学甚至数学专业的学生所学习的函数中，即使不是 $100\%$，也必定有 $95\%$ 的函数被这单个的符号 $F(a,b;c;x)$ 所涵盖。” ——W. W. 索耶
$$
\begin{aligned}\ln(1+z)=zF\bigg(\begin{matrix}1,1\\2\end{matrix}\Bigg|{-z}\bigg)&=z\sum_{k\geqslant0}\frac{k!k!}{(k+1)!}\frac{(-z)^k}{k!}\\&=z-\frac{z^2}2+\frac{z^3}3-\frac{z^4}4+\cdots~.\end{aligned}
$$
注意：$z^{-1}\ln(1+z)$ 是一个超几何函数，但是 $\ln(1+z)$ 本身不可能是超几何函数，因为超几何级数在 $z=0$ 时取值总是 $1$。
到目前为止，超几何学除了借助名人提高身份之外，并没有真正为我们做任何实事。不过我们已经看到，若干个很不相同的函数全都可以看成是超几何的，而这就是我们接下来关注的要点。我们将会看到一大类和式都可以用一种 “标准的” 方式表示成超几何级数，从而我们对与二项式系数有关的事实将会有一个好的归类系统。
什么样的级数是超几何的？如果我们观察其相邻项的比值就容易回答这个问题了：
$$
F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)=\sum_{k\geqslant0}t_k~,\quad t_k=\frac{a_1^{\overline k}\cdots a_m^{\overline k}z^k}{b_1^{\overline k}\cdots b_n^{\overline k}~k!}~.
$$
其第一项是 $t_0=1$，其他项的比值由
$$
\begin{aligned}\frac{t_{k+1}}{t_k}&=\frac{a_1^{\overline{k+1}}\cdots a_m^{\overline{k+1}}}{a_1^{\overline k}\cdots a_m^{\overline k}}\frac{b_1^{\overline k}\cdots b_n^{\overline k}}{b_1^{\overline{k+1}}\cdots b_n^{\overline{k+1}}}\frac{k!}{(k+1)!}\frac{z^{k+1}}{z^k}\\&=\frac{(k+a_1)\cdots(k+a_m)z}{(k+b_1)\cdots(k+b_n)(k+1)}\end{aligned}\tag{5.81}
$$
给出。这是 $k$ 的一个**有理函数**（rational function），也就是说，它是关于 $k$ 的多项式之商。根据代数基本定理，$k$ 的任何有理函数在复数范围内都可以分解并表达成这种形式。诸个 $a$ 是分子中多项式的根的相反数，而诸个 $b$ 则是分母中多项式的根的相反数。如果分母不是已经包含特殊的因子 $(k+1)$，我们可以将 $(k+1)$ 添加到分子和分母中。剩下一个固定因子，我们称之为 $z$。于是超几何级数恰好就是首项为 $1$ 且项的比值 $t_{k+1}/t_k$ 是 $k$ 的有理函数的那些级数。
例如，假设给定一个无穷级数，它的项的比值
$$
\frac{t_{k+1}}{t_k}=\frac{k^2+7k+10}{4k^2+1}
$$
是 $k$ 的一个有理函数。分子多项式正好分解成两个因子 $(k+2)(k+5)$，而分母则分解成 $4(k+i/2)(k-i/2)$。由于分母缺少了所要求的因子 $(k+1)$，我们就把项的比值写成
$$
\frac{t_{k+1}}{t_k}=\frac{(k+2)(k+5)(k+1)(1/4)}{(k+i/2)(k-i/2)(k+1)}~,
$$
我们能很快写出其结果：给定的级数就是
$$
\sum_{k\geqslant0}t_k=t_0F\bigg(\begin{matrix}2,5,1\\i/2,-i/2\end{matrix}\Bigg|1/4\bigg)~.
$$
因此，在有可能存在这样的表示时，我们就有了一般性的方法来求出一个给定量 $S$ 的超几何表示。首先我们将 $S$ 写成一个无穷级数，其首项不是零。我们选择一个记号，使得这个级数就是 $\sum_{k\geqslant0}t_k$，其中 $t_0\ne0$。然后我们计算 $t_{k+1}/t_k$。如果项的比值不是 $k$ 的有理函数，我们就不走运了；否则，我们就可将它表示成 $(5.81)$ 的形式，这就给出参数 $a_1,\cdots\,\!,a_m,b_1\cdots\,\!,b_n$ 和自变量 $z$，使得 $S=t_0F(a_1,\cdots\,\!,a_m;b_1,\cdots\,\!,b_n;z)$。
> （现在是做热身题第 11 题的好时机。）
如果我们希望强调项的比值的重要性，高斯超几何级数可以写成循环分解的形式
$$
F\bigg(\begin{matrix}a,b\\c\end{matrix}\Bigg|z\bigg)=1+\frac a1\frac bcz\Bigg(1+\frac{a+1}2\frac{b+1}{c+1}z\bigg(1+\frac{a+2}3\frac{b+2}{c+2}z(1+\cdots)\bigg)\Bigg)~.
$$
现在我们来尝试对这一章早先得到的二项式系数恒等式重新用公式写成超几何的形式。例如让我们搞清楚，按照超几何的记号，平行求和法则
$$
\sum_{k\leqslant n}\binom{r+k}k=\binom{r+n+1}n~,\quad n\text{ 是整数}
$$
看起来像什么。我们需要将这个和式写成从 $k=0$ 开始的一个无穷级数，所以用 $n-k$ 代替 $k$：
$$
\sum_{k\geqslant0}\binom{r+n-k}{n-k}=\sum_{k\geqslant0}\frac{(r+n-k)!}{r!(n-k)!}=\sum_{k\geqslant0}t_k~.
$$
这个级数形式上是无穷的，但实际上是有限的，因为当 $k>n$ 时分母中的 $(n-k)!$ 使得 $t_k=0$。（以后我们将看到，对所有 $x$，$1/x!$ 都有定义，且当 $x$ 是负整数时有 $1/x!=0$。但是目前来说，在积累了更多的超几何方面的经验之前，我们并不在意忽略这样的技术性细节。）其项的比值是
$$
\begin{aligned}\frac{t_{k+1}}{t_k}=\frac{(r+n-k-1)!r!(n-k)!}{r!(n-k-1)!(r+n-k)!}&=\frac{n-k}{r+n-k}\\&=\frac{(k+1)(k-n)(1)}{(k-n-r)(k+1)}~.\end{aligned}
$$
此外，$t_0=\dbinom{r+n}n$。因此平行求和法则则等价于超几何恒等式
$$
\binom{r+n}nF\bigg(\begin{matrix}1,-n\\-n-r\end{matrix}\Bigg|1\bigg)=\binom{r+n+1}n~.
$$
从头到尾用 $\dbinom{r+n}n$ 来除就给出稍微简单一些的形式
$$
F\bigg(\begin{matrix}1,-n\\-n-r\end{matrix}\Bigg|1\bigg)=\frac{r+n+1}{r+1}~,\quad\text{如果 }\binom{r+n}n\ne0~.\tag{5.82}
$$
我们再做另外一个。在用 $m-k$ 代替了 $k$ 之后，恒等式 $(5.16)
\sum_{k\leqslant m}\binom rk(-1)^k=(-1)^m\binom{r-1}m~,\quad m\text{ 是整数}
的项的比值是 (k-m)/(r-m+k+1)=(k+1)(k-m)(1)/(k-m+r+1)(k+1) ，从而 (5.16) 就由
F\bigg(\begin{matrix}1,-m\\-m+r+1\end{matrix}\Bigg|1\bigg)
给出了封闭形式。这本质上与 (5.82) 左边的超几何函数相同，但改为用 m 代替 n 以及用 r+1 代替 -r 。于是恒等式 (5.16) 就已经能从 (5.82) （它是 (5.9) 的超几何形式）得到了。（我们发现容易用 (5.9) 来证明 (5.16) ，这已经不足为奇了。）
在进一步讨论之前，我们应该考虑一下退化的情形，因为当有一个下参数为零或是负整数时，超几何级数没有定义。我们通常是在 r 和 n 是正整数时应用平行求和恒等式，但 -n-r 是一个负整数且超几何级数 (5.76) 没有定义，这样我们怎么能认为 (5.82) 是合法的呢？答案是，我们可以在 \varepsilon\to0 时对 F\bigg(\begin{matrix}1,-n\\-n-r+\varepsilon\end{matrix}\Bigg|1\bigg) 取极限。
先是讲了重排，现在又讲退化。
在这一章的后面，我们会更加仔细地探讨这一点，目前我们只需知道某些分母可能会出问题。然而有趣的是，事实表明我们曾试图用超几何方式来表示的第一个和式是退化的。
在推导 (5.82) 的过程中，另一个可能的烦心之处是我们将 \dbinom{r+n-k}{n-k} 展开成了 (r+n-k)!/r!(n-k)! 。这个展开式当 r 是负整数时不成立，因为如果要使规则
（原来我们是对整数 r 证明了这些恒等式，并用多项式推理法指出它们在一般情形也成立。现在我们是首先证明它们对无理数 r 成立，并利用极限方法指出它们对整数也成立。）
0!=0\times(-1)\times(-2)\times\cdots\times(-m+1)\times(-m)!
成立，那么 (-m)! 必须是 \infty 。于是我们再次需要通过考虑当 \varepsilon\to0 时对 r+\varepsilon 取极限来逼近整数时的结果。
但是我们仅仅是在 r 为整数时才定义了阶乘的表示法 \dbinom rk=r!/k!(r-k)! 的！如果想要有效地处理超几何级数，就需要一个对所有复数都有定义的阶乘函数。幸运的是存在这样一个函数，而且它可以用多种方法加以定义。下面是 z! 的一个最有用的定义，它实际上是 1/z! 的定义：
\frac1{z!}=\lim_{n\to\infty}\binom{n+z}nn^{-z}~.\tag{5.83}
（见习题 21。欧拉在他 22 岁时就发现了这一点。）可以证明这个极限对所有复数 z 都存在，而且它仅当 z 是负整数时取值为零。另一个有意义的定义是
z!=\int_0^{\infty}t^z\mathrm e^{-t}\mathrm dt~,\quad\Re z>-1~.
这个积分仅当 z 的实部大于 -1 时存在，但是我们可以利用公式
z!=z(z-1)!
将这个定义延拓到所有的复数 z （负整数除外）。还有另外一个定义来自 (5.47) 中 \ln z! 的斯特林插值。所有这些方法都引出同一个广义阶乘函数。
还有很类似的函数，称为 \boldsymbol\Gamma 函数 （Gamma function），它与通常的阶乘之间的关系有点像上升幂与下降幂之间的关系。标准的参考书常常同时使用阶乘和 \Gamma 函数，如果必要的话，利用下面的公式
\begin{align}&\Gamma(z+1)=z!~;\tag{5.86}\\&(-z)!\Gamma(z)=\frac\pi{\sin\pi z}~,\tag{5.87} \end{align}
就可以很方便地在它们之间进行转换。
当 z 和 w 是任意的复数时，我们可以利用这些广义阶乘来定义广义阶乘幂：
当 \overline w 是 w 的复共轭时，如何对 z 取 \overline w 次幂？
\begin{align}z^{\underline w}&=\frac{z!}{(z-w)!}~;\tag{5.88}\\z^{\overline w}&=\frac{\Gamma(z+w)}{\Gamma(z)}~.\tag{5.89}\end{align}
仅有的限制性条件是，当这些公式给出 \infty/\infty 时，我们必须使用适当的极限值。（这些公式从来不会给出 0/0 ，因为阶乘和 \Gamma 函数的值从不为零。）z 和 w 无论是什么实数，二项式系数都可以写成
\binom zw=\lim_{\zeta\to z}\lim_{\omega\to w}\frac{\zeta!}{\omega!(\zeta-\omega)!}~.\tag{5.90}
我看到下指标首先到达它的极限。那就是为什么当 w 是负整数时 \dbinom zw 的值是零。当 z 是负整数且 w 不是整数时，其值是无穷。
有了广义阶乘作为工具，我们就可以回过头来实现将早先得到的恒等式转化为其超几何标准形式这一目标了。事实表明，二项式定理 (5.13) 简直就和 (5.77) 一个样，正如我们期待的那样。下面要尝试的最有趣的恒等式是范德蒙德卷积 (5.27) ：
\sum_k\binom rk\binom s{n-k}=\binom{r+s}n~,\quad n\text{ 是整数.}
这里的第 k 项是
t_k=\frac{r!}{(r-k)!k!}\frac{s!}{(s-n+k)!(n-k)!}~,
而我们也不再羞于将广义阶乘应用于这些表达式中，只要 t_k 包含一个像 (\alpha+k) 这样的因子（k 的前面是正号），由 (5.85) 就在项的比值 t_{k+1}/t_k 中得到 (\alpha+k+1)!/(\alpha+k)!=k+\alpha+1 。这就给对应的超几何级数增加了参数 “\alpha+1 ” ——如果 (\alpha+k)! 在 t_k 的分子之中，那么它就作为上参数，而在相反的情形它就作为下参数。类似地，一个像 (\alpha-k)! 这样的因子引出了 (\alpha-k-1)!/(\alpha-k)!=(-1)/(k-\alpha) ，这对于相反的参数集合（将上下参数的作用颠倒）的贡献是 “-\alpha ”，并且取超几何自变量的相反值。像 r! 这样与 k 无关的因子进入到 t_0 中，从项的比值中消失。利用这样的技巧，无需进一步的计算我们就能预知 (5.27) 的项的比值是
\frac{t_{k+1}}{t_k}=\frac{k-r}{k+1}\frac{k-n}{k+s-n+1}
乘以 (-1)^2=1 ，而范德蒙德卷积就变成了
\binom snF\bigg(\begin{matrix}-r,-n\\s-n+1\end{matrix}\Bigg|1\bigg)=\binom{r+s}n~.\tag{5.91}
当 z=1 以及当 b 是负整数时，一般来说我们可以用这个等式来确定 F(a,b;c;z) 。
我们来将 (5.91) 改写成这样一种形式，使得当需要对一个新的和式进行计算时查表很容易。这个结果显然就是
F\bigg(\begin{matrix}a,b\\c\end{matrix}\Bigg|1\bigg)=\frac{\Gamma(c-a-b)\Gamma(c)}{\Gamma(c-a)\Gamma(c-b)}~;\quad\text{整数 }b\leqslant0~,\quad\text{或者 }\Re c>\Re a+\Re b~.\tag{5.92}
范德蒙德卷积 (5.27) 仅仅适合上参数中的一个（比如 b ）是非正整数的情形，但是高斯证明了：当 a 、b 、c 是实部满足 \Re c>\Re a+\Re b 的复数时，(5.92) 也成立。在其他情形，无穷级数 F\bigg(\begin{matrix}a,b\\c\end{matrix}\Bigg|1\bigg) 并不收敛。当 b=-n 时，这个恒等式可以用阶乘幂代替 \Gamma 函数更方便地表示成：
几个星期以前，我们正在研究高斯在孩提时代所做的事。现在我们则在研究超越了其博士论文的内容。这是吓唬人还是别的什么？
F\bigg(\begin{matrix}a,-n\\c\end{matrix}\Bigg|1\bigg)=\frac{(c-a)^{\overline n}}{c^{\overline n}}=\frac{(a-c)^{\underline n}}{(-c)^{\underline n}}~,\quad\text{整数 }n\geqslant0~.\tag{5.93}
现在很清楚，表 5-3 中的全部 5 个恒等式都是范德蒙德卷积的特殊情形。当对退化的情形适当加以关注时，公式 (5.93) 包含了它们。
注意 (5.82) 正好是 (5.93) 在 a=1 时的特殊情形，因而我们不需要真的记住 (5.82) ，而且我们也并不真的需要能引出 (5.82) 的恒等式 (5.9) ，尽管表 5-4 说它是值得记住的。为了解决计算 \sum_{k\leqslant n}\dbinom{r+k}k 的问题，一个处理公式的计算机程序可以将这个和式转变成超几何形式并代入范德蒙德卷积的一般恒等式。
5.2 节中的问题 1 要求
\sum_{k\leqslant0}\binom mk\bigg/\binom nk
的值。这个问题对超几何学来说是很自然的，稍经训练，任何超几何学者都能一眼就看出 F(1,-m;-n;1) 的参数。嗯，这个问题还是范德蒙德卷积的另外一个特殊情形！
问题 2 和问题 4 中的和式同样产生出 F(2,1-n;2-m;1) 。（我们首先需要用 k+1 代替 k 。）而事实表明，问题 6 中 “令人惊悚的” 和式正是 F(n+1,-n;2;1) 。除了威力强大的范德蒙德卷积的改头换面的形式之外，对于和式而言是否不再有其他的东西了呢？
是的，正是这样，问题 3 稍有不同。它处理的是 (5.74) 中所考虑的一般和式 \sum_k\dbinom{n-k}kz^k 的一种特殊情形，而这就引导出封闭形式表达式
F\bigg(\begin{matrix}1+2\lceil n/2\rceil,-n\\1/2\end{matrix}\Bigg|{-z/4}\bigg)~.
在 (5.55) 中我们还证明了一些新的东西，那个时候我们研究了 (1-z)^r(1+z)^r 的系数：
F\bigg(\begin{matrix}1-c-2n,-2n\\c\end{matrix}\Bigg|-1\bigg)=(-1)^n\frac{(2n)!}{n!}\frac{(c-1)!}{(c+n-1)!}~,\quad\text{整数 }n\geqslant0~.
当这个公式被推广到复数时就称为库默尔公式 （Kummer's formula）：
Kummer 的发音与 summer 相似。
F\bigg(\begin{matrix}a,b\\1+b-a\end{matrix}\Bigg|-1\bigg)=\frac{(b/2)!}{b!}(b-a)^{\underline{b/2}}~.\tag{5.94}
是在 1836 年的夏天。
（恩斯特 · 库默尔于 1836 年证明了这个公式。）
将这两个公式进行比较是很有意思的。我们发现，用 1-2n-a 代替 c ，这两个结果是一致的，当且仅当 n 是正整数且
(-1)^n\frac{(2n)!}{n!}=\lim_{b\to-2n}\frac{(b/2)!}{b!}=\lim_{x\to-n}\frac{x!}{(2x)!}~.\tag{5.95}
例如 n=3 ，那么我们就应该有 -6!/3!=\lim_{x\to-3}x!/(2x)! 。我们知道 (-3)! 和 (-6)! 两者都是无限的，但是我们可以选择忽略这个困难并想象 (-3)!=(-3)(-4)(-5)(-6)! ，所以两次出现的 (-6)! 就会抵消。然而，必须抵制这样的诱惑，因为它们引导出了错误的答案！按照 (5.95) ，当 x\to-3 时 x!/(2x)! 的极限不是 (-3)(-4)(-5) ，而是 -6!/3!=(-4)(-5)(-6) 。
计算 (5.95) 中极限的正确方法是利用等式 (5.87) ，它将负变量的阶乘与正变量的 \Gamma 函数联系起来。如果我们用 -n-\varepsilon 代替 x ，并令 \varepsilon\to0 ，则两次应用 (5.87) 就给出
\frac{(-n-\varepsilon)!}{(-2n-2\varepsilon)!}\frac{\Gamma(n+\varepsilon)}{\Gamma(2n+2\varepsilon)}=\frac{\sin(2n+2\varepsilon)\pi}{\sin(n+\varepsilon)\pi}~.
现在 \sin(x+y)=\sin x\cos y+\cos x\sin y ，所以根据第 9 章的方法，正弦函数的这个比值就是
\frac{\cos2n\pi\sin2\varepsilon\pi}{\cos n\pi\sin\varepsilon\pi}=(-1)^n(2+O(\varepsilon))~.
于是，根据 (5.86) 我们就有
\lim_{\varepsilon\to0}\frac{(-n-\varepsilon)!}{(-2n-2\varepsilon)!}=2(-1)^n\frac{\Gamma(2n)}{\Gamma(n)}=2(-1)^n\frac{(2n-1)!}{(n-1)!}=(-1)^n\frac{(2n)!}{n!}~,
这正是我们所希望的。
让我们用超几何的方式来重新叙述这一章里至此见到的其他恒等式，以此完成我们的全面考察。(5.29) 中的三重二项和式可以写成
\begin{aligned}&\phantom{=~}F\bigg(\begin{matrix}1-a-2n,1-b-2n,-2n\\a,b\end{matrix}\Bigg|1\bigg)\\&=(-1)^n\frac{(2n)!}{n!}\frac{(a+b+2n-1)^{\overline n}}{a^{\overline n}b^{\overline n}}~,\quad\text{整数 }n\geqslant0~.\end{aligned}
当这个公式推广到复数时，它被称为迪克逊公式 （Dixon's formula）：
F\bigg(\begin{matrix}a,b,c\\1+c-a,1+c-b\end{matrix}\Bigg|1\bigg)=\frac{(c/2)!}{c!}\frac{(c-a)^{\underline{c/2}}(c-b)^{\underline{c/2}}}{(c-a-b)^{\underline{c/2}}}~,\Re a+\Re b<1+\Re c/2~.\tag{5.96}
我们遇到过的最一般的公式之一是三重二项和式 (5.28) ，它可推出 Saalschütz 恒等式 （Saalschütz's identity）：
（历史注记：在普法夫首先发表这个结果差不多 100 年之后，Saalschütz 独立发现了这个公式。当 n\to\infty 时取极限就得到等式 (5.92) 。）
\begin{aligned}F\bigg(\begin{matrix}a,b,-n\\c,a+b-c-n+1\end{matrix}\Bigg|1\bigg)&=\frac{(c-a)^{\overline n}(c-b)^{\overline n}}{c^{\overline n}(c-a-b)^{\overline n}}\\&=\frac{(a-c)^{\underline n}(b-c)^{\underline n}}{(-c)^{\underline n}(a+b-c)^{\underline n}}\end{aligned}~,\quad\text{整数 }n\geqslant0~.\tag{5.97}
这个公式给出了具有 3 个上参数和 2 个下参数的一般超几何级数在 z=1 时的值，只要上参数中有一个是非正的整数且 b_1+b_2=a_1+a_2+a_3+1 。（如果下参数之和比上参数之和大 2 ，而不是大 1 ，那么习题 25 的公式就可以用来表示 F(a_1,a_2,a_3;b_1,b_2;1) ，是用满足 Saalschütz 恒等式的两个超几何级数来表示。）
5.2 节问题 8 中艰难获得的恒等式约化为
\frac1{1+x}F\bigg(\begin{matrix}x+1,n+1,-n\\1,x+2\end{matrix}\Bigg|1\bigg)=(-1)^nx^{\underline n}x^{\underline{-n-1}}~.
多么令人遗憾！这就是 Saalschütz 恒等式 (5.97) 当 c=1 时的特殊情形。所以，如果直接进入超几何学，我们可能早就可以节省大量劳动了！
那么关于问题 7 呢？这个格外有杀伤力的和式给出公式
F\hspace{-0.2em}\left(\begin{matrix}n+1,m-n,1,\dfrac12\\\dfrac12m+1,\dfrac12m+\dfrac12,2 \end{matrix}\middle|1\right)=\frac mn~,\quad\text{整数 }n\geqslant m>0~,
这是我们见到的第一种有三个下参数的情形，所以它看起来很新颖，但其实不然。利用习题 26，它的左边可以用
F\hspace{-0.2em}\left(\begin{matrix}n,m-n-1,-\dfrac12\\\dfrac12m,\dfrac12m-\dfrac12\end{matrix}\middle|1\right)-1
的一个倍数来代替，于是 Saalschütz 恒等式再次获得成功。
是的，这是另一个令人泄气的经历，但它也是领会超几何方法威力的另一个理由。
（历史注记：超几何级数与二项式系数恒等式的重大关系首先是由 George Andrews 于 1974 年指出的。）
表 5-6 中的卷积恒等式没有超几何形式的等价结果，因为它们的项的比值仅当 t 是整数时才是 k 的有理函数。即便当 t=1 时，等式 (5.64) 和 (5.65) 都不是超几何的。但是我们可以注意到 t 取小整数值时 (5.62) 所得出的结果：
\begin{aligned}
&F\hspace{-0.2em}\left(\begin{matrix}\dfrac12r,\dfrac12r+\dfrac12,-n,-n-s\\r+1,-n-\dfrac12s,-n-\dfrac12s+\dfrac12\end{matrix}\middle|1\right)=\binom{r+s+2n}n\bigg/\binom{s+2n}n~;\\[1ex]
&F\hspace{-0.2em}\left(\begin{matrix}\dfrac13r,\dfrac13r+\dfrac13,\dfrac13r+\dfrac23,-n,-n-\dfrac12s,-n-\dfrac12s+\dfrac12\\\dfrac12r+\dfrac12,\dfrac12r+1,-n-\dfrac13s,-n-\dfrac13s+\dfrac13,-n-\dfrac13s+\dfrac23\end{matrix}\middle|1\right),\\
&\phantom{F\hspace{-0.2em}\left(\begin{matrix}\dfrac12r,\dfrac12r+\dfrac12,-n,-n-s\\r+1,-n-\dfrac12s,-n-\dfrac12s+\dfrac12\end{matrix}\middle|1\right)}=\binom{r+s+3n}n\bigg/\binom{s+3n}n~.
\end{aligned}
当量 (r,s,n) 分别被 (1,m-2n-1,n-m) 取代时，其中的第一个公式再次给出了问题 7 的结果。
最后，“出人意料的” 和式 (5.20) 给了我们一个意想不到的超几何恒等式，事实表明这个恒等式是相当有教益的。我们来放慢速度加以观察。首先我们可以将它变换成一个无限的和式
\sum_{k\leqslant m}\binom{m+k}k2^{-k}=2m\iff\sum_{k\geqslant0}\binom{2m-k}{m-k}2^k=2^{2m}~.
由 (2m-k)!2^k/m!(m-k)! 得到项的比值是 2(k-m)/(k-2m) ，所以对 z=2 ，我们就有一个超几何恒等式
\binom{2m}mF\bigg(\begin{matrix}1,-m\\-2m\end{matrix}\Bigg|2\bigg)=2^{2m}~,\quad\text{整数 }m\geqslant0~.\tag{5.98}
但是请看下参数 “-2m ”。由于负整数是被禁止的，所以这个恒等式没有定义！
正如我们早先所允诺的那样，现在该是仔细审视这种极限情形的时候了，因为退化的超几何级数常可以通过从附近非退化的点趋向于它们来进行计算。这样做的时候必须谨慎从事，因为如果我们用不同的方式取极限，就有可能得到不同的结果。例如，这里有两个极限，事实证明它们是完全不同的极限，其中的一个上参数增加了 \varepsilon ：
\begin{aligned}
\lim_{\varepsilon\to0}F\bigg(\begin{matrix}-1+\varepsilon,-3\\-2+\varepsilon\end{matrix}\Bigg|1\bigg)&=\lim_{\varepsilon\to0}\bigg(1+\frac{(-1+\varepsilon)(-3)}{(-2+\varepsilon)1!}+\frac{(-1+\varepsilon)(\varepsilon)(-3)(-2)}{(-2+\varepsilon)(-1+\varepsilon)2!}\\
&\hphantom{=~\lim_{\varepsilon\to0}\bigg(1}+\frac{(-1+\varepsilon)(\varepsilon)(1+\varepsilon)(-3)(-2)(-1)}{(-2+\varepsilon)(-1+\varepsilon)(\varepsilon)3!}\bigg)\\
&=1-\frac32+0+\frac12=0~;\\
\lim_{\varepsilon\to0}F\bigg(\begin{matrix}-1,-3\\-2+\varepsilon\end{matrix}\Bigg|1\bigg)&=\lim_{\varepsilon\to0}\bigg(1+\frac{(-1)(-3)}{(-2+\varepsilon)1!}+0+0\bigg)\\
&=1-\frac32+0+0=-\frac12~.
\end{aligned}
类似地，我们已经定义了 \dbinom{-1}{-1}=0=\lim_{\varepsilon\to0}\dbinom{-1+\varepsilon}{-1} ，这与 \lim_{\varepsilon\to0}\dbinom{-1+\varepsilon}{-1+\varepsilon}=1 不同。将 (5.98) 作为极限处理的一个适当方法是：用上参数 -m 来使得级数 \sum_{k\geqslant0}\dbinom{2m-k}{m-k}2^k 的所有满足 k>m 的项都为零，这就意味着我们想要建立如下更精确的命题：
\binom{2m}m\lim_{\varepsilon\to\infty}F\bigg(\begin{matrix}1,-m\\-2m+\varepsilon\end{matrix}\Bigg|2\bigg)=2^{2m}~,\quad\text{整数 }m\geqslant0~.\tag{5.99}
这个极限的每一项都有良好的定义，因为分母的因子 (-2m)^{\overline k} 直到 k>2m 时才变为零。这样一来，这个极限就恰好给出开始时的和式 (5.20) 的值。
5.6 超几何变换 HYPERGEOMETRIC TRANSFORMATIONS
到现在为止应该清楚的是，已知的所有超几何封闭形式的数据库是计算二项式系数和式的有用工具。我们可以直接将任何给定的和式转变成它的标准的超几何形式，然后在这个表中查询它。如果表中有，那我们就得到了答案。如若不然，如果事实表明这个和式可以表示成封闭形式，我们就将它添入数据库中。我们或许还可以在表里包含这样的条目：“这个和式还没有一般意义上的简单封闭形式．” 例如，和式 \sum_{k\leqslant m}\dbinom nk 对应于超几何形式
\binom nmF\bigg(\begin{matrix}1,-m\\n-m+1\end{matrix}\Bigg|{-1}\bigg)~,\quad\text{整数 }n\geqslant m\geqslant0~;\tag{5.100}
它仅当 m 接近于 0 、\dfrac12n 或者 n 时才有简单的封闭形式。
但是对于这个论题还有更多的内容，因为超几何函数也服从它们自己的恒等式。这就意味着超几何函数的每一个封闭形式都导出额外增加的封闭形式，且导出该数据库中额外增加的条目。例如，习题 25 和习题 26 中的恒等式告诉我们，怎样将一个超几何级数变换成另外两个（或一个）具有类似但不同的参数的超几何级数。这些级数还可以依次再进行变换。
超几何资料库真应该是个 “知识库”。
1797 年，J.F. 普法夫发现了一个惊人的反射定律 （reflection law）
\frac1{(1-z)^a}F\bigg(\begin{matrix}a,b\\c\end{matrix}\Bigg|\frac{-z}{1-z}\bigg)=F\bigg(\begin{matrix}a,c-b\\c\end{matrix}\Bigg|z\bigg)~,\tag{5.101}
它是另一种类型的变换。如果在展开左边的时候用无穷级数 (-z)^k\Bigg(1+\dbinom{k+a}1z+\dbinom{k+a+1}2z^2+\cdots\Bigg) 代替量 (-z)^k/(1-z)^{k+a} ，这就是关于幂级数的一个形式恒等式（见习题 50）。当 z\ne1 时，可以利用这个法则从我们已经知道的恒等式推导出新的公式。
例如，如果选择参数使得库默尔公式和反射定律这两个恒等式都适用，那么库默尔公式 (5.94) 就可以与反射定律 (5.101) 结合起来：
\begin{aligned}2^{-a}F\bigg(\begin{matrix}a,1-a\\1+b-a\end{matrix}\Bigg|\frac12\bigg)&=F\bigg(\begin{matrix}a,b\\1+b-a\end{matrix}\Bigg|{-1}\bigg)\\&=\frac{(b/2)!}{b!}(b-a)^{\underline{b/2}}\end{aligned}~.\tag{5.102}
现在令 a=-n 并从这个等式回到二项式系数的一个新的恒等式，或许某一天我们会需要它：
\begin{aligned}\sum_{k\geqslant0}\frac{(-n)^{\overline k}(1+n)^{\overline k}}{(1+b+n)^{\overline k}}\frac{2^{-k}}{k!}&=\sum_k\binom nk\bigg(\frac{-1}2\bigg)^k\binom{n+k}k\bigg/\binom{n+b+k}k\\&=2^{-n}\frac{(b/2)!(b+n)!}{b!(b/2+n)!}~,\quad\text{整数 }n\geqslant0~.\end{aligned}\tag{5.103}
例如，当 n=3 时这个恒等式就是
1-3\frac4{2(4+b)}+3\frac{4\times5}{4(4+b)(5+b)}-\frac{4\times5\times6}{8(4+b)(5+b)(6+b)}=\frac{(b+3)(b+2)(b+1)}{(b+6)(b+4)(b+2)}~.
几乎令人难以置信，但它确实对所有的 b 都为真。（除了分母中某个因子变为零的情形之外。）
这很有趣，我们再试一次。或许我们会发现一个真正使朋友们大吃一惊的公式。如果将普法夫的反射定律应用到陌生的形式 (5.99) 中（其中取 z=2 ），这个定律会告诉我们什么呢？在这种情形下，我们令 a=-m ，b=1 以及 c=-2m+\varepsilon ，就得到
\begin{aligned}(-1)^m\lim_{\varepsilon\to0}F\bigg(\begin{matrix}-m,1\\-2m+\varepsilon\end{matrix}\Bigg|2\bigg)&=\lim_{\varepsilon\to0}F\bigg(\begin{matrix}-m,-2m-m+\varepsilon\\-2m+\varepsilon\end{matrix}\Bigg|2\bigg)\\&=\lim_{\varepsilon\to0}\sum_{k\geqslant0}\frac{(-m)^{\overline k}(-2m-1+\varepsilon)^{\overline k}}{(-2m+\varepsilon)^{\overline k}}\frac{2^k}{k!}\\&=\sum_{k\leqslant m}\binom mk\frac{(2m+1)^{\underline k}}{(2m)^{\underline k}}(-2)^k~,\end{aligned}
因为取极限的项中没有接近于零的。这就引导出另外一个不可思议的公式
（历史注记：如果你得到一个不同的结果，就看习题 51。）
\begin{align}\sum_{k\leqslant m}\binom mk\frac{2m+1}{2m+1-k}(-2)^k&=(-1)^m2^{2m}\bigg/\binom{2m}m\notag\\&=1\bigg/\binom{-1/2}m~,\quad\text{整数 }m\geqslant0~.\tag{5.104}\end{align}
例如，当 m=3 时，该和式就是
1-7+\frac{84}5-14=-\frac{16}5~,
而 \dbinom{-1/2}3 的确等于 -\dfrac5{16} 。
在讲述二项式系数恒等式并将它们转变成超几何形式时，我们忽略了 (5.19) ，因为它是两个和式之间的一个关系，而不是一个封闭形式。但是现在，我们可以将 (5.19) 视为超几何级数之间的一个恒等式了。如果我们将它关于 y 微分 n 次，然后用 m-n-k 代替 k ，就得到
\begin{aligned}&\sum_{k\geqslant0}\binom{m+r}{m-n-k}\binom{n+k}nx^{m-n-k}y^k\\&\qquad=\sum_{k\geqslant0}\binom{-r}{m-n-k}\binom{n+k}n(-x)^{m-n-k}(x+y)^k~.\end{aligned}
这就得到如下的超几何变换：
F\bigg(\begin{matrix}a,-n\\c\end{matrix}\Bigg|z\bigg)=\frac{(a-c)^{\underline n}}{(-c)^{\underline n}}F\bigg(\begin{matrix}a,-n\\1-n+a-c\end{matrix}\Bigg|1-z\bigg)~,\quad\text{整数 }n\geqslant0~.\tag{5.105}
注意，当 z=1 时它转化为范德蒙德卷积 (5.93) 。
如果这个例子有指导意义的话，微分法看起来是有用的。我们还发现微分法在第 2 章里对 x+2x^2+\cdots+nx^n 求和时是有帮助的。我们来看看当一个一般的超几何级数关于 z 求导时会发生什么：
\begin{align}\frac {\mathrm d}{\mathrm dz}F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)&=\sum_{k\geqslant1}\frac{a_1^{\overline k}\cdots a_m^{\overline k}z^{k-1}}{b_1^{\overline k}\cdots b_n^{\overline k}(k-1)!}\notag\\&=\sum_{k+1\geqslant1}\frac{a_1^{\overline{k+1}}\cdots a_m^{\overline{k+1}}z^k}{b_1^{\overline{k+1}}\cdots b_n^{\overline{k+1}}k!}\notag\\&=\sum_{k\geqslant0}\frac{a_1(a_1+1)^{\overline k}\cdots a_m(a_m+1)^{\overline k}z^k}{b_1(b_1+1)^{\overline k}\cdots b_n(b_n+1)^{\overline k}k!}\notag\\&=\frac{a_1\cdots a_m}{b_1\cdots b_n}F\bigg(\begin{matrix}a_1+1,\cdots\,\!,a_m+1\\b_1+1,\cdots\,\!,b_n+1\end{matrix}\Bigg|z\bigg)~.\tag{5.106}\end{align}
参数移了出来且原参数值增加。
也有可能利用微分法只调整其中的一个参数，而其余的参数保持不变。为此我们利用算子
\vartheta=z\frac{\mathrm d}{\mathrm dz}~,
它先对函数求导再乘以 z 。这个算子给出
\vartheta F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)=z\sum_{k\geqslant1}\frac{a_1^{\overline k}\cdots a_m^{\overline k}z^{k-1}}{b_1^{\overline k}\cdots b_n^{\overline k}(k-1)!}=\sum_{k\geqslant0}\frac{ka_1^{\overline k}\cdots a_m^{\overline k}z^k}{b_1^{\overline k}\cdots b_n^{\overline k}k!}~,
这个公式本身不太有用。但是如果我们用它的一个上参数（比方说 a_1 ）乘以 F ，并将它加到 \vartheta F 上，就得到
\begin{aligned}(\vartheta+a_1)F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)&=\sum_{k\geqslant0}\frac{(k+a_1)a_1^{\overline k}\cdots a_m^{\overline k}z^k}{b_1^{\overline k}\cdots b_n^{\overline k}k!}\\&=\sum_{k\geqslant0}\frac{a_1(a_1+1)^{\overline k}a_2^{\overline k}\cdots a_m^{\overline k}z^k}{b_1^{\overline k}\cdots b_n^{\overline k}k!}\\&=a_1F\bigg(\begin{matrix}a_1+1,a_2,\cdots\,\!,a_m\\b_1,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)~.\end{aligned}
只有一个参数改变了。
一个类似的技巧也适用于下参数，但是在这种情形下是把参数往下减少而不是往上增加：
\begin{aligned}(\vartheta+b_1-1)F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)&=\sum_{k\geqslant0}\frac{(k+b_1-1)a_1^{\overline k}\cdots a_m^{\overline k}z^k}{b_1^{\overline k}\cdots b_n^{\overline k}k!}\\&=\sum_{k\geqslant0}\frac{(b_1-1)a_1^{\overline k}\cdots a_m^{\overline k}z^k}{(b_1-1)^{\overline k}b_2^{\overline k}\cdots b_n^{\overline k}k!}\\&=(b_1-1)F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1-1,b_2,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)~.\end{aligned}
现在我们可以把所有的这些运算都组合起来，并用两种不同的方式表达同一个量，由此得到数学的 “双关式”。也就是说，我们有
有没有听说过关于几个兄弟的故事：他们把自己的养牛场取名为 Focus，因为儿子们正是在这里饲养牛的？
正文中用了数学的 “双关式”，而这个旁注则用了 “双关语”，它们都来自同一个英文单词 pun。旁注中的 Focus=where the sun's rays meet（光线汇集之处），它的谐音正是 “where the sons raise meat”。
(\vartheta+a_1)\cdots(\vartheta+a_m)F=a_1\cdots a_mF\bigg(\begin{matrix}a_1+1,\cdots\,\!,a_m+1\\b_1\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)~,
以及
(\vartheta+b_1-1)\cdots(\vartheta+b_n-1)F=(b_1-1)\cdots(b_n-1)F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1-1,\cdots\,\!,b_n-1\end{matrix}\Bigg|z\bigg)~,
其中 F=F(a_1,\cdots\,\!,a_m;b_1,\cdots\,\!,b_n;z) 。而 (5.106) 告诉我们，上面一行是下面一行的导数。于是，一般的超几何函数满足微分方程
\mathrm D(\vartheta+b_1-1)\cdots(\vartheta+b_n-1)F=(\vartheta+a_1)\cdots(\vartheta+a_m)F~,\tag{5.107}
其中 \mathrm D 是算子 \dfrac{\mathrm d}{\mathrm dz} 。
这里迫切需要一个例子。我们来寻求一个微分方程，它满足于一个标准的有两个上参数和一个下参数的超几何级数 F(z)=F(a,b;c;z) 。根据 (5.107) ，我们有
\mathrm D(\vartheta+c-1)F=(\vartheta+a)(\vartheta+b)F~.
按照通常的记号，它的含义是什么？好的，(\vartheta+c-1)F 就是 zF'(z)+(c-1)F(z) ，而它的导数给出左边
F'(z)+zF''(z)+(c-1)F'(z)~.
而在右边我们有
\begin{aligned}(\vartheta+a)(zF'(z)+bF(z))&=z\frac{\mathrm d}{\mathrm dz}(zF'(z)+bF(z))+a(zF'(z)+bF(z))\\&=zF'(z)+z^2F''(z)+bzF'(z)+azF'(z)+abF(z)~.\end{aligned}
使两边相等就得到
z(1-z)F''(z)+(c-z(a+b+1))F'(z)-abF(z)=0~,\tag{5.108}
这个方程等价于分解的形式 (5.107) 。
反过来，我们可以从微分方程回到幂级数。假设 F(z)=\sum_{k\geqslant0}t_kz^k 是一个满足 (5.107) 的幂级数。直接计算，我们必定有
\frac{t_{k+1}}{t_k}=\frac{(k+a_1)\cdots(k+a_m)}{(k+b_1)\cdots(k+b_n)(k+1)}~;
从而 F(z) 必定就是 t_0F(a_1,\cdots\,\!,a_m;b_1,\cdots\,\!,b_n;z) 。我们已经证明了超几何级数 (5.76) 是仅有满足微分方程 (5.107) 且常数项为 1 的形式幂级数。
如果超几何学解决了世界上所有的微分方程，那固然很好，但是它们做不到。(5.107) 的右边总是展开成由形如 \alpha_kz^kF^{(k)}(z) 的项组成的和式，其中 F^{(k)}(z) 是 k 阶导数 \mathrm D^kF(z) ；左边总是展开成由形如 \beta_kz^{k-1}F^{(k)}(z) 的项组成的和式（k>0 ）。所以微分方程 (5.107) 总是取特殊的形式
z^{n-1}(\beta_n-z\alpha_n)F^{(n)}(z)+\cdots+(\beta_1-z\alpha_1)F'(z)-\alpha_0F(z)=0~.
方程 (5.108) 给出了 n=2 时的例证。反之，在习题 6.13 中将要证明，任何这种形式的微分方程都可以分解成 \vartheta 算子这样的项，给出像 (5.107) 这样的方程。所以这些微分方程的解就是以有理数作为项的比值的幂级数。
用 z 乘 (5.107) 的两边就去掉了算子 \mathrm D ，并给出一个有启发性的全 \vartheta 形式
函数 F(z)=(1-z)^r 满足 \vartheta F=z(\vartheta-r)F 。这给出了二项式定理的另一个证明。
\vartheta(\vartheta+b_1-1)\cdots(\vartheta+b_n-1)F=z(\vartheta+a_1)\cdots(\vartheta+a_m)F~.\tag{5.109}
左边的第一个因子 \vartheta=(\vartheta+1-1) 对应于项的比值 (5.81) 中的 (k+1) ，它与一般的超几何级数中第 k 项的分母中的 k! 相对应。其他的因子 (\vartheta+b_j-1) 与分母中的因子 k+b_j 相对应，(k+b_j) 对应于 (5.76) 中的 b_j^{\overline k} 。在右边，z 与 z^k 相对应，而 (\vartheta+a_j) 则与 a_j^{\overline k} 相对应。
这个微分理论的一个用途是发现并证明新的变换。例如，我们可以很容易地验证：两个超几何级数
F\hspace{-0.2em}\left(\begin{matrix}2a,2b\\a+b+\dfrac12\end{matrix}\middle|z\right)\text{ 和 }F\hspace{-0.2em}\left(\begin{matrix}a,b\\a+b+\dfrac12\end{matrix}\middle|4z(1-z)\right)
都满足微分方程
z(1-z)F''(z)+\bigg(a+b+\frac12\bigg)(1-2z)F'(z)-4abF(z)=0~;
从而高斯恒等式 （Gauss's identity）
F\hspace{-0.2em}\left(\begin{matrix}2a,2b\\a+b+\dfrac12\end{matrix}\middle|z\right)=F\hspace{-0.2em}\left(\begin{matrix}a,b\\a+b+\dfrac12\end{matrix}\middle|4z(1-z)\right)\tag{5.110}
必定为真。特别地，
（小心：当 |z|>1/2 时我们不能安全无忧地使用 (5.110) ，除非它的两边都是多项式，见习题 53。）
F\hspace{-0.2em}\left(\begin{matrix}2a,2b\\a+b+\dfrac12\end{matrix}\middle|\frac12\right)=F\hspace{-0.2em}\left(\begin{matrix}a,b\\a+b+\dfrac12\end{matrix}\middle|1\right)~,\tag{5.111}
只要两边的无限和式收敛。而实际上两边的和式的确总是收敛的，除了在 a+b+\dfrac12 是非正整数这种退化的情形。
超几何级数的每一个新的恒等式都有关于二项式系数的推论，这个恒等式也不例外。我们来考虑和式
\sum_{k\leqslant m}\binom{m-k}n\binom{m+n+1}k\bigg(\frac{-1}2\bigg)^k~,\quad\text{整数 }m\geqslant n\geqslant0~.
满足 0\leqslant k\leqslant m-n 的项是非零的，如前一样稍加小心取极限就能将这个和式表示成超几何形式
\lim_{\varepsilon\to0}\binom mnF\bigg(\begin{matrix}n-m,-n-m-1+\alpha\varepsilon\\-m+\varepsilon\end{matrix}\Bigg|\frac12\bigg)~.
$$
\begin{align}&\sum_{k\leqslant m}\binom{m-k}n\binom{m+n+1}k\bigg(\frac{-1}2\bigg)^k\notag\\&\hphantom{\sum\Bigg(}=\binom{(m+n)/2}n2^{n-m}[m+n\text{ 是偶数}]~,\quad\text{整数 }m\geqslant n\geqslant0~,\tag{5.112}\end{align}
$$
正如习题 54 中所指出的那样。例如，当 $m=5$ 以及 $n=2$ 时，我们得到 $\dbinom52\dbinom80-\dbinom42\dbinom81/2+\dbinom32\dbinom82/4+\dbinom22\dbinom83/8=10-24+21-7=0$；而当 $m=4$ 以及 $n=2$ 时，两边都得出 $\dfrac34$。
我们还能发现一些情形，在其中，当 $z=-1$ 时 $(5.110)$ 给出二项和式，这些是真正令人不可思议的。如果我们令 $a=\dfrac16-\dfrac n3$ 以及 $b=-n$，就得到异化的公式
$$
F\hspace{-0.2em}\left(\begin{matrix}\dfrac13-\dfrac23n,-2n\\\dfrac23-\dfrac43n\end{matrix}\middle|{-1}\right)=F\hspace{-0.2em}\left(\begin{matrix}\dfrac16-\dfrac13n,-n\\\dfrac23-\dfrac43n\end{matrix}\middle|{-8}\right).
$$
这些超几何级数在 $n\not\equiv2\pmod3$ 时是非退化的多项式，且其中的参数选取得很是巧妙，使得其左边可以用 $(5.94)$ 来计算。这样一来，我们就引导出一个真正令人难以置信的结果
$$
\begin{align}&\sum_k\binom nk\hspace{-0.15em}\begin{pmatrix}\dfrac13n-\dfrac16\\k\end{pmatrix}8^k\Bigg/\begin{pmatrix}\dfrac43n-\dfrac23\\k\end{pmatrix}\notag\\&=\binom{2n}n\Bigg/\begin{pmatrix}\dfrac43n-\dfrac23\\n\end{pmatrix}~,\quad\text{整数 }n\geqslant0~,\quad n\not\equiv2\pmod3~.\tag{5.113}\end{align}
$$
这是我们在二项式系数中看到过的最令人瞠目结舌的恒等式，甚至连这个恒等式的小数值的情形也不容易通过手工计算来检验。（事实表明，当 $n=3$ 时两边都得出 $\dfrac{81}7$。）这个恒等式当然完全没有用，它肯定不会在实际问题中出现。
> $(5.113)$ 仅有的用途就是展示存在难以置信的无用恒等式。
以上就是我们对超几何学的 “炒作”。我们已经看到，超几何级数对于理解二项式系数和式提供了一个高水平的方法。更多的信息可以在 Bailey 所写的经典著作以及其后由 Gasper 和 Rahman 合著的书中找到。
## 5.7 部分超几何和式 PARTIAL HYPERGEOMETRIC SUMS
在这一章里，我们计算过的大多数和式都考虑到所有的指标 $k\geqslant0$，但有时我们也能在更一般的范围 $a\leqslant k<b$ 内找到有效的封闭形式。例如，由 $(5.16)$ 我们知道
$$
\sum_{k<m}\binom nk(-1)^k=(-1)^{m-1}\binom{n-1}{m-1}~,\quad m\text{ 是整数.}\tag{5.114}
$$
第 2 章里的理论给了我们一个好方法来理解这样的公式：如果 $f(k)=\Delta g(k)=g(k+1)-g(k)$，那么我们就记 $\sum f(k)\delta k=g(k)+C$，且
$$
\sum\nolimits_a^bf(k)\delta k=g(k)\big|_a^b=g(b)-g(a)~.
$$
此外，当 $a$ 和 $b$ 是满足 $a\leqslant b$ 的整数时，我们有
$$
\sum\nolimits_a^bf(k)\delta k=\sum_{a\leqslant k<b}f(k)=g(b)-g(a)~.
$$
这样一来，恒等式 $(5.114)$ 就对应于不定求和公式
$$
\sum\binom nk(-1)^k\delta k=(-1)^{k-1}\binom{n-1}{k-1}+C~,
$$
而且也对应于差分公式
$$
\Delta\Bigg((-1)^k\binom nk\Bigg)=(-1)^{k+1}\binom{n+1}{k+1}~.
$$
从一个函数 $g(k)$ 开始可以很容易计算 $\Delta g(k)=f(k)$，这是一个和等于 $g(k)+C$ 的函数。但是从 $f(k)$ 出发并计算出它的不定和式 $\sum f(k)\delta k=g(k)+C$ 就要困难得多，这个函数 $g$ 可能没有简单的形式。例如，$\sum\dbinom nk\delta k$ 显然没有简单的形式，否则我们就能计算 $\sum_{k\leqslant n/3}\dbinom nk$ 这样的和式了，而我们对此一点线索也没有。不过也可能 $\sum\dbinom nk\delta k$ 有一个简单的形式，而我们正好还没有想到它。我们凭什么对此确信无疑呢？
1977 年，R. W. Gosper 发现了一个优美的方法，只要 $f$ 和 $g$ 属于成为超几何项的一般函数类，就能用此法求出不定和式 $\sum f(k)\delta k=g(k)+C$。我们记
$$
F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)_k=\frac{a_1^{\overline k}\cdots a_m^{\overline k}}{b_1^{\overline k}\cdots b_n^{\overline k}}\frac{z^k}{k!}\tag{5.115}
$$
为超几何函数 $F(a_1,\cdots\,\!,a_m;b_1,\cdots\,\!,b_n;z)$ 的第 $k$ 项。我们将把 $F(a_1,\cdots\,\!,a_m;b_1,\cdots\,\!,b_n;z)$ 看成是 $k$ 而不是 $z$ 的一个函数。在许多情形下都表明，对给定的 $a_1,\cdots\,\!,a_m,b_1,\cdots\,\!,b_n$ 以及 $z$，存在参数 $c$，$A_1,\cdots\,\!,A_M,B_1,\cdots\,\!,B_N$ 以及 $Z$，使得
$$
\sum F\bigg(\begin{matrix}a_1,\cdots\,\!,a_m\\b_1,\cdots\,\!,b_n\end{matrix}\Bigg|z\bigg)\delta k=cF\bigg(\begin{matrix}A_1,\cdots\,\!,A_M\\B_1,\cdots\,\!,B_N\end{matrix}\Bigg|Z\bigg)_k+C~.\tag{5.116}
$$
如果这样的常数 $c,A_1,\cdots\,\!,A_M,B_1,\cdots\,\!,B_N,Z$ 存在，我们将把函数 $F(a_1,\cdots\,\!,a_m;b_1,\cdots\,\!,b_n;z)_k$ 称为是**可用超几何项求和的**（summable in hypergeometric terms），Gosper 算法要么求出未知的常数，要么证明不存在这样的常数。
一般来说，如果 $t(k+1)/t(k)$ 是 $k$ 的一个不恒为零的有理函数，我们就称 $t(k)$ 是一个**超几何项**（hypergeometric term）。这本质上就意味着，$t(k)$ 是像 $(5.115)$ 的一个项的常数倍。（然而会出现与零有关的技术性问题，因为我们希望当 $k$ 取负值以及当 $(5.115)$ 中诸个 $b$ 中有一个或者多个取零或者负整数值时，$t(k)$ 都是有意义的。严格地说，通过用一个非零常数与一个零的幂的积来乘以 $(5.115)$，我们就得到最一般的超几何项，然后将分子的零与分母的零相抵消。习题 12 中的例子有助于阐明这个一般法则。）
假设在 $t(k)$ 是一个超几何项时我们想要求 $\sum t(k)\delta k$。Gosper 算法分两步走，每一步都相当直截了当。第 1 步是将项的比值表示成一个特殊的形式
$$
\frac{t(k+1)}{t(k)}=\frac{p(k+1)}{p(k)}\frac{q(k)}{r(k+1)}~,\tag{5.117}
$$
其中 $p$、$q$ 和 $r$ 是满足下述条件
$$
\begin{align}(k+\alpha)\setminus q(k)\text{ 以及 }(k+\beta)\setminus r(k)\notag\\\implies\alpha-\beta\text{ 不是正整数}\qquad\tag{5.118}\end{align}
$$
> （多项式的整除与整数的整除类似。例如，$(k+\alpha)\backslash q(k)$ 就意味着商 $q(k)/(k+\alpha)$ 是一个多项式。容易看出，$(k+\alpha)$ 是一个多项式。容易看出，$(k+\alpha)\backslash q(k)$ 当且仅当 $q(-\alpha)=0$。）
的多项式。这个条件容易达到：我们暂时从 $p(k)=1$ 出发，并令 $q(k)$ 和 $r(k+1)$ 是将它们分解成线性因子后，项的比值的分子和分母。例如，如果 $t(k)$ 有 $(5.115)$ 的形状，我们就从因子分解 $q(k)=(k+a_1)\cdots(k+a_m)z$ 以及 $r(k)=(k+b_1-1)\cdots(k+b_n-1)k$ 开始。然后，我们来检查是否违反了 $(5.118)$。如果 $q$ 和 $r$ 有因子 $(k+\alpha)$ 以及 $(k+\beta)$，其中 $\alpha-\beta=N>0$，我们就将它们从 $q$ 和 $r$ 中除掉，并用
$$
p(k)(k+\alpha-1)^{\underline{N-1}}=p(k)(k+\alpha-1)(k+\alpha-2)\cdots(k+\beta+1)\tag{5.119}
$$
代替 $p(k)$。新的 $p$、$q$ 和 $r$ 仍然满足 $(5.117)$。我们可以重复这个过程，直到 $(5.118)$ 成立。一会儿我们将会看到为什么 $(5.118)$ 是重要的。
Gosper 算法的第 2 步是完成这项任务——求一个超几何项 $T(k)$，使得只要可能就有
$$
t(k)=T(k+1)-T(k)~.\tag{5.120}
$$
但是怎样做到这一点却并不明显，我们需要先讨论某些理论，然后才能知道怎样做下去。在研究了许多特殊的情形之后，Gosper 注意到，明智的方法是将未知函数 $T(k)$ 写成形式
$$
T(k)=\frac{r(k)s(k)t(k)}{p(k)}~,\tag{5.121}
$$
其中 $s(k)$ 是必须用某种方法发现的一个神秘的函数。将 $(5.121)$ 代入 $(5.120)$ 并应用 $(5.117)$ 就给出
> （习题 55 对为什么我们要做这样一个魔术般的代换给出了一点线索。）
$$
\begin{aligned}t(k)&=\frac{r(k+1)s(k+1)t(k+1)}{p(k+1)}-\frac{r(k)s(k)t(k)}{p(k)}\\&=\frac{q(k)s(k+1)t(k)}{p(k)}-\frac{r(k)s(k)t(k)}{p(k)}~,\end{aligned}
$$
所以我们需要有
$$
p(k)=q(k)s(k+1)-r(k)s(k)~.\tag{5.122}
$$
如果能找到满足这个基本递归关系的 $s(k)$，我们就找到了 $\sum t(k)\delta k$；如果不能找到 $s(k)$，那就找不到 $T$。
我们假设 $T(k)$ 是一个超几何项，这意味着 $T(k+1)/T(k)$ 是 $k$ 的一个有理函数。这样一来，根据 $(5.121)$ 以及 $(5.120)$，$r(k)s(k)/p(k)=T(k)/\big(T(k+1)-T(k)\big)$ 是 $k$ 的一个有理函数，而 $s(k)$ 本身必定是多项式的商
$$
s(k)=f(k)/g(k)~.
$$
但事实上我们可以证明，$s(k)$ 本身就是一个多项式。因为如果 $g(k)$ 不是常数，且 $f(k)$ 与 $g(k)$ 没有公因子，设 $N$ 是对于某个复数 $\beta$ 使得 $(k+\beta)$ 和 $(k+\beta+N-1)$ 两者都作为 $g(k)$ 的因子出现的最大整数。由于 $N=1$ 总满足这个条件，故而 $N$ 的值是正的。方程 $(5.122)$ 可以改写成
$$
p(k)g(k+1)g(k)=q(k)f(k+1)g(k)-r(k)g(k+1)f(k)~,
$$
又如果置 $k=-\beta$ 以及 $k=-\beta-N$，就得到
$$
r(-\beta)g(1-\beta)f(-\beta)=0=q(-\beta-N)f(1-\beta-N)g(-\beta-N)~.
$$
现在 $f(-\beta)\ne0$ 且 $f(1-\beta-N)\ne0$，因为 $f$ 和 $g$ 没有共同的根。同样有 $g(1-\beta)\ne0$ 以及 $g(-\beta-N)\ne0$，如若不然，$g(k)$ 就会包含因子 $(k+\beta-1)$ 或者 $(k+\beta-N)$，而这与 $N$ 的最大值性质相矛盾。于是，
$$
r(-\beta)=q(-\beta-N)=0~.
$$
但是这与条件 $(5.118)$ 矛盾。从而 $s(k)$ 必定是一个多项式。
> 我明白了：Gosper 提出条件 $(5.118)$ 是为了使这个证明能够通过。
当 $p(k)$、$q(k)$ 以及 $r(k)$ 是给定的多项式时，我们的任务就归结为求一个满足 $(5.122)$ 的多项式 $s(k)$，或者证明不存在这样的多项式。当 $s(k)$ 有特定的次数 $d$ 时，这很容易，因为对未知的系数 $(\alpha_d,\cdots\,\!,\alpha_0)$ 我们可以写成
$$
s(k)=\alpha_dk^d+\alpha_{d-1}k^{d-1}+\cdots+\alpha_0~,\quad\alpha_d\ne0\tag{5.123}
$$
并将这个表达式代入基本递归式 $(5.122)$ 中。多项式 $s(k)$ 满足这个递归式，当且仅当诸 $\alpha$ 都满足令 $(5.122)$ 中 $k$ 的每一个幂的系数相等时所得到的线性方程。
但是我们怎么才能确定 $s$ 的次数呢？事实表明，存在至多两种可能性。我们可以将 $(5.122)$ 改写成形式
$$
2p(k)=Q(k)\big(s(k+1)+s(k)\big)+R(k)\big(s(k+1)-s(k)\big)~,\tag{5.124}
$$
其中 $Q(k)=q(k)-r(k)$ 且 $R(k)=q(k)+r(k)$。
如果 $s(k)$ 的次数为 $d$，那么和式 $s(k+1)+s(k)=2\alpha_dk^d+\cdots$ 的次数也为 $d$，而差 $s(k+1)-s(k)=\Delta s(k)=d\alpha_dk^{d-1}+\cdots$ 的次数为 $d-1$。（可以设零多项式的次数为 $-1$。）我们用 $\operatorname{deg}(P)$ 表示多项式 $P$ 的次数。如果 $\operatorname{deg}(Q)\geqslant\operatorname{deg}(R)$，那么 $(5.124)$ 右边的次数就是 $\operatorname{deg}(Q)+d$，所以必定有 $d=\operatorname{deg}(p)-\operatorname{deg}(Q)$。另一方面，如果 $\operatorname{deg}(Q)<\operatorname{deg}(R)=d'$，我们就能记 $Q(k)=\lambda'k^{d'-1}+\cdots$ 以及 $R(k)=\lambda k^{d'}+\cdots$，其中 $\lambda=0$，$(5.124)$ 的右边就有形式
$$
(2\lambda'\alpha_d+\lambda d\alpha_d)k^{d+d'-1}+\cdots~.
$$
因此有两种可能性：$2\lambda'+\lambda d\ne0$，且 $d=\operatorname{deg}(p)-\operatorname{deg}(R)+1$；$2\lambda'+\lambda d=0$，且 $d>\operatorname{deg}(p)-\operatorname{deg}(R)+1$。仅当 $-2\lambda'/\lambda$ 是一个大于 $\operatorname{deg}(p)-\operatorname{deg}(R)+1$ 的整数 $d$ 时，才需要对第二种情形进行检查。
好的，现在我们有足够的事实来执行 Gosper 的两步算法的第 2 步：只要 $(5.122)$ 有多项式解，那么通过尝试 $d$ 的至多两个值，我们就能发现 $s(k)$。如果 $s(k)$ 存在，我们就能将它代入 $(5.121)$，这样就得到了 $T$。如若不然，我们就证明了 $t(k)$ 不可用超几何项求和。
现在讨论一个例子：尝试计算部分和式 $(5.114)$。Gosper 的方法应该能对任何固定的 $n$ 推导出
$$
\sum\binom nk(-1)^k\delta k
$$
的值，所以我们寻求
$$
t(k)=\binom nk(-1)^k=\frac{n!(-1)^k}{k!(n-k)!}
$$
的和式。第 1 步是将项的比值表示成所要求的形式 $(5.117)$，我们有
$$
\frac{t(k+1)}{t(k)}=\frac{k-n}{k+1}=\frac{p(k+1)q(k)}{p(k)r(k+1)}~,
$$
所以我们直接取 $p(k)=1$，$q(k)=k-n$ 和 $r(k)=k$。$p$、$q$ 和 $r$ 的这种选取满足 $(5.118)$，除非 $n$ 是负整数，我们假设并非如此。
> 为什么不是 $r(k)=k+1$？哦，我看出来了。
现在我们来做第 2 步。根据 $(5.124)$，我们应该考虑多项式 $Q(k)=-n$ 和 $R(k)=2k-n$。由于 $R$ 的次数比 $Q$ 大，我们需要考虑两种情形：要么 $d=\operatorname{deg}(p)-\operatorname{deg}(R)+1$，它等于零；要么 $d=-2\lambda'/\lambda$，其中 $\lambda'=-n$ 且 $\lambda=2$，从而 $d=n$。第一种情形更好一些，因为它不要求 $n$ 是正整数，所以我们首先尝试它，仅当第一种情形不成立时我们才需要对 $d$ 尝试另一种可能性。假设 $d=0$，$s(k)$ 的值就是 $\alpha_0$，方程 $(5.122)$ 就转化为
$$
1=(k-n)\alpha_0-k\alpha_0~.
$$
于是我们选取 $\alpha_0=-1/n$。它满足这个方程并给出
$$
\begin{aligned}T(k)&=\frac{r(k)s(k)t(k)}{p(k)}\\&=k\times\bigg(\frac{-1}n\bigg)\times\binom nk(-1)^k\\&=\binom{n-1}{k-1}(-1)^{k-1}~,\quad n\ne0~,\end{aligned}
$$
这恰好就是我们希望确认的答案。
如果用同样的方法来求没有 $(-1)^k$ 的不定和式 $\sum\dbinom nk\delta k$，那么除了 $q(k)$ 将是 $n-k$ 之外，其他的都几乎相同。从而 $Q(k)=n-2k$ 比 $R(k)=n$ 有更大的次数，我们将得出结论：$d$ 取不可能的值 $\operatorname{deg}(p)-\operatorname{deg}(Q)=-1$。（多项式 $s(k)$ 不可能有负的次数，因为它不可能是零。）这样一来，函数 $\dbinom nk$ 就是不可能用超几何项求和的。
然而，我们一旦消除了不可能性，不论剩下的是什么——尽管不大可能——都必定是真实的（按照福尔摩斯）。当在第 1 步中定义 $p$、$q$ 和 $r$ 时，我们就决定了忽略 $n$ 取负整数值的可能性。如果它取负整数值呢？我们就取 $n=-N$，其中 $N$ 是正数。这样 $\sum\dbinom nk\delta k$ 的项的比值是
$$
\frac{t(k+1)}{t(k)}=\frac{-(k+N)}{k+1}=\frac{p(k+1)}{p(k)}\frac{q(k)}{r(k+1)}~,
$$
而且按照 $(5.119)$，它应该能用 $p(k)=(k+1)^{\overline{N-1}}$，$q(k)=-1$，$r(k)=1$ 来表示。Gosper 算法的第 2 步现在就告诉我们，要寻找一个次数为 $d=N-1$ 的多项式 $s(k)$，最终或许会有希望。例如，当 $N=2$ 时，递归式 $(5.122)$ 是说我们应该求解
$$
k+1=-\big((k+1)\alpha_1+\alpha_0\big)-\big(k\alpha_1+\alpha_0\big)~.
$$
令 $k$ 和 $1$ 的系数相等就给出
$$
1=-\alpha_1-\alpha_1~;\quad1=-\alpha_1-\alpha_0-\alpha_0~;
$$
从而 $s(k)=-\dfrac12k-\dfrac14$ 就是一个解，且
$$
T(k)=\frac{1\times\left(-\dfrac12k-\dfrac14\right)\times\dbinom{-2}k}{k+1}=(-1)^{k+1}\frac{2k+1}4~.
$$
这能是所希望的和式吗？是的，它经检查为真：
$$
(-1)^k\frac{2k+3}4-(-1)^{k-1}\frac{2k+1}4=(-1)^k(k+1)=\binom{-2}k~.
$$
> “你干得好极了，福尔摩斯！”“一点儿也不难，我亲爱的华生。”
附带指出，通过附加一个上限，我们可以把这个求和公式写成另外的形式：
$$
\begin{aligned}\sum_{k<m}\binom{-2}k&=(-1)^{k-1}\frac{2k+1}4\Bigg|_0^m\\&=\frac{(-1)^{m-1}}2\left(m+\frac{1-(-1)^m}2\right)\\&=(-1)^{m-1}\bigg\lceil\frac m2\bigg\rceil~,\quad\text{整数 }m\geqslant0~.\end{aligned}
$$
这个表示法掩盖了这样的事实：$\dbinom{-2}k$ 可以用超几何项求和，因为 $\lceil m/2\rceil$ 不是超几何项（见习题 12）。
如果对某个整数 $k$ 有 $p(k)=0$，则 $(5.121)$ 的分母中可能会出现问题。习题 97 介绍了在这种情况下我们能做什么。
注意，我们无需费神像这一章早先提及的确定的超几何和式资料库那样，将不定可求和的超几何项编纂成集，因为 Gosper 算法提供了一个在所有可求和的情形下都有效的快速且一致的方法。
Marko Petkovšek 发现了一个将 Gosper 算法推广到更为复杂的反演问题的好方法，其想法指出了，给定任何超几何项 $t(k)$ 以及多项式 $p_l(k),\cdots\,\!,p_1(k),p_0(k)$，怎样确定满足 $l$ 阶递归式
$$
t(k)=p_l(k)T(k+l)+\cdots+p_1(k)T(k+1)+p_0(k)T(k)\tag{5.125}
$$
的所有超几何项 $T(k)$。