證明組合恒等式的方法與技巧

證明組合恒等式的方法與技巧摘要本文是以高中二項(xiàng)式定理和排列組合知識(shí)為理論基礎(chǔ)，對幾個(gè)常見重要的例題作分析，總結(jié)組合恒等式常見的證明方法與技巧。對組合恒等式的證明方法本文主要講了組合公式法，組合數(shù)性質(zhì)法，二項(xiàng)式定理法，比較系數(shù)法，數(shù)列求和法，數(shù)學(xué)歸納法，組合分析法。關(guān)鍵字組合，組合數(shù)，組合恒等式，二項(xiàng)式定理ProofMethodsandSkillsofCombinatorialIdentityABSTRACTThisthesisprimarilyanalysessomecommonbutsignificantexamplesonthebasisofbinomialtheoremandpermutationandcombinationknowledgeofseniormiddleschooltosummarizethecommondemonstratingmethodsandtechniqueofcombinatorialidentity.Forcombinatorialidentity,hereitmainlyintroducesthemethodsofcombination formula,unitizedconstruction,mathematicalinduction，andsoon.KEYWORDScombination，combinatorialidentity，binomialtheorem前言組合恒等式在數(shù)學(xué)及其應(yīng)用中占有不可忽視的地位,它是以高中排列組合、二項(xiàng)式定理為基礎(chǔ)。組合恒等式的證明有一定的難度和特殊的技巧，且靈活性很強(qiáng)，要求學(xué)生掌握這部分知識(shí)，不但要學(xué)好有關(guān)的基礎(chǔ)知識(shí)，基本概念和基本技能，而且還要適當(dāng)誘導(dǎo)學(xué)生拓寬思路、發(fā)揮才智，培養(yǎng)解決問題方法多樣化的思想。下面就以例題講解的形式，把證明組合恒等式的常見方法與技巧一一列舉出來。利用組合公式證明組合公式：Cm= n!nm(!n－m)！例1．求證：mCm=nCm－1n n－1分析：這是組合恒等式的一個(gè)基本性質(zhì)，等式兩邊都只是一個(gè)簡單的組合數(shù)。由此，我們只要把組合公式代入，經(jīng)過化簡比較，等號(hào)兩邊相等即可。證：???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技巧：利用組合公式證明時(shí)，只須將等式中的組合數(shù)用公式代入，經(jīng)過化簡比較兩邊即可，此方法思路清晰，對處理比較簡單的等式證明很

有效，但運(yùn)算量比較大，如遇到比較復(fù)雜一點(diǎn)的組合恒等式，此方法不可取。利用組合數(shù)性質(zhì)證明組合數(shù)的基本性質(zhì)：(1)C組合數(shù)的基本性質(zhì)：(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分析：等式左邊各項(xiàng)組合數(shù)的系數(shù)與該項(xiàng)組合數(shù)上標(biāo)相等，且各項(xiàng)上標(biāo)是遞增加1的，由此我們聯(lián)想到組合數(shù)的基本性質(zhì):k?Ck=n?Ck—1，n n—1利用它可以將各項(xiàng)組合數(shù)的系數(shù)化為相等，再利用性質(zhì)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分析：觀察到，等式左邊各項(xiàng)的組合數(shù)的上標(biāo)和下標(biāo)存在聯(lián)系：上標(biāo)+m=下標(biāo)，而且各項(xiàng)下標(biāo)是遞增+1的。由此我們想到性質(zhì)(2),將左邊自第二項(xiàng)各項(xiàng)裂項(xiàng)相消，然后整理而得到求證。證：由性質(zhì)(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個(gè)等式相加，得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的證明分別利用性質(zhì)(3)(5)、(2)此方法的技巧關(guān)鍵在于觀察，分析各項(xiàng)組合數(shù)存在的聯(lián)系，讀者應(yīng)在平時(shí)實(shí)踐做題總結(jié)，把它們對號(hào)入座，什么樣的聯(lián)系用什么樣的性質(zhì)來解決。利用二項(xiàng)式定理證明我們都知道二項(xiàng)式定理：(a+b)=an+Cian-ib+C2an-2b2+...+Cn-iabn-i+bn，對于某些比較特殊的組

合恒等式可以用它來證明，下面以兩個(gè)例子說明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分析：以上兩題左邊的各項(xiàng)組合數(shù)都是以Cian-ibi的形式出現(xiàn)，這n證：樣自然會(huì)聯(lián)想到二項(xiàng)式定理。證：(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技巧：此方法的關(guān)鍵在于代值,在一般情況,a,b值都不會(huì)很大,一般都是0,1,-1,2,-2,3,—3這些數(shù),而且a,b值與恒等式右邊也有必然的聯(lián)系,如上題中1+3—22,2-1=1,在做題的時(shí)候要抓住這點(diǎn)。3.2．求導(dǎo)代值例5?求證： 21*C2+3*2*C汁...+(n—1)*Cn—n(n—1)*2n-2 (n=2)n n n分析：觀察左邊各項(xiàng)組合數(shù)的系數(shù)發(fā)現(xiàn)不可以直接運(yùn)用二項(xiàng)式定理但系數(shù)也有一定的規(guī)律，系數(shù)都是i(i-1) i=2,3,???n我們又知道(xi)'='i(i-1)xi-2由此我們想到了求導(dǎo)的方法。證：對(l+x)n=C°+Clx+C2x2+...+Cnxn兩邊求二階導(dǎo)數(shù)，得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求一階或二階導(dǎo)數(shù)，然后適當(dāng)選取x的mi=0值代入。利用多項(xiàng)式恒等條件證明(比較系數(shù)法)比較系數(shù)法主要利用二項(xiàng)式定理中兩邊多項(xiàng)式相等的充要條件為同次冪的系數(shù)相等加以證明。例6?求證:C0)2+(C1)2+(C2)2+...+(Cn)2=Cn(范德家"恒等

m m+1 m+2 n2n式)分析:本題若考慮上面所講和方法來證明是比較困難的，注意到等式左邊各項(xiàng)恰是二項(xiàng)展開式中各項(xiàng)二項(xiàng)式系數(shù)的平方，考慮二項(xiàng)展開式1+x)n=C0+nC1X+C2X2+...+Cnxn和(1+1)n=C0+C1-+C2丄+...+Cn丄這兩個(gè)展nn n xnnx nx2 nxn開式乘積中常數(shù)項(xiàng)且好式是(Co)2+(C1)開式乘積中常數(shù)項(xiàng)且好式是(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比較兩邊的常數(shù)項(xiàng)，左邊常數(shù)項(xiàng)為(Co)2+(C1)2+(C2)2+...+(Cn)2m m+1 m+2 n右邊的常數(shù)項(xiàng)為Cn，根據(jù)二項(xiàng)展開式中對應(yīng)項(xiàng)的唯一性，得2nC0)2+(C1)2+(C2)2+...+(Cn)2=Cnm m+1 m+2 n 2n技巧：此方法關(guān)鍵是適當(dāng)?shù)剡x擇一個(gè)已知的恒等式，然后比較兩邊x同次冪的系數(shù)。當(dāng)然，已知恒等式的選擇不是唯一的，例5也可以選擇已知恒等式(1+x)n(1+X)n=(1+X)2n,只須比較恒等式中兩邊含有xn的系數(shù)即可得證，證明留給讀者。利用數(shù)列求和方法證明我們回到例2，除了上面得證明方法之外，還有沒有其他得證明方法呢？我們觀察，恒等式左邊的各項(xiàng)組合數(shù)的系數(shù)為的等差數(shù)列，現(xiàn)在我們仿照求和公式i+2+...+n=恥一】)的證明可不可以證明例2呢？請看2下面證明TOC\o"1-5"\h\z證：設(shè)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技巧：此方法的證明有一定的特殊性,分析等式中組合數(shù)系數(shù)的變化規(guī)律尤其重要,知識(shí)的遷移在此方法是一個(gè)很好的見證。利用數(shù)學(xué)歸納法證明我們都知道數(shù)學(xué)歸納法，在證明數(shù)列的題目中，我們就體會(huì)了數(shù)學(xué)歸納法的好處，只要按照數(shù)學(xué)歸納法的兩個(gè)步驟進(jìn)行就可以了。那么，組合恒等式的證明可不可以用數(shù)學(xué)歸納法來證明呢？看下面的一個(gè)例題例7.已知仁｝是任意的等差數(shù)列，且n^2,求證：nCoa—Cia+C2a—...+（—1）n-Cn-ia+（—1）nCna=0n1n2n3 nn nn+1分析：由于本題恒等式左邊的各項(xiàng)組合數(shù)系數(shù)是一個(gè)不確定的等差數(shù)列，用上面的方法處理就比較困難，又因?yàn)榈仁胶袛?shù)列，我們不妨用數(shù)學(xué)歸納法試試。證：i）當(dāng)n=2時(shí)，因?yàn)閍-a=a-a所以2132a-2a+a=0，故等式成立，123ii）假設(shè)，當(dāng)n=k（k^2）時(shí)等式成立，即對任何等差數(shù)列｛a｝，n有，C0a－Cia+C2a－...+（－1）k-iCk-ia+（－1）kCka=0①

k1k2k3kkkk+1則當(dāng)n=k+1時(shí)，利用組合數(shù)性質(zhì)，有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因?yàn)楦鶕?jù)歸納假設(shè)，當(dāng)n=k時(shí)，對任意等差數(shù)列a，a，.12..，a與a，a，a①式都成立，所以上式右端的兩k+123k+2個(gè)方括號(hào)都等于零。于是我們證明了當(dāng)n=k+1時(shí)等式也成立，根據(jù)（1）和（2）可知，等式對n^2的任何自然數(shù)都成立。技巧：用本方法證明的思路清晰，只須分兩步進(jìn)行即可，但歸納法的關(guān)鍵是由“假設(shè)n=k成立，推導(dǎo)到n=k+1也成立”這一步中間的變換過程比較復(fù)雜，在“無路可走”的情況之下，歸納法也是一個(gè)好的選擇。利用組合分析方法證明所謂組合分析法就是通過構(gòu)造具體的組合計(jì)數(shù)模型，采用了“算兩次”的方法，再根據(jù)組合數(shù)的加法原理和乘法原理得到恒等式兩邊相等例8．證明：C0C1＋C1C2＋...＋Cn-iCn^Cn-1 (n^2)nnnn nn2n證：算右邊，假設(shè)有2n個(gè)球，現(xiàn)要在2n個(gè)球中任取出(n-1)個(gè)，取法有Cn-1種，2n算左邊，把2n個(gè)球分成兩堆，每堆個(gè)n個(gè)，現(xiàn)要在2n個(gè)球在中取出(n—1)個(gè)，取法是，在第一堆取0個(gè)，第二堆取(n-1)個(gè)，或第一堆取1個(gè)，第二堆取(n—2)個(gè)，或…或第一堆取(n—1)個(gè)，第二堆取0.再根據(jù)加法原理總的取法有C0Cn—1＋C1Cn—2＋...＋Cn—1C0nnnn nn又因?yàn)镃0Cn—l+CiCn—2+...+Cn—iC0=C0Cl+CiC2+...+Cn—iCnnnnn nnnnnn nn所以，左右兩邊都是在2n個(gè)球中