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

证明组合恒等式的方法与技巧摘要本文是以高中二项式定理和排列组合知识为理论基础，对几个常见重要的例题作分析，总结组合恒等式常见的证明方法与技巧。对组合恒等式的证明方法本文主要讲了组合公式法，组合数性质法，二项式定理法，比较系数法，数列求和法，数学归纳法，组合分析法。关键字组合，组合数，组合恒等式，二项式定理ProofMethodsandSkillsofCombinatorialIdentityABSTRACTThisthesisprimarilyanalysessomecommonbutsignificantexamplesonthebasisofbinomialtheoremandpermutationandcombinationknowledgeofseniormiddleschooltosummarizethecommondemonstratingmethodsandtechniqueofcombinatorialidentity.Forcombinatorialidentity,hereitmainlyintroducesthemethodsofcombination formula,unitizedconstruction,mathematicalinduction，andsoon.KEYWORDScombination，combinatorialidentity，binomialtheorem前言组合恒等式在数学及其应用中占有不可忽视的地位,它是以高中排列组合、二项式定理为基础。组合恒等式的证明有一定的难度和特殊的技巧，且灵活性很强，要求学生掌握这部分知识，不但要学好有关的基础知识，基本概念和基本技能，而且还要适当诱导学生拓宽思路、发挥才智，培养解决问题方法多样化的思想。下面就以例题讲解的形式，把证明组合恒等式的常见方法与技巧一一列举出来。利用组合公式证明组合公式：Cm= n!nm(!n－m)！例1．求证：mCm=nCm－1n n－1分析：这是组合恒等式的一个基本性质，等式两边都只是一个简单的组合数。由此，我们只要把组合公式代入，经过化简比较，等号两边相等即可。证：・・・mCm= —nm(!n－m)！Cm-1=(nT)!=(n—D!m=mn-i(m—l)!(n—m)!(m—l)!(n—m)!mm!(n—m)!・•.mCm=nCm—1.n n—l技巧：利用组合公式证明时，只须将等式中的组合数用公式代入，经过化简比较两边即可，此方法思路清晰，对处理比较简单的等式证明很

有效，但运算量比较大，如遇到比较复杂一点的组合恒等式，此方法不可取。利用组合数性质证明组合数的基本性质：(1)C组合数的基本性质：(1)Cm=Cn－m

nn2)Cm=Cm+Cm－1

n＋1 nnTOC\o"1-5"\h\z(3)k-ck=n-Ck-1n n－1(4)Co+Cl+C2...+cn=2nnnn n(5)C0—Cl+C2—C3+...+(—l)nCn=0nnnn n例2：求证：C1+2-C2+3-C3...+n・cn=n・2nTnnn n分析：等式左边各项组合数的系数与该项组合数上标相等，且各项上标是递增加1的，由此我们联想到组合数的基本性质:k•Ck=n•Ck—1，n n—1利用它可以将各项组合数的系数化为相等，再利用性质Co+C1+C2...+Cn=2n可得到证明。nnn n证：由k•ck=n•Ck—1得n n—1Ci+2*C2+3*C3...+n*Cnnnn n—n*C0+n*C1+n*C2...+n*Cn—in—1 n—1 n—1 n—1=n (c0+C1+C2... +Cn—1)n—1n—1n—1 n—1=n•2n—1.例3．求证： C0+C1+C2+...+Ck—1 =Ck—1mm+1m+2 m+k—1 m+k分析：观察到，等式左边各项的组合数的上标和下标存在联系：上标+m=下标，而且各项下标是递增+1的。由此我们想到性质(2),将左边自第二项各项裂项相消，然后整理而得到求证。证：由性质(2)可得TOC\o"1-5"\h\zCi=Ci+Ci-1 (i^N)m+i+1 m+i m+i即Ci=Ci—Ci-1m+im+i+1 m+i令i=1,2,…，k—1,并将这k—1个等式相加，得C1+C2+...+Ck-1m+1m+2 m+k—1=Ci-Co+C2-Ci+...+Ck-i-Ck-2m+2m+1m+3m+2 m+km+k—1=—C0 +Ck-1m+1 m+kC0-+Ck-1m m+k・•・C0+C1+C2+...+Ck-1=Ck-i.mm+1m+2 m+k－1m+k技巧：例2和例3的证明分别利用性质(3)(5)、(2)此方法的技巧关键在于观察，分析各项组合数存在的联系，读者应在平时实践做题总结，把它们对号入座，什么样的联系用什么样的性质来解决。利用二项式定理证明我们都知道二项式定理：(a+b)=an+Cian-ib+C2an-2b2+...+Cn-iabn-i+bn，对于某些比较特殊的组

合恒等式可以用它来证明，下面以两个例子说明3．1．直接代值例4•求证：d)1+3・Cl+32・C2+...+3n-1・Cn-l+3n=22nn n n(2) 2n—2n-1*Cl+2n-2«C2+...+ (—1)n-12*Cn-1+(—1)n=ln n n分析：以上两题左边的各项组合数都是以Cian-ibi的形式出现，这n证：样自然会联想到二项式定理。证：(a+b)n=an+CIan-1b+C2an-2b2+...+Cn-labn-1+bnTOC\o"1-5"\h\zn n n(1)令a=1,b=3,代入①，得C+3)n—1+3*C1+32«C2+...+3n-1«Cn-l+3nnn n即，1+3*C1+32*C2+...+3n-1-Cn-1+3n—22nn n n⑵令a—2,b—-1,代入①，得(2—1)n—2n—2n—1・Cl+2n-2・C2+...+ (—))n-1«2*Cn-1+(—)nn n n即，2n—2n-1*C)+2n-2«C2+...+(—1)n-12*Cn-)+(—1)n—1.n n n技巧：此方法的关键在于代值,在一般情况,a,b值都不会很大,一般都是0,1,-1,2,-2,3,—3这些数,而且a,b值与恒等式右边也有必然的联系,如上题中1+3—22,2-1=1,在做题的时候要抓住这点。3.2．求导代值例5•求证： 21*C2+3*2*C汁...+(n—1)*Cn—n(n—1)*2n-2 (n=2)n n n分析：观察左边各项组合数的系数发现不可以直接运用二项式定理但系数也有一定的规律，系数都是i(i-1) i=2,3,・・・n我们又知道(xi)'='i(i-1)xi-2由此我们想到了求导的方法。证：对(l+x)n=C°+Clx+C2x2+...+Cnxn两边求二阶导数，得TOC\o"1-5"\h\zn n n nn*(n_1)•(]+x)—2=21・C2+3・2・C3・x+...+n(n_1)*Cn n n令x=1,得21*C2+3*2*C3+...+n(n—l)・Cn=n(n—1)*2n—2 (n=2)n n n技巧：此方法证明组合恒等式的步骤是，先对恒等式(a+x)n=£Cian-1xi 两边对x求一阶或二阶导数，然后适当选取x的mi=0值代入。利用多项式恒等条件证明(比较系数法)比较系数法主要利用二项式定理中两边多项式相等的充要条件为同次幂的系数相等加以证明。例6•求证:C0)2+(C1)2+(C2)2+...+(Cn)2=Cn(范德家"恒等

m m+1 m+2 n2n式)分析:本题若考虑上面所讲和方法来证明是比较困难的，注意到等式左边各项恰是二项展开式中各项二项式系数的平方，考虑二项展开式1+x)n=C0+nC1X+C2X2+...+Cnxn和(1+1)n=C0+C1-+C2丄+...+Cn丄这两个展nn n xnnx nx2 nxn开式乘积中常数项且好式是(Co)2+(C1)开式乘积中常数项且好式是(Co)2+(C1)2+(C2 )2+...+(Cn)2m m+1 m+2 n(1+x)n=Co+C1x+C2X2+...+Cnxnnnn n(1+丄)n=Co+C11+C2—+...+C1xnx2n nxn1•• (1+X)n(1+一)xCo+C1x+C2x2+...+Cnxn)nnn n(Co+C11+C2—+...+Cn—nnxnx2 nxn又有，(1+X)n(1—(1+X)2nxn比较两边的常数项，左边常数项为(Co)2+(C1)2+(C2)2+...+(Cn)2m m+1 m+2 n右边的常数项为Cn，根据二项展开式中对应项的唯一性，得2nC0)2+(C1)2+(C2)2+...+(Cn)2=Cnm m+1 m+2 n 2n技巧：此方法关键是适当地选择一个已知的恒等式，然后比较两边x同次幂的系数。当然，已知恒等式的选择不是唯一的，例5也可以选择已知恒等式(1+x)n(1+X)n=(1+X)2n,只须比较恒等式中两边含有xn的系数即可得证，证明留给读者。利用数列求和方法证明我们回到例2，除了上面得证明方法之外，还有没有其他得证明方法呢？我们观察，恒等式左边的各项组合数的系数为的等差数列，现在我们仿照求和公式i+2+...+n=恥一】)的证明可不可以证明例2呢？请看2下面证明TOC\o"1-5"\h\z证：设s=Ci+2C2+3C3..+n・Cn ①nnn n贝Us=n・Cn+(n1)Cni...+2C2+C1n n nn=nC+(n•1i)C+..•.n+22Cn(②n n n n①+②得2s=n・Co+n・C...+n・Cm+n・Cnn n n n=n(C0+C1...+Cn1+Cn)nn n n=n*2n・・s=n2n-1技巧：此方法的证明有一定的特殊性,分析等式中组合数系数的变化规律尤其重要,知识的迁移在此方法是一个很好的见证。利用数学归纳法证明我们都知道数学归纳法，在证明数列的题目中，我们就体会了数学归纳法的好处，只要按照数学归纳法的两个步骤进行就可以了。那么，组合恒等式的证明可不可以用数学归纳法来证明呢？看下面的一个例题例7.已知仁｝是任意的等差数列，且n^2,求证：nCoa—Cia+C2a—...+（—1）n-Cn-ia+（—1）nCna=0n1n2n3 nn nn+1分析：由于本题恒等式左边的各项组合数系数是一个不确定的等差数列，用上面的方法处理就比较困难，又因为等式含有数列，我们不妨用数学归纳法试试。证：i）当n=2时，因为a-a=a-a所以2132a-2a+a=0，故等式成立，123ii）假设，当n=k（k^2）时等式成立，即对任何等差数列｛a｝，n有，C0a－Cia+C2a－...+（－1）k-iCk-ia+（－1）kCka=0①

k1k2k3kkkk+1则当n=k+1时，利用组合数性质，有C0a－Cia+C2a－...+（－1）kCka +（－1）k+1C k＋iak+i1k+i2 k+13 k+1k+1 k＋i k+2=C0a－（Ci+C0）a+（C2+Ci）a－...k1kk2kk3+（－1）（kCk+Ck－i）a+（－1）k+1Ckakk k+1 kk+2=[C0a－Cia+C2a-...+（－1）kCka]k1k2k3k+k1－[C0a－Cia+C2a-...+（－1）k－iCk－ia+（－1）kCka]k2k3k4k+k1kk+2因为根据归纳假设，当n=k时，对任意等差数列a，a，.12..，a与a，a，a①式都成立，所以上式右端的两k+123k+2个方括号都等于零。于是我们证明了当n=k+1时等式也成立，根据（1）和（2）可知，等式对n^2的任何自然数都成立。技巧：用本方法证明的思路清晰，只须分两步进行即可，但归纳法的关键是由“假设n=k成立，推导到n=k+1也成立”这一步中间的变换过程比较复杂，在“无路可走”的情况之下，归纳法也是一个好的选择。利用组合分析方法证明所谓组合分析法就是通过构造具体的组合计数模型，采用了“算两次”的方法，再根据组合数的加法原理和乘法原理得到恒等式两边相等例8．证明：C0C1＋C1C2＋...＋Cn-iCn^Cn-1 (n^2)nnnn nn2n证：算右边，假设有2n个球，现要在2n个球中任取出(n-1)个，取法有Cn-1种，2n算左边，把2n个球分成两堆，每堆个n个，现要在2n个球在中取出(n—1)个，取法是，在第一堆取0个，第二堆取(n-1)个，或第一堆取1个，第二堆取(n—2)个，或…或第一堆取(n—1)个，第二堆取0.再根据加法原理总的取法有C0Cn—1＋C1Cn—2＋...＋Cn—1C0nnnn nn又因为C0Cn—l+CiCn—2+...+Cn—iC0=C0Cl+CiC2+...+Cn—iCnnnnn nnnnnn nn所以，左右两边都是在2n个球中