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

证明组合恒等式的方法与技巧前言组合恒等式在数学及其应用中占有不可忽视的地位,它是以高中排前言列组合、二项式定理为基础．组合恒等式的证明有一定的难度和特殊的技巧，且灵活性很强，要求学生掌握这部分知识，不但要学好有关的基础知识，基本概念和基本技能，而且还要适当诱导学生拓宽思路、发挥才智，培养解决问题方法多样化的思想．下面就以例题讲解的形式，把证明组合恒等式的常见方法与技巧一一列举出来．1.利用组合公式证明组合公式：mnC=n!!nmm（－）！例1．求证：mmnC=n11mnC－－分析：这是组合恒等式的一个基本性质，等式两边都只是一个简单的组合数．由此，我们只要把组合公式代入，经过简化比较，等号两边相等即可．证：∵mmnC=mn!!nmm（－）！11mnC－－=nn!1!nmm（－1）（－）（－）！=nn!m1!nmmm（－1）（－）（－）！=mn!!nmm（－）！∴mmnC=n－－11mnC.技巧：利用组合公式证明时，只须将等式中的组合数用公式代入，经过化简比较即可，此方法思路清晰，对处理比较简单的等式证明很有效，但运算量比较大，如遇到比较复杂一点的组合恒等式，此方法而不可取．2.利用组合数性质证明组合数的基本性质：（1）mnC=nmnC－（2）1mnC＋=mnC+1mnC－（3）kknC=nk11nC－－（4）＋＋...＋＝012n2nnnnnCCCC－＋－＋...＋（－1）＝00123nnnnnnnCCCCC（5）例2：求证：－＋＋3...＋n＝n123n122nnnnnCCCC分析：等式左边各项组合数的系数与该项组合数上标相等，且各项上标是递增加1的,由此我们联想到组合数的基本性质：kknC=nk11nC－－，利用它可以将各项组合数的系数化为相等，再利用性质＋＋...＋＝012n2nnnnnCCCC可得到证明．证：由kknC=nk11nC－－得123n2nnnnCCCC＋＋3...＋n＝012n11111nnnnnnnCCCC－－－－－＋＋...＋n＝n（012n11111nnnnCCCC－－－－－＋＋...＋）＝nn12－.例3．求证：012k1k1mm1m2mk1mkCCCCC－－＋＋＋－＋＋＋＋...＋＝分析：观察到，等式左边各项的组合数的上标和下标存在联系：上标＋m＝下标，而且各项下标是递增＋1的．由此我们想到性质（2），将左边自第二项各项裂项相消，然后整理而得到求证．证：由性质（2）可得imi1C＋＋=imiC＋+i1miC－＋（i∈N）即imiC＋＝imi1C＋＋－i1miC－＋令i＝1，2，…，k－1，并将这k－1个等式相加，得12k1m1m2mk1CCC－＋＋＋－＋＋...＋＝1021k1k2m2m1mmmkmkCCCCCC－－＋＋＋3＋2＋＋－1－＋－＋...＋－＝－0m1C＋＋k1mkC－＋＝－0mC＋k1mkC－＋∴012k1k1mm1m2mk1mkCCCCC－－＋＋＋－＋＋＋＋...＋＝.技巧：例2和例3的证明分别利用性质（3）（5）、（2）此方法的技巧关键在于观察，分析各项组合数存在的联系，读者应在平时实践做题总结，把它们对号入座，什么样的联系用什么样的性质来解决．3.利用二项式定理证明我们都知道二项式定理：nn1n2n2n1nnnnnabaabababbCCC－1－2－－1（＋）＝＋＋＋...＋＋，对于某些比较特殊的组合恒等式可以用它来证明，下面以两个例子说明3．1．直接代值例4．求证：（1）－1－1＋3＋3＋...＋3＋3＝122nn1n2nnnn2CCC（2）－－－1－－＋＋...＋（－1）＋（－1）＝nn11n22nn1nnnn22221CCC分析：以上两题左边的各项组合数都是以iniinabC－的形式出现，这样自然会联想到二项式定理．证：设nn1n2n2n1nnnnnabaabababbCCC－1－2－－1（＋）＝＋＋＋...＋＋①⑴令a＝1，b＝3，代入①，得－1－＋）＝1＋3＋3＋...＋3＋3n122nn1nnnn(13CCC即，－1－1＋3＋3＋...＋3＋3＝122nn1n2nnnn2CCC(2)令a＝2，b＝－1，代入①，得nnn11n-22n1n1nnnn121CCC－－－（2－1）＝2－2＋2＋...＋（－）＋（－）即，－－－1－－＋＋...＋（－1）＋（－1）＝nn11n22nn1nnnn22221CCC.技巧：此方法的关键在于代值，在一般情况，a，b值都不会很大，一般都是0，1，－1，2，－2,3，—3这些数，而且a，b值与恒等式右边也有必然的联系，如上题中1＋3＝22，2－1=1,在做题的时候要抓住这点．3.2．求导代值例5．求证：－＋3＋...＋（－1）＝（－1）23nn2nnn212nnnn2CCC（n≧2）分析：观察左边各项组合数的系数发现不可以直接运用二项式定理，但系数也有一定的规律，系数都是i(i-1)i=2,3,…n我们又知道（xi）’’=i(i-1)xi-2由此我们想到了求导的方法．证：对n0122nnnnnnxxxxCCCC（1＋）＝＋＋＋...＋两边求二阶导数，得n223nn2nnnnn1x212xnnxCCC－－（－1）（＋）＝＋3＋...＋（－1）令x=1得－＋3＋...＋（－1）＝（－1）23nn2nnn212nnnn2CCC（n≧2）技巧：此方法证明组合恒等式的步骤是，先对恒等式nax（＋）＝i1m0nniiCax两边对x求一阶或二阶导数，然后适当选取x的值代入．4.比较系数法比较系数法主要利用二项式定理中两边多项式相等的充要条件为同次幂的系数相等加以证明．例6．求证：2222＋＋)＋()＋()＋...＋()＝012mm1m22(nnnnCCCCC（范德蒙恒等式）分析：本题若考虑上面所讲和方法来证明是比较困难的，注意到等式左边各项恰是二项展开式中各项二项式系数的平方，考虑二项展开式（1＋）nx=＋0nC＋＋...＋122nnnnnxxxCCC和（1＋）＝＋＋＋...＋n012nnnnn2n1111xxxxCCCC这两个展开式乘积中常数项且好式是2222＋＋)＋()＋()＋...＋()012mm1m2(nnCCCC证：∵n0122nnnnnnxxxxCCCC（1＋）＝＋＋＋...＋（1＋）＝＋＋＋...＋n012nnnnn2n1111xxxxCCCC∴n1x(1)nx（1＋）=（＋＋＋...＋0122nnnnnnxxxCCCC）（＋＋＋...＋012nnnnn2n111xxxCCCC）又有，n1x(1)nx（1＋）＝2nn(1+x)x比较两边的常数项，左边常数项为2222＋＋)＋()＋()＋...＋()012mm1m2(nnCCCC右边的常数项为2nnC，根据二项展开式中对应项的唯一性得2222＋＋)＋()＋()＋...＋()＝012mm1m22(nnnnCCCCC技巧：此方法关键是适当地选择一个已知的恒等式，然后比较两边x同次幂的系数．当然，已知恒等式的选择不是唯一的，例5也可以选择已知恒等式n2x(1)(1)nnxx（1＋），只须比较恒等式中两边含有nx的系数即可得证，证明留给读者．5.利用数列求和方法证明回到例2，除了利用组合数的性质，我们还可以有其他方法．观察，恒等式左边的各项组合数的系数为等差数列，现在我们仿照求和公式(1)12...2nnn的证明来证明例2证：设123nnnnns=C2C3C...nC＋＋＋①则nn-121nnnns=nCn-1)C...2CC＋(＋＋01n-2n-1nnnn=nCn-1)C...2CC＋(＋＋②①＋②得01n-1nnnnn2s=nCC...nCCn＋＋＋n01n-1nnnnn=n(CC...CC)＋＋＋=n2n∴12nsn技巧：此方法的证明有一定的特殊性,分析等式中组合数系数的变化规律尤其重要,知识的迁移在此方法是一个很好的见证．6.利用数学归纳法证明我们都知道数学归纳法，在证明数列的题目中，我们就体会了数学归纳法的好处，只要按照数学归纳法的两个步骤进行就可以了．那么，组合恒等式的证明可不可以用数学归纳法来证明呢？看下面的一个例题例7．已知{na}是任意的等差数列，且n≧2，求证：123nn+1a－a＋a－...＋（－1）a+（－1）a＝0012n-1n-1nnnnnnnCCCCC分析：由于本题恒等式左边的各项组合数系数是一个不确定的等差数列，用上面的方法处理就比较困难，又因为等式含有数列，我们不妨用数学归纳法试试．证：i)当n＝2时，因为2132aaaa所以12320aaa，故等式成立，ii)假设，当n＝k（k≧2）时等式成立，即对任何等差数列{na}，有，123kk+1a－a＋a－...＋（－1）a+（－1）a＝0012k-1k-1kkkkkkkCCCCC①则当n＝k＋1时，利用组合数性质，有＋1＋1＋2＋13＋1k＋1k+2a－a＋a－...＋（－1）a+（－1）a012kkkk＋111＋1kkkkkCCCCC123－＋1k＋1k+2＝a－（＋）a＋（＋）a－...＋（－1）（＋）a+（－1）a01021kkk1kkkkkkkkkkCCCCCCCC123k＋1－－234k＋1k＋2＝a－a＋a-...+（1）a－a－a＋a-...+（1）a+（1）a012kk012k1k1kk[－][－－]kkkkkkkkkCCCCCCCCC因为根据归纳假设，当n＝k时，对任意等差数列12k123k2aaaaaa＋＋，，...，与，，①式都成立，所以上式右端的两个方括号都等于零．于是我们证明了当n＝k＋1时等式也成立，根据（1）和（2）可知，等式对n≧2的任何自然数都成立．技巧：用本方法证明的思路清晰，只须分两步进行即可，但归纳法的关键是由“假设n＝k成立，推导到n＝k＋1也成立”这一步中间的变换过程比较复杂，在“无路可走”的情况之下，归纳法也是一个好的选择．7.利用组合分析方法证明所谓组合分析法就是通过构造具体的组合计数模型，采用了“算两次”的方法，再根据组合数的加法原理和乘法原理得到恒等式两边相等．例8．证明：－－＋＋...＋＝0112n1nn12nnnnnnnCCCCCCC（n≧2）证明：算右边，假设有2n个球，现要在2n个球中任取出（n－1个，取法有－n12nC种，算左边，把2n个球分成两堆，每堆个n个，现要在2n个球在中取出（n－1）个，取法是，在第一堆取0个，第二堆取（n－1）个，或第一堆取1个，第二堆取（n－2）个，或…或第一堆取（n－1）个，第二堆取0.再根据加法原理总的取法有－－－＋＋...＋0n11n2n10nnnnnnCCCCCC又因为－－－＋＋...＋0n11n2n10nnnnnnCCCCCC＝－＋＋...＋0112n1nnnnnnnCCCCCC所以，左右两边都是在2n个球中取出（n－1）个球，因此有，－－＋＋...＋＝0112n1nn12nnnnnnnCCCCCCC（n≧2）技巧：用组合分析法证明组合恒等式的步骤是：选指出式子的一边是某个问题的解，然后应用加法原理和乘法原理等去证明式子的另一边也是该组合问题的解．用此方法也可以证明例6，证明过程非常简洁．8概率法证排列组合基本理论是古典概型计算的基石．能否用古典概型来解决某些排列组合问题？我们来看下面的例子例9证明组合数加法题推公式：.21111CCCCknknknkn分析：把特征等式经过适当变形，使之右端变为1，而左端为若干项之和，根据左端和式中各项的特点，构造以概率模型，并找到样本空间的一个特殊分化，使之相应概率等于左端和式的各项，从而得证．证明：我们将公示变形为.11211111CCCCCCknknknknknkn下面利用超几何分布概率公式构建摸球模型来证明：设袋中有1n只球，其中有1只黑球，1只白球，现随机地抽取k只球11nk.设事件A：“抽取的k只球中含有黑球”，B：“抽取的k只球中含有白球”，则CCCknknAP101由全概率公式得BAPBPBAPBPAP=CCCCCCCCCCCCk