一类恒等式的应用（范德蒙德卷积与超几何函数）

数学

---

翻到了2年前的一篇日报，一类恒等式的应用 -- foreverlastnig 的博客 ，里面指出了一个恒等式的应用：

$$\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}$$

这个恒等式就是大名鼎鼎的范德蒙德卷积，它最早是由中国人朱世杰于1303年发现的，法国人范德蒙德在18世纪重新发现了它。本文尝试从超几何函数的角度更进一步探究其在组合数的恒等变形中的重要意义。本文内容大部分来源于对《具体数学》第五章其中有关超几何函数的整理。

本文均只在实数范围内讨论，不考虑复数。

约定与前置知识

连续阶乘（广义阶乘函数）：

最开始，大家熟知的阶乘定义是：

$$n!=\prod_{k=1}^nk$$

欧拉将其拓展到了全体实数上（也适用于部分复述，超出了本文的范围）：

$$x!=\int_0^\infty t^x\mathtt{e}^{-t}\mathrm dt$$

同样满足阶乘的基本性质，即：

$$x!=x(x-1)!$$

欧拉还定义了一个相仿的函数，称为 $\Gamma$ 函数，满足：

$$\begin{aligned}\Gamma(x+1)&=x!\\\Gamma(x+1)&=x\Gamma(x)\\(-x)!\Gamma(x)&=\frac{\pi}{\sin(\pi x)}\end{aligned}$$

通过广义阶乘，我们可以定义广义上的二项式系数（取恰当极限）：

$$\binom{a}{b}=\lim_{r\to a}\lim _{s\to b}\frac{r!}{s!(r-s)!}$$

通过广义阶乘，定义下降幂和上升幂：

$$\begin{aligned}x^{\overline{n}}&=\Gamma(x+n)/\Gamma(x)\\x^{\underline{n}}&=x!/(x-n)!\end{aligned}$$

对于广义阶乘的乘法逆元，欧拉还证明了，

$$\frac{1}{x!}=\lim_{n\to\infty}\binom{n+x}{n}n^{-x}$$

由此可知，对于任何负整数 $x$，都有

$$\frac{1}{x!}=0$$

二项式系数：

基本的二项式恒等式应当被熟练使用，并了解多项式推理法，可以参考二项式系数 -- zhiyangfan 的小窝。下面列出一些常用的供读者快速索引，

$$\begin{aligned}\binom nk&=\binom n{n-k},n\in\mathbb N,k\in\mathbb Z\\(a+b)^r&=\sum_k\binom rka^kb^{r-k}\\\binom rk&=\frac rk\binom{r-1}{k-1},k\in\mathbb Z,k\neq0\\\binom rs&=\binom{r-1}k+\binom{r-1}{k-1},k\in\mathbb Z\\\binom rs&=(-1)^s\binom{s-1-r}s,s\in\mathbb Z\end{aligned}$$

生成函数：

基本的生成函数知识会被使用，可以参考铃悬的数学小讲堂——生成函数初步 -- 铃悬 的博客 。

超几何函数

化简求和式子的时候，我们通常可以将原式转化为下面形式

$$\sum_ {k\ge0}t_k$$

考虑这个求和相邻两项的比值 $\frac{t_{k+1}}{t_k}$，若为一个常数 $c$，则有

$$t_k=t_0c^k$$

运用等比数列的求和公式，

$$\begin{aligned}\sum_ {k\ge0}t_k&=\sum_ {k\ge0}t_0c^k\\&=t_0\sum_ {k\ge0}c^k\\&=\frac{t_0}{1-c}\end{aligned}$$

上面运用了几何级数的求和公式。然而大部分情况相邻两项的比值并非一个常数，举个例子，化简下面式子（$n>0$）

$$A=\sum_{k=0}^{n}\binom{n}{k}^2$$

简单变换后，得到

$$A=\sum_{k\ge0}\binom{n}{n-k}^2$$

即 $t_k=\binom{n}{n-k}^2$，其相邻两项的比值

$$\begin{aligned}\frac{t_{k+1}}{t_k}&=\frac{\binom{n}{n-k-1}^2}{\binom{n}{n-k}^2}\\&=(\frac{n!}{(n-k-1)!(k+1)!}\bigg/\frac{n!}{(n-k)!k!})^2\\&=\frac{(k-n)^2}{(k+1)^2}\end{aligned}$$

是关于 $k$ 的一个有理函数（即两个关于 $k$ 的多项式的商），由此考虑构造级数

$$S=\sum_{k\ge0}(\frac{(-n)^\overline{k}}{k!})^2$$

其相邻两项的比值也为 $\frac{(k-n)^2}{(k+1)^2}$。这个级数 $S$ 的 $k=0$ 的项的值为 $1$。因此

$$A=t_0S=S$$

通过后面将要讲述的方法，我们将会知道 $S=\binom{2n}{n}$。

为了更加通用和方便地通过 $\frac{t_ {k+1}}{t_k}$ 构造出形如 $S$ 的级数，我们考虑一般的超几何函数，它是关于 $x$ 的带有 $n+m$ 个参数的幂级数，定义为

$$\mathrm F\left(\begin{gathered}a_1,\cdots,a _m\\b_1,\cdots,b_n\end{gathered}\middle|x\right)=\sum _{k\ge0}\frac{a _1^\overline{k}\cdots a _m^\overline{k}x^k}{b _1^\overline{k}\cdots b _m^\overline{k}k!}$$

在行内，我们则使用记号 $\mathrm F(a_ 1,\cdots,a_ m;b _ 1,\cdots,b_ n;x)$，其第 $k$ 项为 $t_k=\frac{a _1^\overline{k}\cdots a _m^\overline{k}z^k}{b _1^\overline{k}\cdots b _m^\overline{k}k!}$，故其相邻两项的比值为

$$\begin{aligned}\frac{t_{k+1}}{t _k}&=\frac{a _1^\overline{k+1}\cdots a _m^\overline{k+1}}{b _1^\overline{k+1}\cdots b _m^\overline{k+1}}\frac{b _1^\overline{k}\cdots b _m^\overline{k}}{a _1^\overline{k}\cdots a _m^\overline{k}}\frac{k!x^{k+1}}{(k+1)!x^k}\\&=\frac{(k+a _1)\cdots(k+a _m)x}{(k+b _1)\cdots(k+b _n)(k+1)}\end{aligned}$$

这是 $k$ 的一个有理函数。因此，相邻两项的比值是有理函数的级数是超几何的。这意味着大多数组合恒等式都是超几何函数的特例而已。在上面的例子里，$S$ 其实是超几何函数的一个特殊例子，即

$$S=\mathrm F\left(\begin{gathered}-n,-n\\1\end{gathered}\middle|1\right)$$

高斯超几何函数与范德蒙德卷积

一个拥有两个上参数和一个下参数的超几何函数被称为高斯超几何函数（又称普通超几何函数），它的形式是

$$\mathrm F\left(\begin{gathered}a,b\\c\end{gathered}\middle|x\right)=\sum _{k\ge0}\frac{a^\overline{k}b^\overline{k}z^k}{c^\overline{k}k!}$$

高斯超几何函数取 $x=1$ 时与范德蒙德卷积有着密切的联系。考虑范德蒙德卷积，我们知道

$$\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}$$

另一方面，

$$\text{L.H.S.}=\sum_{k\ge0}\binom{r}{k}\binom{s}{n-k}$$

其第 $k$ 项为 $t_k=\binom{r}{k}\binom{s}{n-k}$，相邻两项的比值

$$\begin{aligned}\frac{t_{k+1}}{t_k}&=\frac{\binom{r}{k+1}\binom{s}{n-k-1}}{\binom{r}{k}\binom{s}{n-k}}\\&=\frac{r!s!k!(r-k)!(n-k)!(s-n+k)!}{r!s!(k+1)!(r-k-1)!(n-k-1)!(s-n+k+1)!}\\&=\frac{(r-k)(n-k)}{(k+1)(s-n+k+1)}\\&=\frac{(k-r)(k-n)}{(k+s-n+1)(k+1)}\end{aligned}$$

由此可知，

$$\begin{aligned}\text{L.H.S.}&=t_0\mathrm F\left(\begin{gathered}-r,-n\\s-n+1\end{gathered}\middle|1\right)\\&=\binom{s}{n}\mathrm F\left(\begin{gathered}-r,-n\\s-n+1\end{gathered}\middle|1\right)=\text{R.H.S}\end{aligned}$$

带入范德蒙德卷积右边，并将 $t_0$ 移项，得到

$$\begin{aligned}\mathrm F\left(\begin{gathered}-r,-n\\s-n+1\end{gathered}\middle|1\right)&=\frac{\binom{r+s}{n}}{\binom{s}{n}}\\\therefore \mathrm F\left(\begin{gathered}-r,-n\\s-n+1\end{gathered}\middle|1\right)&=\frac{(r+s)!(s-n)!}{(r+s-n)!s!}\end{aligned}$$

令 $a=-r,b=-n,c=s-n+1$，整理得到

$$\mathrm F\left(\begin{gathered}a,b\\c\end{gathered}\middle|1\right)=\frac{\Gamma(c-a-b)\Gamma(c)}{\Gamma(c-a)\Gamma(c-b)}$$

高斯证明了，这个等式成立需满足 $b\in\mathbb{Z},b\le0$ 或者 $c>a+b$ 时成立，否则等式左边的级数不收敛。这个等式从某种意义上说是范德蒙德卷积的另一种表现形式，这种形式能够更好的展现各种组合和式与范德蒙德卷积之间的关系。下面举几个应用，

例题1 （平行求和法）求下面式子的封闭形式，其中整数 $r,n\ge0$

$$\sum_{k=0}^n\binom{r+k}{k}$$

令原式为 $S$，翻转求和顺序

$$\begin{aligned}S&=\sum_{k=0}^n\binom{r+n-k}{n-k}\\&=\sum_{k\ge0}\binom{r+n-k}{n-k}\end{aligned}$$

级数的第 $k$ 项 $t_k=\binom{r+n-k}{n-k}$，其相邻两项的比值

$$\begin{aligned}\frac{t_{k+1}}{t _k}&=\binom{r+n-k-1}{n-k-1}\bigg/\binom{r+n-k}{n-k}\\&=\frac{k-n}{k-n-r}\\&=\frac{(k+1)(k-n)}{(k-n-r)(k+1)}\end{aligned}$$

由此可知，

$$\begin{aligned}S&=t_0\mathrm F\left(\begin{gathered}1,-n\\-n-r\end{gathered}\middle|1\right)\\&=\binom{r+n}{n}\mathrm F\left(\begin{gathered}1,-n\\-n-r\end{gathered}\middle|1\right)\end{aligned}$$

其中 $-n\le0$，应用范德蒙德卷积，

$$\begin{aligned}S&=\binom{r+n}{n}\frac{\Gamma(-n-r-(-n)-1)\Gamma(-n-r)}{\Gamma(-n-r-(-n))\Gamma(-n-r-1)}\\&=\binom{r+n}{n}\frac{\Gamma(-r-1)\Gamma(-r-n)}{\Gamma(-r)\Gamma(-r-n-1)}\\&=\binom{r+n}{n}\frac{r+n+1}{r+1}\\&=\binom{r+n+1}{n}\end{aligned}$$

例题2 求下面式子的封闭形式

$$\sum_{k\ge0}\binom{n+k}{2k}\binom{2k}{k}\frac{(-1)^k}{k+1}$$

令原式为 $S$，级数的第 $k$ 项 $t_k=\binom{n+k}{2k}\binom{2k}{k}\frac{(-1)^k}{k+1}$，其相邻两项的比值

$$\begin{aligned}\frac{t_{k+1}}{t _k}&=\frac{\binom{n+k+1}{2k+2}\binom{2k+2}{k+1}\frac{(-1)^{(k+1)}}{k+2}}{\binom{n+k}{2k}\binom{2k}{k}\frac{(-1)^k}{k+1}}\\&=\frac{(k+n+1)(k-n)}{(k+2)(k+1)}\end{aligned}$$

由此可知，

$$\begin{aligned}S&=t_0\mathrm F\left(\begin{gathered}n+1,-n\\2\end{gathered}\middle|1\right)\\&=\mathrm F\left(\begin{gathered}n+1,-n\\2\end{gathered}\middle|1\right)\end{aligned}$$

其中 $2>n+1+(-n)$，应用范德蒙德卷积，

$$\begin{aligned}S&=\frac{\Gamma(2-n-1+n)\Gamma(2)}{\Gamma(2-n-1)\Gamma(2+n)}\\&=\frac{1}{\Gamma(1-n)\Gamma(2+n)}\\&=\frac{\sin(\pi n)}{n(n+1)\pi}\end{aligned}$$

特别的，当 $n$ 为自然数时，$S=[n=0]$。

例题3 求下面式子的封闭形式，其中整数 $n\ge m\ge0$

$$\sum_{k=0}^m\binom mk\bigg/\binom nk$$

令原式为 $S$，取消求和上界以把 $S$ 写成级数的形式，

$$S=\sum_{k\ge0}\binom mk\bigg/\binom nk$$

级数的第 $k$ 项 $t_k=\binom mk\big/\binom nk$，其相邻两项的比值

$$\begin{aligned}\frac{t_ {k+1}}{t_k}&=\frac{\binom{m}{k+1} \binom{n}{k}}{\binom{m}{k} \binom{n}{k+1}}\\&=\frac{k-m}{k-n}\\&=\frac{(k+1)(k-m)}{(k-n)(k+1)}\end{aligned}$$

由此可知，

$$\begin{aligned}S&=t_0\mathrm F\left(\begin{gathered}1,-m\\-n\end{gathered}\middle|1\right)\\&=\mathrm F\left(\begin{gathered}1,-m\\-n\end{gathered}\middle|1\right)\end{aligned}$$

其中整数 $-m\le0$，应用范德蒙德卷积，

$$\begin{aligned}S&=\frac{\Gamma(-n-1+m)\Gamma(-n)}{\Gamma(-n-1)\Gamma(-n+m)}\\&=\frac{n+1}{n+1-m}\end{aligned}$$

例题4 求下面式子的封闭形式，其中整数 $n\ge m\ge0$

$$\sum_{k=0}^{n-1}\binom{k}{m}\frac{1}{n-k}$$

令原式为 $S$，翻转求和顺序，

$$\begin{aligned}S&=\sum_{k=0}^{n-1}\binom{n-1-k}{m}\frac{1}{k+1}\\&=\sum _{k\ge0}\frac{\binom{n-1-k}{m}}{k+1}\end{aligned}$$

到目前为止一切正常，级数的第 $k$ 项 $t_k=\frac{\binom{n-1-k}{m}}{k+1}$，我们似乎只用算出它的相邻两项的比值即可

$$\begin{aligned}\frac{t_{k+1}}{t _k}&=\frac{(k+1) \binom{-k+n-2}{m}}{(k+2) \binom{-k+n-1}{m}}\\&=\frac{(k+1) (k+m-n+1)}{(k+2) (k-n+1)}\end{aligned}$$

这显然不是一个高斯超几何函数相邻两项的比值，它对应的是，

$$S=t_0\mathrm F\left(\begin{gathered}m-n+1,1,1\\-n+1,2\end{gathered}\middle|1\right)$$

我们尚且还不知道这样的超几何函数如何求解。退一步，我们注意到似乎只要在求和中移动 $k$，就可以使比值的 $\frac{(k+1)}{(k+2)}$ 变为 $\frac{k}{(k+1)}$。具体而言，考虑

$$\begin{aligned}S&=\sum _{k\ge0}\frac{\binom{n-1-k}{m}}{k+1}\\&=\sum _{k\ge1}\frac{\binom{n-k}{m}}{k}\\&=\lim _{\epsilon\to0}-\frac{\binom{n}{m}}{\epsilon}+\sum _{k\ge0}\frac{\binom{n-k}{m}}{k+\epsilon}\end{aligned}$$

后半部分级数的第 $k$ 项 $t_k=\frac{\binom{n-k}m}{k+\epsilon}$，其相邻两项的比值

$$\begin{aligned}\frac{t_ {k+1}}{t_k}&=\lim _{\epsilon\to0}\frac{\frac{\binom{n-k-1}m}{k+\epsilon+1}}{\frac{\binom{n-k}m}{k+\epsilon}}\\&=\lim _{\epsilon\to0}\frac{\frac{\binom{n-k-1}m}{k+1}}{\frac{\binom{n-k}m}{k+\epsilon}}\\&=\lim _{\epsilon\to0}\frac{(k+\epsilon ) \binom{n-k-1}{m}}{(k+1) \binom{n-k}{m}}\\&=\lim _{\epsilon\to0}\frac{(k+\epsilon ) (k+m-n)}{(k-n) (k +1)}\end{aligned}$$

由此而言，

$$\begin{aligned}S&=\lim_{\epsilon\to0}-\frac{\binom{n}{m}}{\epsilon}+t _0\mathrm F\left(\begin{gathered}\epsilon,m-n\\-n\end{gathered}\middle|1\right)\\&=\lim _{\epsilon\to0}\frac{\binom{n}{m}}{\epsilon}\left(\mathrm F\left(\begin{gathered}\epsilon,m-n\\-n\end{gathered}\middle|1\right)-1\right)\end{aligned}$$

其中整数 $m-n\le0$，应用范德蒙德卷积，

$$\begin{aligned}S&=\lim _{\epsilon\to0}\frac{\binom{n}{m}}{\epsilon}\left(\frac{\Gamma(-m-\epsilon)\Gamma(-n)}{\Gamma(-n-\epsilon)\Gamma(-m)}-1\right)\\&=\binom{n}{m}\lim_{\epsilon\to0}\frac1\epsilon\left(\frac{m!(n+\epsilon)!\sin(m\pi)\sin(n\pi+\epsilon\pi)}{n!(m+\epsilon)!\sin(m\pi)\sin(m\pi+\epsilon\pi)}-1\right)\\&=\binom{n}{m}\lim_{\epsilon\to0}\frac1\epsilon\left(\frac{m!(n+\epsilon)!\sin(m\pi)(\sin(n\pi)\cos(\epsilon\pi)+\sin(\epsilon\pi)\cos(n\pi))}{n!(m+\epsilon)!\sin(m\pi)(\sin(m\pi)\cos(\epsilon\pi)+\sin(\epsilon\pi)\cos(m\pi))}-1\right)\\&=\binom{n}{m}\lim _{\epsilon\to0}\frac1\epsilon\left(\frac{m!(n+\epsilon)!\sin(m\pi)\sin(n\pi)}{n!(m+\epsilon)!\sin(m\pi)\sin(m\pi)}-1\right)\\&=\binom{n}{m}\lim _{\epsilon\to0}\frac1\epsilon\left(\frac{m!(n+\epsilon)!}{n!(m+\epsilon)!}-1\right)\end{aligned}$$

对于后半部分的极限，可以直接运用洛必达法则求值，得到

$$\lim _{\epsilon\to0}\frac1\epsilon\left(\frac{m!(n+\epsilon)!}{n!(m+\epsilon)!}-1\right)=\mathtt H _ n-\mathtt H _m$$

综上所述，

$$S=\binom{n}m(\mathtt H_ n-\mathtt H_m)$$

库默尔公式与迪克逊公式

有几个公式与范德蒙德卷积十分相似的，属于同一类型，其中一个是

$$\sum_{k=0}^{2n}(-1)^k\binom rk\binom r{2n-k}=(-1)^n\binom rn$$

一方面，考虑生成函数 $(1-x)^r(1+x)^r=(1-x^2)^r$ 两侧 $x^n$ 的系数相等，原等式显然成立。
另一方面，从超几何函数的角度考虑，

$$\begin{aligned}\text{L.H.S.}&=\sum_{k\ge0}(-1)^k\binom rk\binom r{2n-k}\\&=\binom{r}{2n}\mathrm F\left(\begin{gathered}-2n,-r\\-2n+r+1\end{gathered}\middle|-1\right)=\text{R.H.S.}\end{aligned}$$

代入原等式的右侧，并移项，

$$\begin{aligned}\mathrm F\left(\begin{gathered}-2n,-r\\-2n+r+1\end{gathered}\middle|-1\right)&=\frac{(-1)^n\binom rn}{\binom{r}{2n}}\\\mathrm F\left(\begin{gathered}-2n,-r\\-2n+r+1\end{gathered}\middle|-1\right)&=\frac{(-1)^n(2n)!(2n-r)!}{n!(r-n)!}\end{aligned}$$

令 $a=-2n,b=-r$，整理得到

$$\mathrm F\left(\begin{gathered}a,b\\1+b-a\end{gathered}\middle|-1\right)=\frac{(b/2)!(b-a)^\underline{b/2}}{b!}$$

这就是库默尔公式，由库默尔证明于1836年。

例题5 求下面式子的封闭形式，其中整数 $a,b\ge0$

$$\sum_k(-1)^k\binom{a+b}{a+k}\binom{b+a}{b+k}$$

令原式为 $S$，确定 $S$ 的求和范围，写出它的超几何函数形式，并对于这个式子使用库默尔公式，

$$\begin{aligned}S&=\sum_{k=-a}^a(-1)^k\binom{a+b}{a+k}\binom{b+a}{b+k}\\&=\sum _{k\ge0}(-1)^{k-a}\binom{a+b}{k}\binom{a+b}{b-a+k}\\&=(-1)^a\binom{a+b}{b-a}\mathrm F\left(\begin{gathered}-a-b,-2a\\1-a+b\end{gathered}\middle|-1\right)\\&=\frac{\sqrt{\pi } (-4)^a \binom{a+b}{b-a} \Gamma (-a+b+1)}{b! \Gamma \left(\frac{1}{2}-a\right)}\\&=\frac {(a+b)!}{a!b!}\end{aligned}$$

考虑例题5中的恒等式的三项版本，我们可以用其导出一个与库默尔公式相似的超几何函数恒等式

$$\sum_{k\in\mathbb Z}(-1)^k\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+a}{c+k}=\frac{(a+b+c)!}{a!b!c!}$$

这个恒等式对于整数 $a,b,c\ge0$ 成立，证明参见 A Proof of Dixon's Identity -- Journal of Integer Sequences, Vol. 19 (2016)。我们从超几何函数的角度讨论，

确定求和范围，不妨设 $0\le a\le b\le c$，则

$$\begin{aligned}\text{L.H.S.}&=\sum_{k=-a}^a(-1)^k\binom{a+b}{a+k}\binom{b+c}{b+k}\binom{c+a}{c+k}\\&=\sum_{k\ge0}(-1)^{k-a}\binom{a+b}k\binom{b+c}{b+k-a}\binom{a+c}{c+k-a}\\&=(-1)^{-a}\binom{b+c}{b-a}\binom{a+c}{c-a}F\left(\begin{gathered}-2a,-a-b,-a-c\\-a+b+1,-a+c+1\end{gathered}\middle|1\right)=\text{R.H.S.}\end{aligned}$$

代入原等式的右侧，并移项，

$$\mathrm F\left(\begin{gathered}-2a,-a-b,-a-c\\-a+b+1,-a+c+1\end{gathered}\middle|1\right)=\frac{(-1)^a(a+b+c)!}{a!b!c!\binom{b+c}{b-a}\binom{a+c}{c-a}}$$

令 $a=-2a,b=-a-b,c=-a-c$，整理得到

$$\mathrm F\left(\begin{gathered}a,b,c\\1+c-a,1+c-b\end{gathered}\middle|1\right)=\frac{(c/2)!(c-a)^\underline{c/2}(c-b)^\underline{c/2}}{c!(c-a-b)^\underline{c/2}}$$

这就是迪克逊公式，迪克逊最早证明了上面等式在 $a+b<1+c/2$ 时成立。

拓展范德蒙德卷积

关于三个二项式系数的卷积十分罕见而重要，考虑整数 $m,n$，有

$$\sum_k\binom{m-r+s}{k}\binom{n+r-s}{n-k}\binom{r+k}{m+n}=\binom rm\binom sn$$

对此证明的关键点是注意到 $\binom{r+k}{m+n}=\sum_j\binom r{m+n-j} kj$，然后使用范德蒙德卷积，即可堆出右边的表达式。

另一方面，

$$\begin{aligned}\text{L.H.S.}&=\sum_{k\ge0}\binom{m-r+s}{k}\binom{n+r-s}{n-k}\binom{r+k}{m+n}\\&=\binom{n+r-s}n\binom r{m+n}\mathrm F\left(\begin{gathered}1+r,r-m-s,-n\\r-s+1,r-m-n\end{gathered}\middle|1\right)=\text{R.H.S.}\end{aligned}$$

代入原等式的右侧，并移项，

$$\begin{aligned}\mathrm F\left(\begin{gathered}1+r,r-m-s,-n\\r-s+1,r-m-n\end{gathered}\middle|1\right)=\frac{\binom rm\binom sn}{\binom{n+r-s}n\binom r{m+n}}\end{aligned}$$

令 $a=1+r,b=r-m-s,c=r-s+1$，整理得到

$$\mathrm F\left(\begin{gathered}a,b,-n\\c,a+b-c-n+1\end{gathered}\middle|1\right)=\frac{(c-a)^\overline{n}(c-b)^\overline{n}}{c^\overline{n}(c-a-b)^\overline{n}}$$

其中等式成立的条件是整数 $n\ge0$。它通常被称为Saalschütz恒等式，最早由普法夫发表于1797年。从某种意义上说，这个恒等式是拓展范德蒙德卷积，因为当 $n\to\infty$ 时的极限就是范德蒙德卷积。

例题6 求下面式子的封闭形式，其中整数 $m,n\ge0$，

$$\sum_{k\ge0}\binom{n+k}{2k}\binom{2k}k\frac{(-1)^k}{k+m+1}$$

求出原级数的超几何表达，并应用拓展范德蒙德卷积，发现这是 $c=1$ 时的特殊情况。

超几何变换

我们已经拥有了若干超几何函数与组合数之间的恒等式，但这个话题还有更多讨论内容，因为超几何函数也有它们自己的恒等式，称为超几何变换。这样一来，即使一个超几何函数的值尚不知道，我们也可以尝试先利用超几何变换将其变形为一个已知的形式。

我们在研究例题4时注意到对超几何级数移项有时是一种有效的处理方法，我们现在考虑一般情况下，

$$\begin{aligned}\mathrm F\left(\begin{gathered}a_1,\cdots,a _m\\b_1,\cdots,b_n\end{gathered}\middle|x\right)&=\sum _{k\ge0}\frac{a _1^\overline{k}\cdots a _m^\overline{k}x^k}{b _1^\overline{k}\cdots b _m^\overline{k}k!}\\&=1+\sum_{k\ge1}\frac{a _1^\overline{k}\cdots a _m^\overline{k}x^k}{b _1^\overline{k}\cdots b _m^\overline{k}k!}\\&=1+\frac{a _1\cdots a _mx}{b _1\cdots b _m}\sum_{k\ge0}\frac{(a _1+1)^\overline{k}\cdots (a _m+1)^\overline{k}x^k}{(b_1+1) ^\overline{k}\cdots(b_n+1)^\overline{k}(k+1)!}\\&=1+\frac{a _1\cdots a _mx}{b _1\cdots b _m}\mathrm F\left(\begin{gathered}a_1+1,\cdots,a _m+1,1\\b_1+1,\cdots,b_n+1,2\end{gathered}\middle|x\right)\end{aligned}$$

由此我们得到右移项变换：

$$\mathrm F\left(\begin{gathered}a_1,\cdots,a _m\\b_1,\cdots,b_n\end{gathered}\middle|x\right)=1+\frac{a _1\cdots a _mx}{b _1\cdots b _m}\mathrm F\left(\begin{gathered}a_1+1,\cdots,a _m+1,1\\b_1+1,\cdots,b_n+1,2\end{gathered}\middle|x\right)$$

这是最基本的一个超几何变换。如果我们在一点知道它，那么就不用在解决例题4时绕弯路了。

1797年，德国数学家J.F.普法夫（Johann Friedrich Pfaff）发表了一个惊人的反射定律：

$$\frac1{(1-x)^a}\mathrm F\left(\begin{gathered}a,b\\c\end{gathered}\middle|\frac{-x}{1-x}\right)=\mathrm F\left(\begin{gathered}a,c-b\\c\end{gathered}\middle|x\right)$$

例题7 求下面式子的封闭形式，其中整数 $n\ge0$

$$\sum_k(-1)^k2^{-k}\binom nk\binom{n+k}k\bigg/\binom{n+b+k}k$$

连接反射定律和库默尔公式，我们可以得到

$$\begin{aligned}\mathrm F\left(\begin{gathered}a,1-a\\1+b-a\end{gathered}\middle|\frac12\right)&=2^a\mathrm F\left(\begin{gathered}a,b\\1+b-a\end{gathered}\middle|-1\right)\\&=\frac{2^a(b/2)!(b-a)^\underline{b/2}}{b!}\end{aligned}$$

将这个等式转换为关于二项式系数的恒等式，有

$$\sum_k(-1)^k2^{-k}\binom nk\binom{n+k}k\bigg/\binom{n+b+k}k=\frac{2^{-n}(b/2)!(b+n)!}{b!(b/2+n)!}$$

例题8 求下面式子的封闭形式，

$$\sum_{k=0}^m\frac{2m+1}{1+k}(-2)^k\binom mk$$

令原式为 $S$，翻转求和顺序，

$$\begin{aligned}S&=\sum_{k\ge0}\frac{2m+1}{m+1-k}(-2)^{m-k}\binom m{m-k}\\&=\frac{2m+1}{m+1}(-2)^m\mathrm F\left(\begin{gathered}-m-1,1\\1\end{gathered}\middle|\frac12\right)\end{aligned}$$

应用反射定律，

$$\mathrm F\left(\begin{gathered}-m-1,1\\1\end{gathered}\middle|\frac12\right)=\frac1{2^{m+1}}\mathrm F\left(\begin{gathered}-m-1,0\\1\end{gathered}\middle|-1\right)$$

注意到对于 $k\ge0$，有

$$0^{\overline{k}}=\frac{\Gamma(k)}{\Gamma(0)}=[k=0]$$

因此，

$$\mathrm F\left(\begin{gathered}-m-1,0\\1\end{gathered}\middle|-1\right)=1$$

代回原式，得到

$$S=\frac{(-1)^m (2 m+1)}{2 (m+1)}$$

例题9 求下面式子的封闭形式，其中整数 $m\ge0$，

$$\sum_{k=0}^m\frac{2m+1}{2m+1-k}(-2)^k\binom mk$$

令原式为 $S$，翻转求和顺序，依次应用反射定律和库默尔公式

$$\begin{aligned}S&=\sum_{k\ge0}\frac{2m+1}{m+1+k}(-2)^{m-k}\binom m{m-k}\\&=\frac{2m+1}{m+1}(-2)^m\mathrm F\left(\begin{gathered}-m,m+1\\m+2\end{gathered}\middle|\frac12\right)\\&=\frac{2m+1}{m+1}(-1)^m\mathrm F\left(\begin{gathered}-m,1\\m+2\end{gathered}\middle|-1\right)\\&=(-1)^m\frac{2m+1}{m+1}(1/2)!(m+1)^{\underline{1/2}}\\&=\binom{-1/2}m^{-1}\end{aligned}$$

这真是个不错的结果！不过我们不应该止步于此，是时候该找出更多超几何变换了。通过二项式定理，我们很容易注意到，对于整数 $m$，有

$$\sum_{k=0}^m\binom{m+r}kx^ky^{m-k}=\sum_{k=0}^m\binom{-r}k(-x)^k(x+y)^{m-k}$$

为了证明这个恒等式，我们首先假定 $-m\le r\le0$，随后使用多项式推理法。显然有

$$(x+y)^{m+r}y^{-r}=(x+y)^{m+r}(-x+(x+y))^{-r}$$

运用二项式定理，

$$\begin{aligned}\text{L.H.S.}&=y^{-r}\sum_{k=0}^{m+r}\binom{m+r}kx^ky^{m+r-k}\\&=\sum_{k=0}^{m+r}\binom{m+r}kx^ky^{m-k}\end{aligned}$$

其中 $m+r\le m$，而当 $k>m+r$ 时始终有 $\binom{m+r}k=0$，故可以重写求和上界为 $m$：

$$\text{L.H.S.}=\sum_{k=0}^m\binom{m+r}kx^ky^{m-k}$$

同理，

$$\begin{aligned}\text{R.H.S.}&=(x+y)^{m+r}\sum_{k=0}^{-r}\binom{-r}k(-x)^k(x+y)^{-r-k}\\&=\sum _{k=0}^{-r}\binom{-r}k(-x)^k(x+y)^{m-k}\\&=\sum _{k=0}^m\binom{-r}k(-x)^k(x+y)^{m-k}\end{aligned}$$

代入 $\text{L.H.S}=\text{R.H.S}$，对于 $-m\le r\le0$ 这 $m+1$ 种 $r$ 的取值，有

$$\sum_{k=0}^m\binom{m+r}kx^ky^{m-k}=\sum _{k=0}^m\binom{-r}k(-x)^k(x+y)^{m-k}$$

另一方面，等式两边均为关于 $r$ 的 $m$ 次或更低次多项式，在上述 $m+1$ 个不同取值处相等说明等式在一般情况下成立。

言归正传，我们尝试将其转化为超几何函数的一个恒等式。具体而言，考虑将等式两边关于 $y$ 偏微分 $n$ 次，同时除以 $n!$，并用 $m-n-k$ 代替 $k$，

$$\begin{aligned}\frac{\partial^n}{\partial y^nn!}\text{L.H.S.}&=\frac{\partial^n}{\partial y^nn!}\sum_ {k=0}^m\binom{m+r}kx^ky^{m-k}\\&=\frac1{n!}\sum _{k=0}^m\frac{\partial^n}{\partial y^n}\binom{m+r}kx^ky^{m-k}\\&=\frac1{n!}\sum _{k=0}^m\binom{m+r}kx^k(m-k)^{\underline{n}}y^{m-n-k}\\&=\sum _{k\ge0}\binom{m+r}{m-k-n}\frac{(n+k)^{\underline{n}}}{n!}x^{m-n-k}y^k\\&=\sum _{k\ge0}\binom{m+r}{m-n-k}\binom{n+k}nx^{m-n-k}y^k\end{aligned}$$

$$\begin{aligned}\frac{\partial^n}{\partial y^nn!}\text{R.H.S.}&=\frac{\partial^n}{\partial y^nn!}\sum _{k=0}^m\binom{-r}k(-x)^k(x+y)^{m-k}\\&=\frac1{n!}\sum _{k=0}^m\frac{\partial^n}{\partial y^n}\binom{-r}k(-x)^k(x+y)^{m-k}\\&=\frac1{n!}\sum _{k=0}^m\binom{-r}k(-x)^k(m-k)^{\underline{n}}(x+y)^{m-n-k}\\&=\sum_{k\ge0}\binom{-r}{m-n-k}\frac{(n+k)^{\underline{n}}}{n!}(-x)^{m-n-k}(x+y)^k\\&=\sum_{k\ge0}\binom{-r}{m-n-k}\binom{n+k}n(-x)^{m-n-k}y^k\end{aligned}$$

代入 $\frac{\partial^n}{\partial y^nn!}\text{L.H.S.}=\frac{\partial^n}{\partial y^nn!}\text{R.H.S.}$，

$$\sum _{k\ge0}\binom{m+r}{m-n-k}\binom{n+k}nx^{m-n-k}y^k=\sum_{k\ge0}\binom{-r}{m-n-k}\binom{n+k}n(-x)^{m-n-k}y^k$$

将等式两边写成超几何函数的形式并整理，最终得到一条超几何变换式，对于整数 $n\le0$

$$\mathrm F\left(\begin{gathered}a,n\\c\end{gathered}\middle|x\right)=\frac{(a-c)^{\underline{-n}}}{(-c)^\underline{-n}}\mathrm F\left(\begin{gathered}a,n\\1+a+n-c\end{gathered}\middle|1-x\right)$$

这就是范德蒙德变换，当 $x=1$ 时它退化为范德蒙德卷积。

微分方程与高斯恒等式