组合恒等式证明的几种方法

Several Methods for Proving Combinatorial Identities

摘要: 通过含有二项式系数的一些恒等式，介绍了组合证明法、积分法、差分法、生成函数法和机器证明法五种常用的恒等式的证明方法。

Abstract: By proving some identities involving binomial coefficients, this paper introduces five well-known methods for proving combinatorial identities, including the methods of combination, integration, finite difference, generating functions and mechanical proving.

1. 引言

组合序列的相关和式一直是组合数学研究的热点，特别是含有二项式系数、Stirling数、Catalan数、harmonic数、Euler数、Fibonacci数等的相关恒等式。目前，关于超几何恒等式的研究已经较为成熟，对非超几何恒等式，一个证明思路是将其转化成超几何恒等式进行证明 [1]。本文通过含有二项式系数 [1] [2] 的一些恒等式 [3] 来介绍组合恒等式的常用证明方法：组合证明法 [1] [2]、积分法 [1] [4]、差分法 [1]、生成函数法 [5] 和机器证明法 [6]。

2. 基础知识

定义1 二项式系数 [1]：对非负整数 $k$， $\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!\left(n-k\right)!}=\frac{n^{\underset{\_}{k}}}{k!}$，其中 $n^{\underset{\_}{k}}=n\left(n-1\right)\cdots \left(n-k+1\right)$ 为 $n$ 的 $k$

次降阶乘，规定 $n^{\underset{\_}{0}}=1$。

定义2 对给定数列 $\left\{a_n\right\}$，称对应的幂级数 $f\left(x\right)=a_0+a_{1}x+a_2{x}^2+\cdots +a_n{x}^n+\cdots$ 为其生成函数 [5]。

定义3 Fibonacci数列 [7] [8]： $F_{n+2}=F_n+F_{n+1}$，初始条件为 $F_0=0,F_1=1$。

定义4 Lucas数列 [9]： $L_{n+2}=L_n+L_{n+1}$，初始条件为 $L_0=2,L_1=1$。

众所周知，Fibonacci数列可表示成二项式系数的相关和式 [2]。

定理1 对非负整数 $n$，有 $F_{n+1}={\displaystyle \underset{i=0}{\overset{\lfloor \frac{n}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-i\\ i\end{array}\right)}$。

下面我们给出Fibonacci数列和Lucas数列的生成函数，可参考文献 [5]。

定理2 记 $F\left(x\right)$ 和 $L\left(x\right)$ 分别为Fibonacci数列和Lucas数列的生成函数，则

$F\left(x\right)={\displaystyle \underset{n=0}{\overset{+\infty }{\sum }}{F}_n{x}^n}=\frac{x}{1-x-x^2},L\left(x\right)={\displaystyle \underset{n=0}{\overset{+\infty }{\sum }}{L}_n{x}^n}=\frac{2-x}{1-x-x^2}.$

3. 组合恒等式证明的常用五种方法

3.1. 组合证明法

组合证明法的思路是对恒等式两端赋予一定的组合意义将其化为计数问题，再通过构造两个计数对象之间的双射，根据双射的一一对应来得到恒等式。下面以两个经典例子进行说明。

例1证明Chu-Vandermonde恒等式 [1] ${\displaystyle \underset{i+j=k}{\sum }\left(\begin{array}{c}m\\ i\end{array}\right)}\left(\begin{array}{c}n\\ j\end{array}\right)=\left(\begin{array}{c}m+n\\ k\end{array}\right)$ (其中 $m,k$ 为非负整数)。

证明由两个集合元素的个数分别为 $m,n$，分别在其中找一个大小为 $i,j$ 的子集，其中 $i+j=k$，对

所有满足条件的 $i,j$ 求和，即： ${\displaystyle \underset{i+j=k}{\sum }\left(\begin{array}{c}m\\ i\end{array}\right)}\left(\begin{array}{c}n\\ j\end{array}\right)$ ；另一方面，对集合元素个数为 $m+n$ 的集合，其子集大小为 $k$ 的集合的方法数为： $\left(\begin{array}{c}m+n\\ k\end{array}\right)$ ；综上：即有： ${\displaystyle \underset{i+j=k}{\sum }\left(\begin{array}{c}m\\ i\end{array}\right)}\left(\begin{array}{c}n\\ j\end{array}\right)=\left(\begin{array}{c}m+n\\ k\end{array}\right)$。

例2证明 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}k\\ m\end{array}\right)}=\left(\begin{array}{c}n+1\\ m+1\end{array}\right)$ [1]。

证明对于等式右边：假设我们抛了 $n+1$ 次硬币，其中有 $m+1$ 次正面朝上，方法数为 $\left(\begin{array}{c}n+1\\ m+1\end{array}\right)$。对

于等式左边选择 $m$ 个位置，可供选择的位置总数就是求和的变量，如果最后一个正面朝上出现在 $k+1$ 位置上，那么可能出现的方法数就是在最后一个正面朝上出现之前从 $k$ 个可能的位置中选 $m$ 个位置的方法

数，即 $\left(\begin{array}{c}k\\ m\end{array}\right)$。综上：即有 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}k\\ m\end{array}\right)}=\left(\begin{array}{c}n+1\\ m+1\end{array}\right)$。

3.2. 积分法

积分法的主要思想是将求和项或其一部分利用积分表示出来，通过交换积分与求和次序直接得到等式右端或验证左右两端积分后的结果相同来证明恒等式。下面给出两个例子：

例3 证明 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{\left(x_2^{k+1}-x_1^{k+1}\right)y^{n-k}}{{\left(k+1\right)}^2}=\frac{1}{n+1}{\displaystyle \underset{k=0}{\overset{n}{\sum }}\frac{\left({\left(x_2+y\right)}^{n+1}-{\left(x_1+y\right)}^{n+1}\right)y^{n-k}}{k+1}}$ [1]。

证明令 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{\left(x_2^{k+1}-x_1^{k+1}\right)y^{n-k}}{k+1}=\frac{{\left(x_2+y\right)}^{n+1}-{\left(x_1+y\right)}^{n+1}}{n+1}$ 中的 $x_2=x,x_1=0$ 得到：

${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{x^{k+1}{y}^{n-k}}{k+1}=\frac{{\left(x+y\right)}^{n+1}-y^{n+1}}{n+1}.$

对 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{x^{k+1}{y}^{n-k}}{k+1}=\frac{{\left(x+y\right)}^{n+1}-y^{n+1}}{n+1}$ 两边同时除以 $x$ 得到： ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{x^k{y}^{n-k}}{k+1}=\frac{1}{n+1}\frac{{\left(x+y\right)}^{n+1}-y^{n+1}}{x}.$

对 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{x^k{y}^{n-k}}{k+1}=\frac{1}{n+1}\frac{{\left(x+y\right)}^{n+1}-y^{n+1}}{x}$ 两边同时对 $x$ 从 $x_1$ 到 $x_2$ 求积分

等式左边得： ${\displaystyle {\int }_{x_1}^{x_2}{\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{x^k{y}^{n-k}}{k+1}\text{d}x}={\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{x^{k+1}{y}^{n-k}}{{\left(k+1\right)}^2}|\begin{array}{c}{x}_2\\ x_1\end{array}={\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{\left(x_2^{k+1}-x_1^{k+1}\right)y^{n-k}}{{\left(k+1\right)}^2}.$

等式右边得：

$\begin{array}{c}{\displaystyle {\int }_{x_1}^{x_2}\frac{1}{n+1}\frac{{\left(x+y\right)}^{n+1}-y^{n+1}}{x}\text{d}x}=\frac{1}{n+1}{\displaystyle {\int }_{x_1}^{x_2}\frac{{\left(x+y\right)}^{n+1}-y^{n+1}}{x}\text{d}x}\\ =\frac{1}{n+1}{\displaystyle {\int }_{x_1}^{x_2}{\displaystyle \underset{k=0}{\overset{n}{\sum }}{\left(x+y\right)}^k{y}^{n-k}}}\text{d}x=\frac{1}{n+1}{\displaystyle \underset{k=0}{\overset{n}{\sum }}\frac{{\left(x+y\right)}^{k+1}{y}^{n-k}}{k+1}}|\begin{array}{c}{x}_2\\ x_1\end{array}\\ =\frac{1}{n+1}{\displaystyle \underset{k=0}{\overset{n}{\sum }}\frac{\left({(x_2+y)}^{k\text{+1}}-{\left(x_1+y\right)}^{k\text{+1}}\right)y^{n-k}}{k+1}}.\end{array}$

其中： $\frac{{\left(x+y\right)}^{n+1}-y^{n+1}}{x}\text{=}\frac{\left(x+y-y\right){\displaystyle \underset{k=0}{\overset{n}{\sum }}{\left(x+y\right)}^k{y}^{n-k}}}{x}\text{=}{\displaystyle \underset{k=0}{\overset{n}{\sum }}{\left(x+y\right)}^k{y}^{n-k}}.$

即： ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{\left(x_2^{k+1}-x_1^{k+1}\right)y^{n-k}}{{\left(k+1\right)}^2}=\frac{1}{n+1}{\displaystyle \underset{k=0}{\overset{n}{\sum }}\frac{\left({\left(x_2+y\right)}^{n+1}-{\left(x_1+y\right)}^{n+1}\right)y^{n-k}}{k+1}}.$

例4证明 ${\displaystyle \underset{n=0}{\overset{\infty }{\sum }}\frac{2^n}{\left(2n+1\right)\left(\begin{array}{c}2n\\ n\end{array}\right)}}=\frac{\pi }{2}$ [1]。

证明由Gamma函数的性质 [10] [11] $B\left(a,b\right)=\frac{\Gamma \left(a\right)\Gamma \left(b\right)}{\Gamma (a+b)}$， $B\left(a,b\right)={\displaystyle {\int }_0^1{x}^{a-1}}{\left(1-x\right)}^{b-1}\text{d}x$。

可得： ${\left(\begin{array}{c}2n\\ n\end{array}\right)}^{-1}=\left(2n+1\right){\displaystyle {\int }_0^1{x}^n}{\left(1-x\right)}^n\text{d}x$ 以及 $\left(\begin{array}{c}2n\\ n\end{array}\right)=\frac{1}{\left(2n+1\right)B\left(n,n\right)}$。

由上式可得：

$\begin{array}{c}{\displaystyle \underset{n=0}{\overset{\infty }{\sum }}\frac{2^n}{\left(2n+1\right)\left(\begin{array}{c}2n\\ n\end{array}\right)}}={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}\frac{2^n}{\left(2n+1\right)}}\left(2n+1\right){\displaystyle {\int }_0^1{x}^n}{\left(1-x\right)}^n\text{d}x\\ ={\displaystyle {\int }_0^1{\displaystyle \underset{n=0}{\overset{\infty }{\sum }}{2}^n{x}^n{\left(1-x\right)}^n\text{d}x}}={\displaystyle {\int }_0^1\frac{1}{1-2x(1-x)}\text{d}x}\\ ={\displaystyle {\int }_0^1\frac{1}{1-2x+2x^2}\text{d}x}=\frac{\pi }{2}.\end{array}$

3.3. 差分法

差分法的基本思想是通过验证左右两端相邻两项的差相等来证明恒等式，即要证明 $A\left(n\right)=B\left(n\right)$，只需 $A\left(n+1\right)-A\left(n\right)=B\left(n+1\right)-B\left(n\right)$ 和相同的初值即可。

例5证明 ${\displaystyle \underset{k=1}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{{\left(-1\right)}^k}{k}=-H_n$ $\left(H_n={\displaystyle \underset{k=1}{\overset{n}{\sum }}\frac{1}{k}}\right)$ [14] [15]。

证明设左端和式为 $f\left(n\right)$ 可得：

$\begin{array}{c}f\left(n+1\right)-f\left(n\right)={\displaystyle \underset{k=1}{\overset{n+1}{\sum }}\left(\begin{array}{c}n+1\\ k\end{array}\right)}\frac{{\left(-1\right)}^k}{k}-{\displaystyle \underset{k=1}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{{\left(-1\right)}^k}{k}={\displaystyle \underset{k=1}{\overset{n+1}{\sum }}\left(\begin{array}{c}n\\ k-1\end{array}\right)}\frac{{\left(-1\right)}^k}{k}\\ ={\displaystyle \underset{k=0}{\overset{n+1}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{{\left(-1\right)}^{k+1}}{k+1}={\left(-1\right)}^{k+1}{\displaystyle \underset{k=0}{\overset{n+1}{\sum }}\left(\begin{array}{c}n+1\\ k+1\end{array}\right)}\frac{1}{n+1}=\frac{{\left(-1\right)}^k}{n+1}{\displaystyle \underset{k=1}{\overset{n+1}{\sum }}\left(\begin{array}{c}n+1\\ k\end{array}\right)}=\frac{{\left(-1\right)}^k}{n+1}\left({\displaystyle \underset{k=0}{\overset{n+1}{\sum }}\left(\begin{array}{c}n+1\\ k\end{array}\right)-\left(\begin{array}{c}n+1\\ 0\end{array}\right)}\right)\\ =\frac{1}{n+1}\left({\displaystyle \underset{k=0}{\overset{n+1}{\sum }}\left(\begin{array}{c}n+1\\ k\end{array}\right){\left(-1\right)}^k-\left(\begin{array}{c}n+1\\ 0\end{array}\right)}\right)=\frac{0-1}{n+1}=-\frac{1}{n+1}.\end{array}$

再利用 $f\left(0\right)=0$ 可得

${\displaystyle \underset{k=1}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{{\left(-1\right)}^k}{k}=f\left(n\right)={\displaystyle \underset{k=1}{\overset{n}{\sum }}\left(f\left(k\right)-f\left(k-1\right)\right)}={\displaystyle \underset{k=1}{\overset{n}{\sum }}\left(-\frac{1}{k}\right)}=-H_n$ .

例6证明 ${\displaystyle \underset{k=0}{\overset{\text{m}}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\frac{{\left(-1\right)}^k}{k+1}=\frac{1}{n+1}\left(\begin{array}{c}n\\ m+1\end{array}\right){\left(-1\right)}^m+\frac{1}{n+1}$ [1]。

证明令 $S\left(m\right)=\frac{1}{n+1}\left(\begin{array}{c}n\\ m+1\end{array}\right){\left(-1\right)}^m+\frac{1}{n+1}$，只需证明 $S\left(m\right)-S\left(m-1\right)=\left(\begin{array}{c}n\\ m\end{array}\right)\frac{{\left(-1\right)}^m}{m+1}$ 即可。

$\begin{array}{c}S\left(m\right)-S\left(m-1\right)=\left(\frac{1}{n+1}\left(\begin{array}{c}n\\ m+1\end{array}\right){\left(-1\right)}^m+\frac{1}{n+1}\right)-\left(\frac{1}{n+1}\left(\begin{array}{c}n\\ m\end{array}\right){\left(-1\right)}^{m-1}+\frac{1}{n+1}\right)\\ =\frac{1}{n+1}\left(\begin{array}{c}n\\ m+1\end{array}\right){\left(-1\right)}^m+\frac{1}{n+1}\left(\begin{array}{c}n\\ m\end{array}\right){\left(-1\right)}^m=\frac{1}{n+1}{\left(-1\right)}^m\left(\left(\begin{array}{c}n\\ m+1\end{array}\right)\text{+}\left(\begin{array}{c}n\\ m\end{array}\right)\right)\text{=}\frac{1}{n+1}{\left(-1\right)}^m\left(\begin{array}{c}n+1\\ m+1\end{array}\right)\\ =\frac{1}{n+1}\frac{\left(n+1\right)!}{\left(m+1\right)!\left(n-m\right)!}{\left(-1\right)}^m=\frac{n!}{\left(m+1\right)!\left(n-m\right)!}{\left(-1\right)}^m=\frac{1}{m+1}\frac{n!}{m!\left(n-m\right)!}{\left(-1\right)}^m=\left(\begin{array}{c}n\\ m\end{array}\right)\frac{{\left(-1\right)}^m}{m+1}.\end{array}$

再利用 $S\left(0\right)=1$ 即可得证。

3.4. 生成函数法

生成函数法的基本思想是将含有组合序列的求和项转化为其对应的生成函数，通过生成函数的操作

得到相应的函数关系式，进一步取系数返回到原和式即可。给定一个含有组合序列的和式 $A\left(n\right)={\displaystyle \underset{k=0}{\overset{n}{\sum }}{a}_k}$，

要证明 $A\left(n\right)=B\left(n\right)$ 或求出 $A\left(n\right)$ 的表达式(也称为闭形式)，具体步骤如下 [5]：

1) 将新的求和项 $A\left(n\right)x^n$ 对变量 $n$ 求和，记 $S\left(x\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}A\left(n\right)x^n}$ ；

2) 通过交换求和次序并利用已知生成函数的解析式得到 $S\left(x\right)$ 的解析表达式；

3) 要证明 $A\left(n\right)=B\left(n\right)$，只要证明 $$ 和 $B\left(n\right)$ 有相同的生成函数即可。

例7 证明 $\text{3}-F_{n+3}+{\displaystyle \underset{i=1}{\overset{n}{\sum }}{L}_i}={\displaystyle \underset{i=0}{\overset{\lfloor \frac{n}{2}\rfloor }{\sum }}\left(\begin{array}{c}n-i\\ i\end{array}\right)}$ [12]。

证明 由Lucas数列的性质 $L_1+L_2+\cdots +L_n=L_{n+2}-3$ 和定理1可知该等式等价于 $L_{n+2}-F_{n+3}=F_{n+1}$。

利用定理2，不难得到左端的生成函数为：

${\displaystyle \underset{n=0}{\overset{+\infty }{\sum }}\left(L_{n\text{+}2}-F_{n\text{+3}}\right)x^n}={\displaystyle \underset{n=0}{\overset{+\infty }{\sum }}{L}_{n\text{+}2}}{x}^n-{\displaystyle \underset{n=0}{\overset{+\infty }{\sum }}{F}_{n\text{+3}}}{x}^n=\frac{x+3}{1-x-x^2}-\frac{x+2}{1-x-x^2}=\frac{1}{1-x-x^2}$ .

同理，右端生成函数为 ${\displaystyle \underset{n=0}{\overset{+\infty }{\sum }}{F}_{n+1}}{x}^n=\frac{1}{1-x-x^2}$。

可见两端生成函数相等，于是等式得证。

例8证明 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)F_k}=F_{\text{2}n}$ [1]。

证明利用定理2以及 ${\displaystyle \underset{n=0}{\overset{\infty }{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)x^n}=\frac{x^k}{{\left(1-x\right)}^{k+1}}$ 可得：

对等式左端取其生成函数可得：

$\begin{array}{c}{\displaystyle \underset{n=0}{\overset{\infty }{\sum }}{\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)F_k{x}^n}}={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{F}_k}{\displaystyle \underset{n=k}{\overset{\infty }{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}{x}^n={\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{F}_k}\frac{x^k}{{\left(1-x\right)}^{k+1}}=\frac{1}{1-x}{\displaystyle \underset{k=0}{\overset{\infty }{\sum }}{F}_k}{\left(\frac{x}{1-x}\right)}^k\\ =\frac{1}{1-x}\frac{\frac{x}{1-x}}{1-\frac{x}{1-x}-{\left(\frac{x}{1-x}\right)}^2}=\frac{x}{1-3x+x^2}\end{array}$

对等式右端利用生成函数和换元的思想，具体操作如下：

又由于 $F\left(x\right)={\displaystyle \underset{n=0}{\overset{+\infty }{\sum }}{F}_n{x}^n}=\frac{x}{1-x-x^2}$，可得： $F\left(-x\right)=\frac{-x}{1+x-x^2}$

令 $G\left(x\right)=\frac{F\left(x\right)+F\left(-x\right)}{2}\text{=}\frac{x^2}{\left(1-x-x^2\right)\left(1+x-x^2\right)}$，则令 $x=\sqrt{x}$，

可得： $G\left(\sqrt{x}\right)={\displaystyle \underset{n=0}{\overset{\infty }{\sum }}{F}_{2n}}{x}^n=\frac{x}{1-3x+x^2}$

可见两端生成函数相等，于是等式得证。

3.5. 机器证明方法

机器证明法是近几十年才发展起来的证明恒等式的有力方法。目前，超几何恒等式证明的相关研究已经成熟，下面我们介绍最经典的两个超几何算法及WZ方法。

1) Gosper算法：

Gosper算法完全解决了超几何恒等式不定和问题。

对给定的超几何项 $t_n$，Gosper算法寻找满足 $z_{n+1}-z_n=t_n$ 的超几何项 $z_n$。一旦得到不定和 $z_n$，即可求

出和式 $s_n={\displaystyle \underset{k=0}{\overset{n-1}{\sum }}{t}_k}$ 的闭形式 $s_n=z_{n+1}-z_0$。注意 $s_n$ 有可能不是超几何项。

Gosper算法已集成在Maple系统中，通过调用with (SumTools [Hypergeometric])工具包以及Gosper(t(n), n)命令即可求出给定求和项的不定和。这里仅举一例。

例9证明 ${\displaystyle \underset{k=0}{\overset{m}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)k{\left(-1\right)}^k}={\left(-1\right)}^{m}n\left(\begin{array}{c}n-2\\ m-1\end{array}\right)$ [1]。

证明令 $t_k=\left(\begin{array}{c}n\\ k\end{array}\right)k{\left(-1\right)}^k$，由Gosper算法可得：则 $z_k=n\left(\begin{array}{c}n-2\\ k-2\end{array}\right){\left(-1\right)}^{k-1}$

即： ${\displaystyle \underset{k=0}{\overset{m}{\sum }}{t}_k}=z_{m+1}-z_0={\left(-1\right)}^{m}n\left(\begin{array}{c}n-2\\ m-1\end{array}\right)-0={\left(-1\right)}^{m}n\left(\begin{array}{c}n-2\\ m-1\end{array}\right)$。得证。

2) Zeilberger算法

Zeilberger算法用来处理定和问题。给定一个双超几何项 $F\left(n,k\right)$，(即关于n和k都是超几何的)。考

虑和式 $S\left(n\right)={\displaystyle \underset{k}{\sum }F\left(n,k\right)}$。Zeilberger算法寻找与求和变量k无关的一些多项式 $a_0\left(n\right),a_1\left(n\right),\cdots ,a_J\left(n\right)$ 及一

个有理函数 $R\left(n,k\right)$ 使得

${\displaystyle \underset{j=0}{\overset{J}{\sum }}{a}_j\left(n\right)F\left(n+j,k\right)}=G\left(n,k+1\right)-G\left(n,k\right)$

称该式为斜递推关系，其中 $G\left(n,k\right)=R\left(n,k\right)F\left(n,k\right).$ 对该式两端对所有整数 $k$ 求和得到和式 $S\left(n\right)$ 满足的一个递推关系式

${\displaystyle \underset{j=0}{\overset{J}{\sum }}{a}_j}\left(n\right)S\left(n+j\right)=0.$

若要证明恒等式 $S\left(n\right)=T\left(n\right)$，只需验证 $T\left(n\right)$ 也满足该递推关系，且与 $S\left(n\right)$ 具有相同的初值即可。

注意，若能直接求出该递推关系的闭公式，也可直接证明恒等式。

Zeilberger算法也已集成在Maple系统中，通过调用with (SumTools [Hypergeometric])工具包以及Zeilberger (f, n, k, N)命令即可得到斜递推关系。下面我们给出几个例子。

例10证明 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\left(\begin{array}{c}k\\ m\end{array}\right)=2^{n-m}\left(\begin{array}{c}n\\ m\end{array}\right)$ [1]。

证明令 $S\left(n\right)={\displaystyle \underset{k=0}{\overset{n}{\sum }}\left(\begin{array}{c}n\\ k\end{array}\right)}\left(\begin{array}{c}k\\ m\end{array}\right)$，用 $F\left(n,k\right)$ 表示求和项，则由Zeilberger算法可以找到斜递推关系：

$\left(\left(n-m+1\right)N-2n-2\right)F\left(n,k\right)=G\left(n,k+1\right)-G\left(n,k\right)$ 上式等式两边对 $k$ 求和，得到：

$\left(-m+n+1\right)S\left(n+1\right)-\left(2n+2\right)S\left(n\right)=0$。于是有 $\frac{S\left(n+1\right)}{S\left(n\right)}=\frac{2\left(n+1\right)}{-m+n+1}$，其中 $S\left(m\right)=1$。

由于当 $k<m$ 之前的项都为0，当 $k\ge m$ 时每一项才不为0，于是可得

$\begin{array}{c}\frac{S\left(n+1\right)}{S\left(n\right)}\frac{S\left(n\right)}{S\left(n-1\right)}\cdots \frac{S\left(m+1\right)}{S\left(m\right)}=\frac{2^{n-m+1}\frac{\left(n+1\right)!}{m!}}{\left(-m+n+1\right)\left(-m+n\right)\cdots \left(-m+m+1\right)}\\ =\frac{2^{n-m+1}\frac{\left(n+1\right)!}{m!}}{\left(-m+n+1\right)!}=2^{n-m+1}\frac{\left(n+1\right)!}{\left(-m+n+1\right)!m!}=2^{n-m+1}\left(\begin{array}{c}n+1\\ m\end{array}\right)\end{array}$

可得 $S\left(n+1\right)=2^{n-m+1}\left(\begin{array}{c}n+1\\ m\end{array}\right)$ ；即 $S\left(n\right)=2^{n-m}\left(\begin{array}{c}n\\ m\end{array}\right)$。得证。

例11证明Gould’s 恒等式 ${\displaystyle \underset{k=0}{\overset{r}{\sum }}\frac{r}{r-qk}\cdot \left(\begin{array}{c}r-qk\\ k\end{array}\right)\cdot \left(\begin{array}{c}p+qk\\ n-k\end{array}\right)}=\left(\begin{array}{c}p+r\\ n\end{array}\right)$ [13]。

证明令 $S\left(n\right)={\displaystyle \underset{k=0}{\overset{r}{\sum }}\frac{r}{r-qk}\cdot \left(\begin{array}{c}r-qk\\ k\end{array}\right)\cdot \left(\begin{array}{c}p+qk\\ n-k\end{array}\right)}$，用 $F\left(n,k\right)$ 表示求和项，则由Zeilberger算法可以找到

斜递推关系： $\left(\left(n+1\right)N-p-r+n\right)F\left(n,k\right)=G\left(n,k+1\right)-G\left(n,k\right)$。

上式等式两边对 $k$ 求和，得到： $\left(n+1\right)S\left(n+1\right)-\left(p+r-n\right)S\left(n\right)=0$。

即： $\frac{S\left(n+1\right)}{S\left(n\right)}=\frac{p+r-n}{n+1}$ ；其中： $S\left(0\right)=1$。

则： $\frac{S\left(n+1\right)}{S\left(n\right)}\frac{S\left(n\right)}{S\left(n-1\right)}\cdots \frac{S\left(m+1\right)}{S\left(m\right)}=\frac{{\left(p+r\right)}^{\underset{\_}{n}}}{\left(n+1\right)!}=\left(\begin{array}{c}p+r\\ n+1\end{array}\right)=\frac{S\left(n+1\right)}{S\left(0\right)}$。

可得： $S\left(n+1\right)=\left(\begin{array}{c}p+r\\ n+1\end{array}\right)$ ；即： $S\left(n\right)=\left(\begin{array}{c}p+r\\ n\end{array}\right)$。得证。

3) WZ方法

WZ方法是基于Zeilberger算法一个证明超几何恒等式的有效工具。对超几何恒等式

${\displaystyle \underset{k}{\sum }t\left(n,k\right)=rhs\left(n\right)}$，由于 $rhs\left(n\right)$ 也是超几何的，可将其等价于 ${\displaystyle \underset{k}{\sum }F\left(n,k\right)=1}$，其中 $F\left(n,k\right)=\frac{t\left(n,k\right)}{rhs\left(n\right)}$。在

绝大多数情况下，对新的求和项，Zeilberger算法可得到有理满足 $R\left(n,k\right)$ 使得：

$F\left(n+1,k\right)-F\left(n,k\right)=G\left(n,k+1\right)-G\left(n,k\right)$，其中 $G\left(n,k\right)=R\left(n,k\right)F\left(n,k\right)$。对所有整数 $k$ 求和，可得

${\displaystyle \underset{k}{\sum }F\left(n+1,k\right)={\displaystyle \underset{k}{\sum }F\left(n,k\right)}}$，即和式为一常数。再通过验证 ${\displaystyle \underset{k}{\sum }F\left(0,k\right)=1}$ 即可证明该恒等式。

例12证明 ${\displaystyle \underset{k}{\sum }{\left(-1\right)}^k}\left(\begin{array}{c}n\\ k\end{array}\right)\frac{x}{k+x}=\frac{1}{\left(\begin{array}{c}x+n\\ n\end{array}\right)}$ [6]。

证明利用WZ方法，令 $t\left(n,k\right)={\left(-1\right)}^k\left(\begin{array}{c}n\\ k\end{array}\right)\frac{x}{k+x}$， $rhs=\frac{1}{\left(\begin{array}{c}x+n\\ n\end{array}\right)}$。

恒等式两边同除以等式右边得到新的恒等式： ${\displaystyle \underset{k}{\sum }F\left(n,k\right)=1}$，

其中 $F\left(n,k\right)=\frac{t\left(n,k\right)}{rhs\left(n\right)}=\frac{{\left(-1\right)}^k\left(x+n\right)!}{k!\left(n-k\right)!\left(x-1\right)!\left(k+x\right)}$。

由Zeilberger 算法可得到有理函数 $R\left(n,k\right)=\frac{k\left(k+1\right)}{\left(n+1\right)\left(k-n-1\right)}$。

令 $G\left(n,k\right)=R\left(n,k\right)F\left(n,k\right)$，则得到 $F\left(n+1,k\right)-F\left(n,k\right)=G\left(n,k+1\right)-G\left(n,k\right)$。

对所有整数 $k$ 求和，则可得到 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}F\left(n+1,k\right)}={\displaystyle \underset{k=0}{\overset{n}{\sum }}F\left(n,k\right)}$ ；再验证 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}F\left(0,k\right)}=1$ 即可得证。

例13证明 ${\displaystyle \underset{k}{\sum }\left(\begin{array}{c}x+1\\ 2k\text{+}1\end{array}\right)}\left(\begin{array}{c}x-2k\\ n-k\end{array}\right)2^{2k+1}=\left(\begin{array}{c}2x+2\\ 2n+1\end{array}\right)$ [6]。

证明利用WZ方法，令 $t\left(n,k\right)=\left(\begin{array}{c}x+1\\ 2k+1\end{array}\right)\left(\begin{array}{c}x-2k\\ n-k\end{array}\right)2^{2k+1}$， $rhs\left(n\right)=\left(\begin{array}{c}2x+2\\ 2n+1\end{array}\right)$。

恒等式两边同时除以等式右边，得到新的恒等式： ${\displaystyle \underset{k}{\sum }F\left(n,k\right)=1}$。

其中 $F\left(n,k\right)=\frac{t\left(n,k\right)}{rhs\left(n\right)}=2^{2k+1}\frac{\left(x+1\right)！\left(x-2k\right)!\left(2n+1\right)!\left(2x+1-2n\right)!}{\left(2k+1\right)!\left(x-2k\right)!\left(n-k\right)!\left(x-k-n\right)!\left(2x+2\right)!}$。

由Zeilberger算法可得有理函数 $R\left(n,k\right)=\frac{k\left(2k+1\right)\left(x-2n-1\right)}{\left(k-n-1\right)\left(2n-2x-1\right)\left(n-x\right)}$。

令 $G\left(n,k\right)=R\left(n,k\right)F\left(n,k\right)$，则得到 $F\left(n+1,k\right)-F\left(n,k\right)=G\left(n,k+1\right)-G\left(n,k\right)$。

对所有整数 $k$ 求和，则可得到 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}F\left(n+1,k\right)}={\displaystyle \underset{k=0}{\overset{n}{\sum }}F\left(n,k\right)}$ ；再验证 ${\displaystyle \underset{k=0}{\overset{n}{\sum }}F\left(0,k\right)}=1$ 即可得证。

4. 结语

本文通过一些含有二项式系数的相关恒等式介绍了组合恒等式证明的常用五种方法：组合证明法、积分法、差分法、生成函数法和机器证明法。当然，这些方法的应用不仅限于二项式系数的相关恒等式。此外，近些年来，相关方法的推广和应用也得到了广泛关注 [13] [14] [15]。在后续的研究中，将继续探讨这些方法在处理含有其他组合序列和特殊函数的恒等式中的应用。

基金项目

国家自然科学基金项目(11501416)，国家自然科学基金项目(12071235)。

参考文献