1 引言
组合恒等式是组合数学的一个重要部分. 它在数学的各个分支中都有广泛应用, 而且它的证明方法多种多样, 具有很强的灵活性. 下面通过几个实例具体讲述一下,几种证法在组合恒等式中的运用.
2 代数法
通常利用组合恒等式的一些性质进行计算或化简,使得等式两边相等,
r r n r C n x y 在展开式中令x 和或者利用二项式定理(x +y ) n =∑
r =0n
y 为某个特定的
值,也可以先对二项式定理利用幂级数的微商或积分后再代值,得出所需要的
恒等式.
m +1m -1m m +1
+C n +2C n =C n 例1 C n +2,n >m .
分析:这个等式两边都很简单,我们可以利用一些常用的组合恒等式去求证.
m +1m 1m m +1
证明:C n +C n +2C n =C n +2
n m m m 1m m
C n , C n =C n
m +1n +1m
m m m n ∴左边=C n (++2) m +1n +1m
m m n +m +2=C n (+)
m +1n +1-m
m +1
C n =
(n +m +2)(n +1-m ) +m 2+m =C ()
(m +1)(n +1-m )
m n
n 2+3n +2
=C ()
(m +1)(n +1-m )
(n +2)(n +1) m
=C n ()
(m +1)(n +1-m )
m n
m +1
右边=C n +2=
(n +2)! (n +2)(n +1) n !
=
(n +1-m )! m +1! (m +1)(n +1-m )(n -m )! m !
m =C n
(n +1)(n +2) (n +1-m )(m +1)
左边=右边 即证.
1n -12n -2n -11n 03+C n 3+ +C n 3+C n 3=22n . 例2 求证:3n +C n
分析:看到上式,很容易想到二项式的展开式,尝试利用二项式定理去做. 证明:
由二项式定理建立恒等式,
1n -12n -22n -1
(3+n ) n =3n +C n 3x +C n 3x + +C n 3x n -1+x n
令x =1, 即得
1n -12n -2n -14n =22n =3n +C n 3+C n 3+ +C n 3+1
即证.
例3(1)设n 是大于2的整数,则
123n
-2C n +3C n + +(-1) nC n =0. C n
(2)n 为正整数,则
111311n 1+C n +C n + +C n =(2n +1-1) . 23n +1n +1
分析:观察上面两式的系数,很容易想到它们和微分积分有关,我们可以尝试利用求积分或微分的方法去解决这道题目.
0122n n
+C n x +C n x + +C n x 证明:(1)(1+x ) n =C n
等式两边对x 求导,
12
n (1+x n ) -1=C 2C x +n +n +
n -n 1
n n C x
123n
-2C n +3C n + +(-1) n -1nC n 令x =0得, 0=C n
即证.
(2)由二项式定理有,
0122n n
(1+x ) n =C n +C n x +C n x + +C n x
上式两边对x 积分,有
⎰(1+x )
1
n
0122n n
dx =⎰(C n +C n x +C n x + +C n x ) dx
010
1
1
(1+x ) n +1
n +1
x k
=∑C
k +1k =0
n
k n
10
n
11n +1k
(2-1) =∑C n
n +1k +1k =0
111211n 即1+C n +C n + +C n =(2n +1-1) .
23n +1n +1
i n -i i
此类方法证明组合恒等式的步骤是先对恒等式(a +x ) =∑C n a x 两边
n
i =0n
对x 求一阶或二阶导数,或者积分,然后对x 取特殊值代入,得到所需证明的等式.
我们也可以利用组合恒等式的性质,证明一些恒等式,例如
121
+C m 利用m 2=2C m , 求证:12+22+ +n 2=n (n +1)(2n +1)
6
证明:
22111+C 32+ +C n ) +(C 1+C 2+ +C n ) 左边=2(C 2
3232112
=2(1+C 3+C 32+ +C n -C 3) +(1+C 2+C 2+ +C n -C 2) 32=2C n +1+C n
==
2(n +1)! n (n -1)
+
2n -2!3! 1
n (n +1)(2n +1) 6
.
311+6C m +C m 同样的道理利用m 3=6C m ,
可以证明
⎡n (n -1) ⎤
1+2+ +n =⎢
⎣2⎥⎦.
3
3
3
2
3 组合分析法
所谓组合分析法就是通过构造具体的组合计数模型或模型实例,利用不同的方法解得的结果应该相同,从而得到恒等式相等.
r r +1
=C n 例5 证明:C r r +C r r +1+ +C n +1.
+1
证明:C n r +1是n +1元集A ={a 1, a 2, , a n +1}中r +1元子集的个数,这些子集
可以分为n +1类.
第0类:r +1元子集中含有a 1,则共有C n r 个.
r 第1类:不含a 1,但含a 2的r +1元子集共有C n -1个;
,
第n 类:不含a 1, a 2, , a n 但含a n +1的r +1元子集共有C 0r 个. 由加法原理得
r r r +1C 0+C 1r + +C r r +C r r +1 +C n =C n +1.
但是C k r =0, 当k
r r +1
=C n 所以有C r r +C r r +1+ +C n +1.
001122m m m
C n +C m C n +C m C n + +C m C n =C m 例6 求证:C m +n (n >m ) .
证明:构造组合模型,假设一个班有m 个男生,有n 个女生,现在要选m 个人,组成一组,那么有多少种选法.
m
选法一:不区分男女生时,共有m +n 个人,选出m 人,共有选法C m +n ; k 选法二:选出的男生人数为k 个,k =0,1,2, , m , 男生的选法共有C m ,女n -k k
C m 种, 生的选法共有C n n -k ,完成事件的选法共C n
n -k k m n -k k
C m =C m =C n 于是C n . +n , 又因为C n
k k m C m =C m 所以C n +n ,k =0,1,2, , m .
001122m m m C n +C m C n +C m C n + +C m C n =C m 即C m +n (n >m ) . 1222n 2n
) +(C n ) + +(C n ) =C 2当n =m 时,即有(C n n .
4 比较系数法
主要是利用二项式定理中两边多项式相等的充要条件为同次幂的系数相等加以证明.
一般情况下,用比较系数法证明所需辅助函数利用幂的运算性质:
(1+x ) m +n =(1+x ) m (1+x ) n ,其中m ,n 为任意实数,然后利用二项式定理的展
开得到两个多项式,再通过比较同次幂的系数得到所证的恒等式.
上题也可以利用比较系数法
01m m 01n n
+C m x + +C m x )(C n +C n x + +C n x ) 证明:(1+x ) m (1+x ) n =(C m
0010010
=C m C n +(C C x n + +C (C m m +C m +n C C m ) n C
m m +C C m n x
+n
m
m -1
m 1m m 0+ x ) n +C C m +n
0m 1m -1m 0i m -i
C n +C m C n + +C m C n ,又因为C m =C m 所以x 的系数为C m . 所以
m
0m 1m -1m 0001122m m
C m C n +C m C n + +C m C n =C m C n +C m C n +C m C n + +C m C n
,
又因为,
01m m m +n n +m (1+x ) m (1+x ) n =(1+x ) m +n =C m +C x + +C x + +C +n m +n m +n m +n x 001122m m m
C n +C m C n +C m C n + +C m C n =C m 所以C m +n (n >m ) .
即证.
1222n 2n
) +(C n ) + +(C n ) =C 2例 7 求证 (C n n .
证明:(1+x ) n (1+x ) n 展开式中x n 的系数为:
0n 1n -1n 0
C n C n +C n C n + +C n C n
001122n n =C n C n +C n C n +C n C n + +C n C n
=(C ) +(C ) + +(C )
12
n 22n n 2n
n
又(1+x ) n (1+x ) n =(1+x ) 2n ;(1+x ) 2n 展开式中x n 的系数为C 2n , 122n
) +C (n 2) + +C (所以即有 (C n n
2n
=) C 2n .
5 数学归纳法
我们都知道数学归纳法, 在证明数列的题目中, 我们就体会了数学归纳法的好处, 只要按照数学归纳法的两个步骤进行就可以了. 组合恒等式是与自然数有关的命题, 因此, 数学归纳法也就成为证明组合恒等式的常用方法之一.
n n n n
+C n 例8 求证 : C n +1+ +C n +p =C n +p +1, p 为自然数.
分析:这里有一个变量p , 可以利用数学归纳法. 证明:(1)当p =1时,
n n n +1
+C n C n +1=C n +1+1显然成立.
(2)假设p =k 时成立,即
n n n n +1
C n +C n +1+ +C n +k =C n +k +1
.
当p =k +1时,即上式两边同时加上
n n n n C n +C n +1+ +C n +k +C n +k +1
n +1n =C n +k +1+C n +k +1
=C
n +1
n +k +2
.
即当p =k +1时也成立.
由(1)(2)知命题对任意自然数p 皆成立.
01m m
+(-1)1C n + +(-1)m C n =(-1)m C n 例9 证明:(-1)0C n -1
证明:当m =0时, 上式显然成立, 当m =1时, 有
01
+(-1)1C n 左边=(-1)0C n 11=-C n =1-C n -1=右边
所以原式成立. 假设当m =k 时成立, 即
01k k
(-1)0C n +(-1)1C n + +(-1)k C n =(-1)k C n -1.
当m =k +1时,
01k k +1
+(-1)1C n + +(-1)k C n +(-1)k +1C n 左边=(-1)0C n
=(-1) k =(-1) k
(n -1)! n !
+(-1) k +1
n -k -1! k ! n -k -1!(k +1)! (n -1)! n
(1-)
n -k -1! k ! k +1(n -1)! (-1)(n -k -1)
k +1n -k -1! k ! (n -1)!
n -k -2!(k +1)!
=(-1) k
=(-1) k +1
k +1
=(-1) k +1C n -1
即当m =k +1时, 命题也成立. 由(1),(2)知, 命题对任意自然数皆成立.
结 论
关于组合恒等式证明的方法还有很多,例如,微积分法,二项式反演公式法,几何法等. 本文介绍的主要是几种常见的方法,以上的方法是以高中知识为基础,也可以说是组合恒等式证明的初等方法. 通过学习,我们学会用具体问题具体分析和解决问题多样化的思想. 以上例题的解法大多不是唯一的,本文也有提及. 但各种方法之间也存在一定的联系. 有时一道题可以同时使用几种方法,思路很活!
参 考 文 献
[1] 孙淑玲, 许胤龙. 组合数学引论[M].合肥,中国科学技术大学出版社,1999. [2] 吴顺唐. 离散数学[M].上海,华东师范大学出版社出版发行,1997:79-138. [3] 孙世新, 张先迪. 组合原理及其运用[M].北京,国防工业出版社,2006.
[4] 陈镇邃, 浅谈证明组合恒等式的几种方法[J].数学教学通讯,1986,02:15-16. [5] 张红兵, 浅谈组合恒等式的证明方法[J].高等函授学报,2005,19(13):37-42. [6] 柳丽红, 证明组合恒等式的方法与技巧[J].内蒙古电大学刊,2006,86:86-87. [7] 李士荣, 组合恒等式的几种证法及应用[J].重庆工学院学报(自然科学版),2007,21(5):72-74.
致 谢
本论文是在沈邦玉老师的悉心指导下完成的。沈老师渊博的专业知识,严谨的治学态度,精益求精的工作作风,诲人不倦的高尚师德,严以律己、宽以待人的崇高风范,朴实无华、平易近人的人格魅力对我影响深远。不仅使我树立了远大的学术目标、掌握了基本的研究方法,还使我明白了许多待人接物与为人处世的道理。本论文从选题到完成,每一步都是在沈老师的指导下完成的,倾注了沈老师大量的心血。在此,谨向沈老师表示崇高的敬意和衷心的感谢!
1 引言
组合恒等式是组合数学的一个重要部分. 它在数学的各个分支中都有广泛应用, 而且它的证明方法多种多样, 具有很强的灵活性. 下面通过几个实例具体讲述一下,几种证法在组合恒等式中的运用.
2 代数法
通常利用组合恒等式的一些性质进行计算或化简,使得等式两边相等,
r r n r C n x y 在展开式中令x 和或者利用二项式定理(x +y ) n =∑
r =0n
y 为某个特定的
值,也可以先对二项式定理利用幂级数的微商或积分后再代值,得出所需要的
恒等式.
m +1m -1m m +1
+C n +2C n =C n 例1 C n +2,n >m .
分析:这个等式两边都很简单,我们可以利用一些常用的组合恒等式去求证.
m +1m 1m m +1
证明:C n +C n +2C n =C n +2
n m m m 1m m
C n , C n =C n
m +1n +1m
m m m n ∴左边=C n (++2) m +1n +1m
m m n +m +2=C n (+)
m +1n +1-m
m +1
C n =
(n +m +2)(n +1-m ) +m 2+m =C ()
(m +1)(n +1-m )
m n
n 2+3n +2
=C ()
(m +1)(n +1-m )
(n +2)(n +1) m
=C n ()
(m +1)(n +1-m )
m n
m +1
右边=C n +2=
(n +2)! (n +2)(n +1) n !
=
(n +1-m )! m +1! (m +1)(n +1-m )(n -m )! m !
m =C n
(n +1)(n +2) (n +1-m )(m +1)
左边=右边 即证.
1n -12n -2n -11n 03+C n 3+ +C n 3+C n 3=22n . 例2 求证:3n +C n
分析:看到上式,很容易想到二项式的展开式,尝试利用二项式定理去做. 证明:
由二项式定理建立恒等式,
1n -12n -22n -1
(3+n ) n =3n +C n 3x +C n 3x + +C n 3x n -1+x n
令x =1, 即得
1n -12n -2n -14n =22n =3n +C n 3+C n 3+ +C n 3+1
即证.
例3(1)设n 是大于2的整数,则
123n
-2C n +3C n + +(-1) nC n =0. C n
(2)n 为正整数,则
111311n 1+C n +C n + +C n =(2n +1-1) . 23n +1n +1
分析:观察上面两式的系数,很容易想到它们和微分积分有关,我们可以尝试利用求积分或微分的方法去解决这道题目.
0122n n
+C n x +C n x + +C n x 证明:(1)(1+x ) n =C n
等式两边对x 求导,
12
n (1+x n ) -1=C 2C x +n +n +
n -n 1
n n C x
123n
-2C n +3C n + +(-1) n -1nC n 令x =0得, 0=C n
即证.
(2)由二项式定理有,
0122n n
(1+x ) n =C n +C n x +C n x + +C n x
上式两边对x 积分,有
⎰(1+x )
1
n
0122n n
dx =⎰(C n +C n x +C n x + +C n x ) dx
010
1
1
(1+x ) n +1
n +1
x k
=∑C
k +1k =0
n
k n
10
n
11n +1k
(2-1) =∑C n
n +1k +1k =0
111211n 即1+C n +C n + +C n =(2n +1-1) .
23n +1n +1
i n -i i
此类方法证明组合恒等式的步骤是先对恒等式(a +x ) =∑C n a x 两边
n
i =0n
对x 求一阶或二阶导数,或者积分,然后对x 取特殊值代入,得到所需证明的等式.
我们也可以利用组合恒等式的性质,证明一些恒等式,例如
121
+C m 利用m 2=2C m , 求证:12+22+ +n 2=n (n +1)(2n +1)
6
证明:
22111+C 32+ +C n ) +(C 1+C 2+ +C n ) 左边=2(C 2
3232112
=2(1+C 3+C 32+ +C n -C 3) +(1+C 2+C 2+ +C n -C 2) 32=2C n +1+C n
==
2(n +1)! n (n -1)
+
2n -2!3! 1
n (n +1)(2n +1) 6
.
311+6C m +C m 同样的道理利用m 3=6C m ,
可以证明
⎡n (n -1) ⎤
1+2+ +n =⎢
⎣2⎥⎦.
3
3
3
2
3 组合分析法
所谓组合分析法就是通过构造具体的组合计数模型或模型实例,利用不同的方法解得的结果应该相同,从而得到恒等式相等.
r r +1
=C n 例5 证明:C r r +C r r +1+ +C n +1.
+1
证明:C n r +1是n +1元集A ={a 1, a 2, , a n +1}中r +1元子集的个数,这些子集
可以分为n +1类.
第0类:r +1元子集中含有a 1,则共有C n r 个.
r 第1类:不含a 1,但含a 2的r +1元子集共有C n -1个;
,
第n 类:不含a 1, a 2, , a n 但含a n +1的r +1元子集共有C 0r 个. 由加法原理得
r r r +1C 0+C 1r + +C r r +C r r +1 +C n =C n +1.
但是C k r =0, 当k
r r +1
=C n 所以有C r r +C r r +1+ +C n +1.
001122m m m
C n +C m C n +C m C n + +C m C n =C m 例6 求证:C m +n (n >m ) .
证明:构造组合模型,假设一个班有m 个男生,有n 个女生,现在要选m 个人,组成一组,那么有多少种选法.
m
选法一:不区分男女生时,共有m +n 个人,选出m 人,共有选法C m +n ; k 选法二:选出的男生人数为k 个,k =0,1,2, , m , 男生的选法共有C m ,女n -k k
C m 种, 生的选法共有C n n -k ,完成事件的选法共C n
n -k k m n -k k
C m =C m =C n 于是C n . +n , 又因为C n
k k m C m =C m 所以C n +n ,k =0,1,2, , m .
001122m m m C n +C m C n +C m C n + +C m C n =C m 即C m +n (n >m ) . 1222n 2n
) +(C n ) + +(C n ) =C 2当n =m 时,即有(C n n .
4 比较系数法
主要是利用二项式定理中两边多项式相等的充要条件为同次幂的系数相等加以证明.
一般情况下,用比较系数法证明所需辅助函数利用幂的运算性质:
(1+x ) m +n =(1+x ) m (1+x ) n ,其中m ,n 为任意实数,然后利用二项式定理的展
开得到两个多项式,再通过比较同次幂的系数得到所证的恒等式.
上题也可以利用比较系数法
01m m 01n n
+C m x + +C m x )(C n +C n x + +C n x ) 证明:(1+x ) m (1+x ) n =(C m
0010010
=C m C n +(C C x n + +C (C m m +C m +n C C m ) n C
m m +C C m n x
+n
m
m -1
m 1m m 0+ x ) n +C C m +n
0m 1m -1m 0i m -i
C n +C m C n + +C m C n ,又因为C m =C m 所以x 的系数为C m . 所以
m
0m 1m -1m 0001122m m
C m C n +C m C n + +C m C n =C m C n +C m C n +C m C n + +C m C n
,
又因为,
01m m m +n n +m (1+x ) m (1+x ) n =(1+x ) m +n =C m +C x + +C x + +C +n m +n m +n m +n x 001122m m m
C n +C m C n +C m C n + +C m C n =C m 所以C m +n (n >m ) .
即证.
1222n 2n
) +(C n ) + +(C n ) =C 2例 7 求证 (C n n .
证明:(1+x ) n (1+x ) n 展开式中x n 的系数为:
0n 1n -1n 0
C n C n +C n C n + +C n C n
001122n n =C n C n +C n C n +C n C n + +C n C n
=(C ) +(C ) + +(C )
12
n 22n n 2n
n
又(1+x ) n (1+x ) n =(1+x ) 2n ;(1+x ) 2n 展开式中x n 的系数为C 2n , 122n
) +C (n 2) + +C (所以即有 (C n n
2n
=) C 2n .
5 数学归纳法
我们都知道数学归纳法, 在证明数列的题目中, 我们就体会了数学归纳法的好处, 只要按照数学归纳法的两个步骤进行就可以了. 组合恒等式是与自然数有关的命题, 因此, 数学归纳法也就成为证明组合恒等式的常用方法之一.
n n n n
+C n 例8 求证 : C n +1+ +C n +p =C n +p +1, p 为自然数.
分析:这里有一个变量p , 可以利用数学归纳法. 证明:(1)当p =1时,
n n n +1
+C n C n +1=C n +1+1显然成立.
(2)假设p =k 时成立,即
n n n n +1
C n +C n +1+ +C n +k =C n +k +1
.
当p =k +1时,即上式两边同时加上
n n n n C n +C n +1+ +C n +k +C n +k +1
n +1n =C n +k +1+C n +k +1
=C
n +1
n +k +2
.
即当p =k +1时也成立.
由(1)(2)知命题对任意自然数p 皆成立.
01m m
+(-1)1C n + +(-1)m C n =(-1)m C n 例9 证明:(-1)0C n -1
证明:当m =0时, 上式显然成立, 当m =1时, 有
01
+(-1)1C n 左边=(-1)0C n 11=-C n =1-C n -1=右边
所以原式成立. 假设当m =k 时成立, 即
01k k
(-1)0C n +(-1)1C n + +(-1)k C n =(-1)k C n -1.
当m =k +1时,
01k k +1
+(-1)1C n + +(-1)k C n +(-1)k +1C n 左边=(-1)0C n
=(-1) k =(-1) k
(n -1)! n !
+(-1) k +1
n -k -1! k ! n -k -1!(k +1)! (n -1)! n
(1-)
n -k -1! k ! k +1(n -1)! (-1)(n -k -1)
k +1n -k -1! k ! (n -1)!
n -k -2!(k +1)!
=(-1) k
=(-1) k +1
k +1
=(-1) k +1C n -1
即当m =k +1时, 命题也成立. 由(1),(2)知, 命题对任意自然数皆成立.
结 论
关于组合恒等式证明的方法还有很多,例如,微积分法,二项式反演公式法,几何法等. 本文介绍的主要是几种常见的方法,以上的方法是以高中知识为基础,也可以说是组合恒等式证明的初等方法. 通过学习,我们学会用具体问题具体分析和解决问题多样化的思想. 以上例题的解法大多不是唯一的,本文也有提及. 但各种方法之间也存在一定的联系. 有时一道题可以同时使用几种方法,思路很活!
参 考 文 献
[1] 孙淑玲, 许胤龙. 组合数学引论[M].合肥,中国科学技术大学出版社,1999. [2] 吴顺唐. 离散数学[M].上海,华东师范大学出版社出版发行,1997:79-138. [3] 孙世新, 张先迪. 组合原理及其运用[M].北京,国防工业出版社,2006.
[4] 陈镇邃, 浅谈证明组合恒等式的几种方法[J].数学教学通讯,1986,02:15-16. [5] 张红兵, 浅谈组合恒等式的证明方法[J].高等函授学报,2005,19(13):37-42. [6] 柳丽红, 证明组合恒等式的方法与技巧[J].内蒙古电大学刊,2006,86:86-87. [7] 李士荣, 组合恒等式的几种证法及应用[J].重庆工学院学报(自然科学版),2007,21(5):72-74.
致 谢
本论文是在沈邦玉老师的悉心指导下完成的。沈老师渊博的专业知识,严谨的治学态度,精益求精的工作作风,诲人不倦的高尚师德,严以律己、宽以待人的崇高风范,朴实无华、平易近人的人格魅力对我影响深远。不仅使我树立了远大的学术目标、掌握了基本的研究方法,还使我明白了许多待人接物与为人处世的道理。本论文从选题到完成,每一步都是在沈老师的指导下完成的,倾注了沈老师大量的心血。在此,谨向沈老师表示崇高的敬意和衷心的感谢!