证明组合恒等式的方法与技巧
内蒙古电大学刊 2006年第10期(总第86期)
证明组合恒等式的方法与技巧
柳丽红
(山西机电职工学院大众分院, 山西太原030024)
[摘 要]以高中二项式定理和排列组合知识为理论基础, 对几个常见重要的例题作分析, 总结组合
恒等式常见的证明方法与技巧。
[关键词]组合 组合数 组合恒等式 二项式定理
组合恒等式的证明有一定的难度和特殊的技巧, 且灵活性很强, 下面就以例题讲解的形式, 把证明组合恒等式的常见方法与技巧列举出来。
1. 利用组合公式证明
n !
组合公式:C m n =m ! (n -m ) !
n m -1m +1m +1
例1 求证:C m C =C , 分析:n =m n -1n -m n
这题可以利用组合公式解决, 等式两边都只是一个简单的组合数。由此, 我们只要把相关组合公式代入, 经过化简, 等号两边相等即可。
n ! n
证明:∵C m ==×n
m ! (n -m ) ! m
(m -1) ! (n -m ) !
n n ! -1m +1=C m ×n -1, m n -m (m +1) ! (n -m ) !
n !
==C m n m ! (n -m ) !
n m -1m +1m +1
∴C m C =C n =n -1n 技巧:此方法思路清晰, 对处理比较简单的等式证明很有效, 但运算量比较大, 如遇到比较复杂一点的组合恒等式, 此方法不可取。
2. 利用组合数性质证明组合数的基本性质:
n -m m -1
(1) C m ; (2) C m C m ; (3) k ·C k n =C n n +1=C n +n n =
-112n n 12n ·C k (4) C 0(5) C 0n -1; n +C n +C n …C n =2; n -C n +C n +2-1m -1+L +C m n +m +1=C n +m
12m -1
例2 求证:C 0n +C n +1+C n +2+L +C n +m -1=-1
C m n +m
变形, 然后整理而得到求证。
m m -112
证明:∵C m ∴C 0n +1=C n +C n n +C n +1+C n +2+
-1012m -1
L +C m n +m -1=C n +1+C n +1+C n +2+L +C n +m -1=2m -12m -1C 1n +2+C n +2+L +C n +m -1=C n +3+L +C n +m -1=…-1012m -1m -1C m n +m ∴C n +C n +1+C n +2+L +C n +m -1=C n +m
3. 利用二项式定理证明
我们都知道二项式定理:
n n -1n -22-1
(a +b ) =a n +C 1b +C 2b +…+C n n a n a n ab n -1+b n , 对于某些比较特殊的组合恒等式可以用它来证明, 下面以两个例子说明:
3. 1直接代值
22n -1
例3 求证明:1+3·C 1·n +3·C n +…+3
-1
C n +3n =22n n
分析:上题左边的各项组合数都是以C i n a n -i b i 的形式出现, 这样自然全联想到二项式定理。用直接代值法。此方法的关键在于赋值, 在一般情况, a , b 值都不会很大, 一般都是0, 1, -1, 2, -2, 3, -3这些数或简单字母, 而且a , b 值与恒等式右边也有必然的联系, 在做题的时候要抓住这点。
02132
例4 求证C -C +C -1-a n 1-a n 1-a n
n +1n
43n n
C +L +(-1) C =1-a n 1-a n 1-a
分析:本题要用到组合数性质5及二项式定理。
23
证明:∵左边=[C 0-C 1n +C n -C n +L +(-1-a n
1n n 12233
1) C n ]=[C 0n -aC n +a C n -a C n +L +(-1-a n n n 1) a C n ]
1a n n =1-1) -1-A ) 1-a 1-a
1-a 01-a 211-a 321-a 43∴C -C +C -C +L +1-a n 1-a n 1-a n 1-a n
分析:观察到, 等式左边各项的组合数的上标和下标存在联系:上标+n =下标, 而且各项上、下标是递增+1的。由此我们想到性质; (2) 将左边第一项
柳丽红 证明组合恒等式的方法与技巧 教育教学研究
n
(-1)
n
1-a n +1n a (1-a )
C n 1-a a -13. 2求导代值
3
例5 求证:2·1·C 2(n -1) ·n +3·2·C n …+n ·
2n -2(n 2) 分析:观察左边各项组合数的系数发现不可以直接运用二项式定理, 但系数也有一定的规律, 系数都是i (i -1) i =2, 3, …n 我们又知道(x i ) =i (i -1) i -2
x 由此我们想到了求导的方法。
n 122n n
证明:对(1+x ) =C 0n +C n x +C n x +…+C n x
n -2
两边求二阶导数, 得n ·(n -1) ·(1+x ) =2·1·C 2n
第零种取法为选零个男生和k 个女生, 第一种取法
为选一个男生和(k -1) 个女生, L , 第i 种取法为选i 个男生和(k -i ) 女生(i =0, 1, 2, L , k ) , 由乘法原
i -i
理, 第i 种取法共有C m C k n 种方法, 再由加法原理,
k 1k -1k -20总的取法有C 0+C 2+L +C k m C n +C m C n m C n m C n 种方法。
k 1k -1k -20k
∴C n +C 2+L +C k m C n +C m C n m C n m C n =C m +n 技巧:用组合分析法证明组合恒等式的步骤是:选指出式子的一边的某个问题的解, 然后应用加法原理和乘法原理等去证明式子的另一边, 也是该组合问题的解。
6. 利用数学归纳法证明
我们都知道数学归纳法, 在证明数列的题目中, 我们就体会了数学归纳法的好处, 只要按照数学归纳法的两个步骤进行就可以了。某些组合恒等式的证明也可以用数学归纳法来证明。
k k m m
例8. 求证:∑(-1) C n =(-1) C n -1
k =0m
+3·2·C 3(n -1) ·C n x n -2n x +…+n n ·
令x =1, 得2·1·C 22·C 3n -1) ·C n n +3·n +…+n (n =n (n -1) ·2n -2(n 2)
技巧:此方法证明组合恒等式的步骤是, 先对恒
n
等式(a +x ) =∑C i m a n -1x i 两边对x 求一阶或二阶
i =0n
导数, 然后适当取x 的值代入。
4. 利用数列求和方法证明例6已知:{a n }是等差数列,
12n n -1求证:a 1C 0(a 1n +a 2C n +a 3C n +L +a a +1C n =2
+a n +1
12n 证明:令S 1=a 1C 0n +a 2C n +a 3C n +L +a a +1C n 12n S 2=a n +1C 0n +a n C n +a n C n +L +a 1C n
∵{a n }是等差数列, ∴a 1+a a +1=a 2+a n =a 3+a a -1=L
12n
∴S 1+s 2=(a +a n -1) C 0(a 1n +C n +C n +L +C n =
+a n +1) 2n
n -k 又∵C k ∴s 1=s 2 ∴(a 1+a n +1) 2n =n =C n
2s 1
12∴S 1=2n -1(a 1+a n +1) 即a 1C 0n +a 2C n +a 3C n +L
+a a +1C n n
=2n -1(a 1+a n +1) 5. 利用组合分析方法证明
所谓组合分析法就是通过构造具体的组合计数模型, 采用了“算两次”的方法, 再根据组合数的加法原理和乘法原理得到恒等式两边相等。
k 1k -1k -20
例7. 求证:C 0+C 2+L +C k m C n +C m C n m C n m C n =C k m +n
证明:先看右边, C k m +n 相当于从m 个男生和n 个女生中选k 个人, 共有m +n 种方法。
再看左边, 这样的k 人小组共有(k +l ) 种取法:
分析:由于上式左边是数列求和, 用其他方法较
困难, 我们用数学归纳法试一试。
证明(略) :技巧:用本方法证明的思路清晰, 只需分两步进行即可, 但归纳法的关键是由“假设n =k 成立, 推导到n =k +l 也成立”这一步中间的变化过程比较复杂, 在“无路可走”的情况下, 归纳法也是一个好的选择。
7. 利用概率的方法证明
有些组合恒等式的证明, 用概率的方法证明也较为简单。
12n n
例9. 求证:C 0解法略) n +C n +C n +L +C n =2(8. 结束语
关于组合恒等式的证明方法还有很多, 例如, 微积分法, 二项式反演公式法, 几何法等等。本文介绍的主要是几种常见的方法, 而且以上的方法是以高中知识为基础, 也可以说是组合恒等式证明的初等方法。通过学习, 我们要学会具体问题具体分析和解决问题多样化的思想。顺便指出以上例题的解法不是唯一的, 本文也有提及。细心读者可以留意到, 各种方法之间也存在着一定的联系, 有时一道题可以同时使用几种方法, 思路很活, 有兴趣的读者可以研究一下。
[责任编辑:联 群]