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

· · 个人记录

广告：在我的cnblogs博客上查看

你可以在这里找到一个PDF版本

翻到了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\mathrm{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

考虑这个求和相邻两项的比值 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\ge0

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 的常数项的值为 1，巧的是 A 的常数项也为 1，这使得我们断定这两个级数相等，即

A=t_0S=S

通过后面要讲述的方法，我们将可以轻松的求出 S=\binom{2n}{n}，从而求出了 A 的封闭形式。

为了更加通用和方便地通过 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 _n^{\overline{k}}k!}

（在行内，我们则使用记号 \mathrm F(a_ 1,\cdots,a_ m;b _ 1,\cdots,b_ n;x) 表示）不难发现，超几何级数的常数项总为 1，而其相邻两项的比值为

\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 _n^{\overline{k+1}}}\frac{b _1^{\overline{k}}\cdots b _n^{\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} \binom 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 _n^{\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 _n^{\overline{k}}k!}\\&=1+\frac{a _1\cdots a _mx}{b _1\cdots b _n}\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 _n}\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{\mathrm d^n}{\mathrm d y^nn!}\text{L.H.S.}&=\frac{\mathrm d^n}{\mathrm d y^nn!}\sum_ {k=0}^m\binom{m+r}kx^ky^{m-k}\\&=\frac1{n!}\sum _{k=0}^m\frac{\mathrm d^n}{\mathrm dy^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{\mathrm d^n}{\mathrm dy^nn!}\text{R.H.S.}&=\frac{\mathrm d^n}{\mathrm dy^nn!}\sum _{k=0}^m\binom{-r}k(-x)^k(x+y)^{m-k}\\&=\frac1{n!}\sum _{k=0}^m\frac{\mathrm d^n}{\mathrm dy^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}(x+y)^k\end{aligned}

代入 \frac{\mathrm d^n}{\mathrm dy^nn!}\text{L.H.S.}=\frac{\mathrm d^n}{\mathrm dy^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}(x+y)^k

取 x=1，将等式两边写成超几何函数的形式并整理，最终得到一条超几何变换式，对于整数 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 时它退化为范德蒙德卷积。

微分方程与高斯恒等式

为了简便起见，我们简记关于 x 的求导算子为 \mathcal D，即

\mathcal D=\frac{\mathrm d}{\mathrm dx}

上面推理范德蒙德变换所使用的微分方法看起来十分有用，事实上，这个例子是具有指导意义的。我们来看看一个一般的超几何函数关于 x 求导时会发生什么：

\cdots b_n^{\overline{k}}(k-1)!}\\&=\sum_{k+1\ge1}\frac{a_1^{\overline{k+1}}\cdots a_m^{\overline{k+1}}x^k}{b_1^{\overline{k+1}} \cdots b_n^{\overline{k+1}}k!}\\&=\sum_{k\ge0}\frac{a_1(a_1+1)^{\overline{k}}\cdots a_m(a_m+1)^{\overline{k}}x^k}{b_1(b_1+1)^{\overline{k}} \cdots b_n(b_n+1)^{\overline{k}}k!}\\&=\frac{a_1\cdots a_m}{b_1\cdots b_n}\mathrm F\left(\begin{gathered}a_1+1,\cdots,a_m+1\\b_1+1,\cdots,b_n+1\end{gathered}\middle|x\right)\end{aligned}

这样参数被移出来了一项并且原参数都增加了 1。当然，我们尝试是否可以用微分法调整超几何函数中的一个参数而保持其他参数不变。为此，我们考虑算子

\vartheta=x\mathcal {D}

即 \vartheta 算子先对函数求关于 x 的导数，然后再把结果乘 x。这个算子给出

\vartheta\mathrm F\left(\begin{gathered}a_1,\cdots,a_m\\b_1,\cdots,b_n\end{gathered}\middle|x\right)=\sum_{k\ge0}\frac{ka_1^{\overline{k}}\cdots a_m^{\overline{k}}z^k}{b_1^{\overline{k}}\cdots b_n^{\overline{k}}k!}

这个式子乍一看不太有用，但是我们尝试用 \vartheta 和某个上参数（如 a_1）的和乘以 \mathrm F(a_1,\cdots a_m;b_1,\cdots b_n;x)，得到

\begin{aligned}(\vartheta+a_1)\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+k)a_1^{\overline{k}}\cdots a_m^{\overline{k}}z^k}{b_1^{\overline{k}}\cdots b_n^{\overline{k}}k!}\\&=\sum_{k\ge0}\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_1\mathrm F\left(\begin{gathered}a_1+1,a_2,\cdots a_m\\b_1,\cdots,b_n\end{gathered}\middle|x\right)\end{aligned}

这样，只有选定的一个上参数改变了。同时，一个类似的技巧也可以运用于下参数，不过这将把下参数减少而不是增加：

\begin{aligned}(\vartheta+b_1-1)\mathrm F\left(\begin{gathered}a_1,\cdots,a_m\\b_1,\cdots,b_n\end{gathered}\middle|x\right)&=\sum_{k\ge0}\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\ge0}\frac{(b_1-1)(a_1+1)^{\overline{k}}\cdots a_m^{\overline{k}}z^k}{(b_1-1)^{\overline{k}}\cdots b_n^{\overline{k}}k!}\\&=(b_1-1)F\left(\begin{gathered}a_1,\cdots,a_m\\b_1-1,b_2\cdots,b_n\end{gathered}\middle|x\right)\end{aligned}

现在我们尝试把这两个式子结合起来看（简记 \mathrm F(a_1,\cdots a_m;b_1,\cdots b_n;x)=\mathrm F），我们有

\begin{aligned}(\vartheta+a_1)\cdots(\vartheta+a_m)\mathrm F&=a_1\cdots a_m\mathrm F\left(\begin{gathered}a_1+1,\cdots,a_m+1\\b_1,\cdots,b_n\end{gathered}\middle|x\right)\\(\vartheta+b_1-1)\cdots(\vartheta+b_n-1)\mathrm F&=(b_1-1)\cdots(b_n-1)\mathrm F\left(\begin{gathered}a_1,\cdots,a_m\\b_1-1,\cdots,b_n-1\end{gathered}\middle|x\right)\end{aligned}

我们容易发现，上面一行右边的超几何函数是下面一行右边的超几何函数的导数，由此我们得到一个一般的超几何函数都满足的微分方程

\mathcal D(\vartheta+b_1-1)\cdots(\vartheta+b_n-1)\mathrm F=(\vartheta+a_1)\cdots(\vartheta+a_m)\mathrm F

这个似乎让人眼花缭乱式子的式子就是超几何微分方程。我们不妨从一个基本的例子出发，只考虑普通超几何函数 \mathrm F(x)=\mathrm F(a,b;c;x)。代入上面的微分方程，我们有

\mathcal D(\vartheta+c-1)\mathrm F=(\vartheta+a)(\vartheta+b)\mathrm F

代入算子 \mathcal D 和 \vartheta 的含义，并整理成通常的微分方程的记号，

x(1-x)\mathrm F''(x)=(c-(a+b+1)x)\mathrm F'(x)-ab\mathrm F(x)=0

尝试求解这个微分方程会发现，\mathrm F(a,b;c;x) 是唯一满足这个微分方程且常数项为 1 的形式幂级数。事实上，这不是一个巧合。我们尝试从任意一个超几何微分方程回到幂级数：假设 \mathrm F(x)=\sum_{k\ge0}t_kx^k 是某个满足超几何微分方程的幂级数。从超几何微分方程的形式出发，必定有

\frac{t_{k+1}}{t_k}=\frac{(k+a_1)\cdots(k+a_m)}{(k+b_1)\cdots(k+b_n)(k+1)}

从而解得，\mathrm F(x)=c\mathrm F(a_1,\cdots,a_m;b_1,\cdots,b_n;x)。因此，我们证明了超几何级数 F(a_1,\cdots,a_m;b_1,\cdots,b_n;x) 是唯一满足超几何微分方程且常数项为 1 的形式幂级数。

我们还可以用 x 乘超几何微分方程的等式两边，这将给出一个相当有启发性的只包含算子 \vartheta 式子：

\vartheta(\vartheta+c-1)\mathrm F=x(\vartheta+a)(\vartheta+b)\mathrm F

这个式子的启发性意义在于其算子与超几何级数的相邻两项的比值一一对应：左边第一个因子 \vartheta=(\vartheta+1-1) 对应相邻两项的比值中的 k+1，与一般的超几何级数中的分母的 k! 对应；其他因子 (\vartheta+b_j-1) 与 b_j^{\overline{k}} 相对应，而右边的 z 与 z^k 相对应， (\vartheta+a_j) 则与 a_j^{\overline{k}} 相对应。

例题10 （二项式定理）求证：

(a+b)^r=\sum_{k=0}^r\binom rka^kb^{r-k}

这不是什么新鲜的式子，不过从超几何的角度来研究一下总是有益的。首先将等式右边重写为超几何函数的形式，

\text{R.H.S.}=b^r\mathrm F\left(\begin{gathered}-r\\{}\end{gathered}\middle|-\frac ab\right)

令 x=-a/b，得到

\text{R.H.S.}=b^r\mathrm F\left(\begin{gathered}-r\\{}\end{gathered}\middle|x\right)

其中 \mathrm F(-r;;x) 满足超几何微分方程

\vartheta\mathrm F=x(\vartheta-r)\mathrm F

另一方面 f(x)=(1-x)^r 也满足上面的超几何微分方程，由此可知

(1-x)^r=\mathrm F\left(\begin{gathered}-r\\{}\end{gathered}\middle|x\right)

代回原式，

\begin{aligned}\text{L.H.S.}&=(-bx+b)^r\\&=b^r(1-x)^r\\&=b^r\mathrm F\left(\begin{gathered}-r\\{}\end{gathered}\middle|x\right)=\text{R.H.S.}\end{aligned}

由此，原恒等式成立。

言归正传，这个微分理论的一个用途是证明新的超几何变换，因为每个确定的超几何微分方程只有一个（常数项为 1 的）解，从而如果两个形式上不同的超几何函数满足同一个超几何微分方程，那么它们一定总是相等。考虑下面两个超几何级数

\mathrm F\left(\begin{gathered}2a,2b\\a+b+\frac12\end{gathered}\middle|x\right),\mathrm F\left(\begin{gathered}a,b\\a+b+\frac12\end{gathered}\middle|4x(1-x)\right)

它们都满足微分方程

x(1-x)\mathrm F''(x)+(a+b+\frac12)(1-2x)\mathrm F'(x)-4ab\mathrm F(x)=0

由此可知，

\mathrm F\left(\begin{gathered}2a,2b\\a+b+\frac12\end{gathered}\middle|x\right)=\mathrm F\left(\begin{gathered}a,b\\a+b+\frac12\end{gathered}\middle|4x(1-x)\right)

这就是高斯恒等式，由德国数学家高斯在1813年发表。特别地，当 x=1/2 时，可以连接高斯恒等式和范德蒙德卷积，

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

运用这个公式时必须注意原超几何级数只在 a+b+1/2 是正整数时收敛。

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

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

令原式为 S。注意到只有满足 0\le k\le m-n 的项是非零的，重写求和上界，

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

计算其相邻两项的比值

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

由此可知，

\begin{aligned}S&=\binom mn\mathrm F\left(\begin{gathered}-m-n-1,n-m\\-m\end{gathered}\middle|\frac12\right)\\&=[m+n\text{是偶数}]\binom mn\sqrt\pi\frac{(\frac{-m-n-1}2)^{\overline{\frac{n+1-m}2}}}{(-m-n-1)!}\\&=[m+n\text{是偶数}]2^{n-m}\binom{(m+n)/2}n\end{aligned}

例题12 求下面式子的封闭形式，其中整数 n\ge0 且 n\not\equiv2(\bmod 3)，

\sum_k8^k\binom nk\binom{\frac13n-\frac16}k\bigg/\binom{\frac43n-\frac23}k

令原式为 S。将 S 写成超几何函数的形式，并应用高斯恒等式和库默尔公式，

\begin{aligned}S&=\mathrm F\left(\begin{gathered}\frac16-\frac13n,-n\\\frac23-\frac43n\end{gathered}\middle|-8\right)\\&=\mathrm F\left(\begin{gathered}\frac13-\frac23n,-2n\\\frac23-\frac43n\end{gathered}\middle|-1\right)\\&=\binom{2n}n\bigg/\binom{\frac43n-\frac23}n\end{aligned}

这实在是一个令人感到不可思议的结果，这个恒等式即使是在小数值时也不容易手工计算。然而这个恒等式完全没有用（除了用作一道例题之外），它几乎肯定不会在实际问题中出现。

小结与闲话

那本文到此所有的知识点就都讲解完毕了~，写了超过2.6w字，总时长四天，还是很希望能让大家（当然还有我自己）学到新东西的。在《具体数学》上还有部分超几何求和（Gosper算法）和机械求和法的讲解作为超几何方法的更进一步拓展。另一方面，根据Wolfram Mathematica的提示（DifferenceRootReduce[]），超几何函数与生成函数、整式递推和矩阵还有更深刻的联系，我以后也许会单独谈谈（其实现在我还没想清楚这个联系是什么，但是可以确定它是存在的，参考一个三重求和下的组合数问题 -- 方而静的笔记）。

写这篇文章时我每个式子都在纸上推导后又用数学软件验证，并与书上结果核对了，但难免仍有错漏，欢迎读者指出。祝您早日成为数数大师！