组合恒等式的证明方法与技巧

1、证明组合恒等式的方法与技巧组合恒等式在数学及其应用中占有不可忽视的地位 ，它是以高中排前言列组合、 二项式定理为基础.组合恒等式的证明有一定的难度和特殊的技巧，且灵活性很强，要求学生掌握这部分知识，不但要学好有关 的基础知识，基本概念和基本技能，而且还要适当诱导学生拓宽思路、发挥才智，培养解决问题方法多样 化的思想.下面就以例题讲解的形式，把证明组合恒等式的常见方法与技巧一一列举出来.1.利用组合公式证明组合公式:n!m!(n- m)例 1.求证：nCm=nCmV分析：这是组合恒等式的一个基本性质，等式两边都只是一个简单的组合数.由此，我们只要把组合公式 代入，经过简化比较，等号两边相等即可.

2、mm|n!证：. mC n =m!(nm) !m i_n|(n1) !_n|(n1) !|m_m|n!Cn 1 =1：一,： =二：一,： ；-=： (m1)!(n m) ! (m-1)!(n-m) ! |m m!(n-m) !，mCnm=nCnmT 11.技巧：利用组合公式证明时，只须将等式中的组合数用公式代入，经过化简比较即可，此方法思路清晰， 对处理比较简单的等式证明很有效，但运算量比较大，如遇到比较复杂一点的组合恒等式，此方法而不可 取.(2) 用组合数性质证明组合数的基本性质：(1) Cnm=Cn1 m(2)m m m m m-1Cn+ 1=C n +Cn(3) k C=n，Cnr

3、11012n on(4) Cn十Cn十Cn. 十Cn=20c12 c 3nc n (5) Cn Cn+ CnCn+ + ( 1) Cn=0例2 :求证： C： + 2C：+ 3c3+n|C：= n|2n 1分析：等式左边各项组合数的系数与该项组合数上标相等，且各项上标是递增加1的，由此我们联想到组合数的基本性质：k,C：=nC:11 ,利用它可以将各项组合数的系数化为相等，再利用性质C0 I 八1 I 八2I 八n nn+ Cn+ Cn+ Cn = 2 可付到证明.证：由 k Cnk=n，Cn：得C：+2C：+ 3c3+n|Cnn= nC；1+ nCni+n|C2i+n|C>101=n

4、(” 1+C：1+ C2 n-1.+ C11)n1坛/o 、-、r-o0 I11 I22kk-1kk - 1例3.求证： C m+ Cm + 1 + C m+2+ + Cm+kT= Cm + k分析：观察到，等式左边各项的组合数的上标和下标存在联系：上标+m=下标，而且各项下标是递增十1的.由此我们想到性质（2）,将左边自第二项各项裂项相消，然后整理而得到求证.证：由T质（2）可得Cm+i + 1 =Cm+i +Cm+i( iNO即 Cm+i=Cm+i+Cm:令i=1, 2,，k-1,并将这k 1个等式相加，得C 1 + C2 +J m+1 1 m + 2 1 .+ C3 k1= C=2 C&

5、gt; 1+ C：+3C1k k_ 1k k_ 2m+2十. 十 Cm+k Cm+k1=-Cm+Cm： 1k Cm+Cm+什 Cm+2+ + Cm 二1=c>1k.技巧：例2和例3的证明分别利用性质（3） （5）、（2）此方法的技巧关键在于观察，分析各项组合数存在的联系，读者应在平时实践做题总结，把它们对号入座，什么样的联系用什么样的性质来解决.3.利用二项式定理证明我们都知道二项式定理：(a+ b)n= an+ C；an1b+ C：an2b2+ Cnn-1abn-1+ bn,对于某些比较特殊的组合恒等式可以用它来证明，下面以两个例子说明3. 1.直接代值例4.求证：(1) 1 + 3/

6、+32储+ 31匕;1+3n=22n9、 nn nn_1 iK 1 I nn_2 H 2 II (、n-1Tcn-1 , (1、n d(2) 2 2Cn 十 2Cn 十十(一1)2|Cn 十(一 ) 一1分析：以上两题左边的各项组合数都是以C：aibi的形式出现，这样自然会联想到二项式定理.<n nc1n12n22n1 n1n:设(a+ b) = a + C0ab+ Cnab + + Cn ab + b d j 。au n nr /曰，/ic、n d 1Gh1io22 on_ 1An1 0n 口 口令 a= 1, b= 3,代入，得(1 + 3) = 1 + 3Cn+ 3 Cn + +3

7、 |Cn + 3 即,1 + 3C：+ 32|C：+ .+ 3nTCnnT+ 3n= 22n(2)令a=2, b= 1,代入，得2n-2n 1 C；+ 2n2C；+.(21)n= 2n 2L|C：+2n，C：+ ( 1)1|2匕；1+ (1)n 即,+ ( 1)nT2|C：T+ ( 1)n= 1 .技巧：此方法的关键在于代值，在一般情况，a, b值都不会很大，一般都是 0, 1,1,2, 2 , 33这些数，而且a, b值与恒等式右边也有必然的联系，如上题中1 + 3=22, 21=1,在做题的时候要抓住这点.3. 2 .求导代值例5.求证：21C；+32C：+. +n|(n1)c：= n |

8、n- 1)2n 2(n 皂 2)分析：观察左边各项组合数的系数发现不可以直接运用二项式定理，但系数也有一定的规律，系数都是i(i-1) i=2,3,n我们又知道(xi) ' ' =i(i-1)x i-2由此我们想到了求导的方法.证：对(1 + x)n=C：+Cnx+C：x2+. +Cnnxn两边求二阶导数，得n(n- 1)|(1+x)n 2= 2归：+ 3|2|C；|x+. +n (n-1) C： kn 2令x=1(n 皂 2)得 21C：+32C；+ . +n (n1)lC；=n (n1)12n2技巧：此方法证明组合恒等式的步骤是，先对恒等式（a+ x）n=Cman 1xi

9、两边对x求一阶或二阶i 0导数，然后适当选取 x的值代入.4.比较系数法比较系数法主要利用二项式定理中两边多项式相等的充要条件为同次哥的系数相等加以证明.例6.求证：（cm）2+（cm+1）2+（cm+2）2+. +（c：）2= c2n （范德蒙恒等式）分析：本题若考虑上面所讲和方法来证明是比较困难的，注意到等式左边各项恰是二项展开式中各项二项式系数的平方，考虑二项展开式（1 + x）n = c：+ c；x+cn2x2+. +cnnxn和11 C 1c 1(i+-)n= c：+ cn + c： -2+. + c： -n这两个展开式乘积中常数项且好式是 xxxxc 0 )2+ ( c 1 )2+

10、 ( c 2 )2+ ( c n )2(cm ) 十 (cm+ 1) 十 (cm+2) 十 十 (cn)证：.(1+x)n= c：+ cnx+c；x2+. +c：xn1 ., 1 c 1. 1(1H)=与+ g +。=+ . +。一nxx xxn1 x n , c 0 I c 12 2n n、(1 + x) (1) = ( cn+ cnx+ cnx + . + cnx )xc “ 1 c 11(c°+ cn-+c1+") x xx又有，（1 + x）n（1比较两边的常数项,1 n (1+x) 2n一) = nx xo_-、l ,、，乙1、/j-r*77"?、r/0

11、 2 I 11 2 I 22 2 n n 2左边吊数项为(J ) + ( 7 + 1)+ ( 7+2)+ . +(以)右边的常数项为c21n根据二项展开式 中对应项的唯一性得(cm)2+(cm+1)2+(cm+2)2+.+ ©)2= cn2nx同次哥的系数.当然，已知恒等式的x）n（1x）2n ,只须比较恒等式中两技巧：此方法关键是适当地选择一个已知的恒等式，然后比较两边选择不是唯一的，例5也可以选择已知恒等式（1+x）n（1边含有xn的系数即可得证，证明留给读者.5.利用数列求和方法证明回到例2,除了利用组合数的性质，我们还可以有其他方法.观察，恒等式左边的各项组合数的系数为等差数

12、列，现在我们仿照求和公式12 n91)的证明来证明例22证：设 s=C；+2Cn +3c3 +n|C：则s=n C：+(n-1)C| n-1+2Cn+C=n C0+(n-1)C| ； +2Cn2 + C，+得2s=n Cn+nC； +nCn-1 + nCn=n(C ；+C；+ Cn-1 + C；)=；2n5 n|2n 1技巧：此方法的证明有一定的特殊性，分析等式中组合数系数的变化规律尤其重要，知识的迁移在此方法是一个很好的见证.6 .利用数学归纳法证明我们都知道数学归纳法，在证明数列的题目中，我们就体会了数学归纳法的好处，只要按照数学归纳法的两个步骤进行就可以了.那么，组合恒等式的证明可不可以

13、用数学归纳法来证明呢看下面的一个例题例7.已知an是任意的等差数列，且 n皂2,求证：C：a1 C；a2+ C|2a3+ ( 1) n-1Cn-1an+(1”照明+0分析：由于本题恒等式左边的各项组合数系数是一个不确定的等差数列，用上面的方法处理就比较困难，又因为等式含有数列，我们不妨用数学归纳法试试.证：i)当n=2时，因为a2aa3a2所以a2a2a30 ,故等式成立，ii) 假设，当n=k (k叁2)时等式成立，即对任何等差数列an,有，CMC：a2+Ci2a3.+ ( 1)k-1Ck-1ak+ ( 1)kCk ak+1 = 0 .+ ( 1)kCik+ 1ak+1+(-1)k+1CkL

14、1ak+2则当n=k+1时，利用组合数性质，有0 1 2Ck + 1a1Ck+1a2十 Ck + 1a3Ck0a1（Ck1 Ck0）a2（ Ck2 Ck1）a31）（k CkkCkk1） ak1+（ 1）k 1Ckkak+2Ck0a1 Ck1a2 Ck2a3-.+（ 1）kCkkak1Ck0a2 Ck1a3Ck2a4-.+（1）k1Ckk1ak1+（ 1）kCkkak2因为根据归纳假设，当n=k时，对任意等差数列a1, a2，,ak+1与a2, a3, ak+2式都成立,所以上式右端的两个方括号都等于零.于是我们证明了当n=k + 1时等式也成立，根据（1）和（2）可知，等式对n皂2的任何自然

15、数都成立.技巧：用本方法证明的思路清晰，只须分两步进行即可，但归纳法的关键是由“假设n = k成立，推导到n= k+1也成立”这一步中间的变换过程比较复杂，在“无路可走”的情况之下，归纳法也是一个好的选择.7. 利用组合分析方法证明所谓组合分析法就是通过构造具体的组合计数模型，采用了“算两次”的方法，再根据组合数的加法原理和乘法原理得到恒等式两边相等0 11 2n1 nn1例 8 . uE 明：CnCn+ CnCn+ +Cn Cn = C2n （n=2）证明：算右边，假设有2n 个球，现要在 2n 个球中任取出（ n 1 个，取法有C2nn1 种，算左边，把2n 个球分成两堆，每堆个n 个，现

16、要 在 2n 个球在中取出（ n 1 ）个，取法是，在第一堆取。个，第二堆取（n-1）个，或第一堆取1个，第二堆 取（n2）个，或或第一堆取（n-1）个，第二堆取 0. 再根据加法原理总的取法有CnC n CnCn . Cn C n+n n0 n 11 n 2n 1 00112乂内为CnCn 十CnCn 十 十Cn Cn =CnCn十CnCn十所以，左右两边都是在 2n 个球中取出（ n 1 ）个球，因此有，（n皂 2）0 11 2n 1 n n 1CnCn 十 C nC n 十十 Cn Cn C 2n技巧：用组合分析法证明组合恒等式的步骤是：选指出式子的一边是某个问题的解，然后应用加法原理和

17、乘法原理等去证明式子的另一边也是该组合问题的解用此方法也可以证明例6 ，证明过程非常简洁8 概率法证排列组合基本理论是古典概型计算的基石 能否用古典概型来解决某些排列组合问题我们来看下面的例子例 9 证明组合数加法题推公式：kCn1kCnk1 k2Cn1 Cn1.分析：把特征等式经过适当变形，使之右端变为1，而左端为若干项之和，根据左端和式中各项的特点，构造以概率模型，并找到样本空间的一个特殊分化，使之相应概率等于左端和式的各项，从而得证.证明：我们将公示变形为kCnCn 1k 1 k 2Cn 1 Cnik-Cni Cni1.卜面利用超几何分布概率公式构建摸球模型来证明：设袋中有n 1只球，其

18、中有1只黑球，1只白球，现随机地抽取 k只球1 k n 1 .设事件A： “抽取的k只球中含有黑球” ，B： “抽取的k只球中含有白球”，则0 kC1CnC由全概率公式得AB P B P A B =1 k 11 k 2CCn ?C1Cn1k k 1Cn 1Cn0 k 1 kCCn?CCnk kCn 1 Cnk 2=C n 1k-Cn 1k 1Cn 1 kCn 11,立即得证该公式技巧：利用概率对立事件发生的概率和为1,或是在某种情况下必然事件的概率也为1.可以与实际相结合,容易理解.9几何法例10 证明 C0 Cn Cn 2n分析：主要是利用组合的几何意义来证明.无重组合 n I的几何意义Cn

19、 1表示平面坐标上的（0,0）点到整点（n,m）（这里n,m都是整数）的递增路径的总和.一条从点（0,0）到点（n,m）的递增路径是指一个有长度为1的端点为整点的线段首尾连接所组成的折线，并且每一条线段的后一个端点的坐标或者在x上或者在y上，比前一个端点增加一的单位长，水平走一步为x,垂直走一步为y,图1中的递增路径可表示为：x,y,x,x,y,y,x,x,y,y证明：由图2可知等式的左边，C：表示从（0Q）至（ °， 点的增路径，C1n表示从（0Q）到（1，n1）点的增路径数，Cn表不从（0Q）到（n1,1 ）点的的增路径数， Cn 表示从（0,0）到（n,0 ）点的的增路径数1,

20、而这所有的地 增路径之和就是从（0,0）点到斜边上的整点的递增路径. 另一方面，从（0,0 ）点到斜边上任何一整点的递增路径是 n步步长，每一步是 x或者y,有两种选择，由乘法法则，n步的不同方法的总数为 2 n ,所以等式成立.10用哥级数法n 1我们知道，1-X可展成如下哥级数:CnkXk X 1k 0现在我们用次展开式证明下列等式例11证明c：nCn1nCn证明：因为 1-X左边应为:nCn0k kXXi0右边应为:nCn0比较两边X的系数可知,原等式成立.技巧：对组合求和,当组合下标变动时，常用骞级数方法.11微积分法例11 求证：k 11C分析：利用微分与积分的相互转化是问题得以解决

21、,求导后再积回去,不改变原等式的性质.证明：令k kCnXkCn上式两边同时求积分得k k nXkCn1 =111 1所以从而上述例kCn12递推公式法12是否还可以用递推公式的方法解决，我们来看一下证明：令fnkCnn 1,2,3,f12时,fn =-1kk-1kCn1kCnn1 _1 kkCn所以fnfnfn 1fn1首先介绍生成函数相关定义和定理.定义C 旦.an定义1= fnn个数列，做形式骞级数称f x为数列an的生成函数.对任何实数r和整数k kCn=fn1 =fn13kCnkCrk!f1生成函数法2x a0axa?xnanx定理1设数列an , bn的生成函数为 A x , B

22、xbnnaii 0定理2设m是一个有理数，a R,有1例13/ 3 n 1n n 1N,有Cn2(n 2)(n 3)证明：设数列设bnaxkCm k 02 kk Cn k的生成函数 A(x),即A(x)=2 k kk Cnkxi1ai,先求A(x),由-n1 xk kCnkxk 1对上式两边求导得:k k 1kCnkxk 1两边同乘x得：nk k kCnkx对上式两边求导得:2 k k 1 kCnkx两边同乘x得:k Cnkxk=A(x)由定理B(x)1A(x)1 x由式得 12的系数为n 2C2n1» n 1.一中x 的系数为nC2n.因此1B(x)展开式中xn的系数为bnn 2C

23、2n 1n 1C2n1n nn 1 =3_C2n 1因此相关定理及定义/ 3 n 11 C2n114牛顿公式法定义 1 设 f n n 0 为任一数列，令 f n f n 1 f nn 0,1,2, k f n = k 1 f n 1 - k 1 f n n 0,1,2, 这里成为差分算子.定义 2 设 f n 为任一数列，令 n0Ef n f n 1n 0,1,2,Ekf n Ek 1 f n 1 f n k n 0,1,2, 这里称 E 移位算子定义 3 设 f n n 0 为任一数列，令If n f nn 0,1,2,I k f n I k 1 f n f n n 0,1,2, 这里称

24、I 为恒等因子定理 1 设 f n n 0 为任一数列， a, bR ，则 af n bg n约定： 0 E0 I0 I定理 2 （牛顿公式） nEn= JI）n 小 j j0nnjE I n 1C nj E jj0例 14f l =a0a1lamlm(其中 am 0, aiR , l N),有k0n k k 0， m n1 f l=C n m! am , m n证明：由牛顿公式nj1nj1 flCnjnj1nj，CnjEjf l j nf实际上是证明f =0, m nm!am, m对 f 用数学归纳法证明当 fn时，有 n f l =0当 f 1 时，令 f l al b ( a 0) f l f l 1 f l a l 1 b al b a ，2fl a a 0假设 f m 时命题成立，m 且 m n 时，令 f l a 0a1 laml f la0a1 l 1am l 1 m a0a1lam l显然 （ f l ）m 1 n 1，由归纳法设 n f l =An