组合恒等式的证明方法与技巧(共14页)

证明组合恒等式的方法与技巧前言组合恒等式在数学及其应用中占有不可忽视的地位,它是以高中排前言列组合、二项式定理为基础组合恒等式的证明有一定的难度和特殊的技巧，且灵活性很强，要求学生掌握这部分知识，不但要学好有关的基础知识，基本概念和基本技能，而且还要适当诱导学生拓宽思路、发挥才智，培养解决问题方法多样化的思想下面就以例题讲解的形式，把证明组合恒等式的常见方法与技巧一一列举出来1. 利用组合公式证明组合公式：=例1 求证：m=n分析：这是组合恒等式的一个基本性质，等式两边都只是一个简单的组合数由此，我们只要把组合公式代入，经过简化比较，等号两边相等即可证： m= = m=n.技巧：利用组合公式证明时，只须将等式中的组合数用公式代入，经过化简比较即可，此方法思路清晰，对处理比较简单的等式证明很有效，但运算量比较大，如遇到比较复杂一点的组合恒等式，此方法而不可取2. 利用组合数性质证明组合数的基本性质：（1）= （2）=+ （3）k =n （4） 例2：求证：分析：等式左边各项组合数的系数与该项组合数上标相等，且各项上标是递增加1的,由此我们联想到组合数的基本性质：k =n ，利用它可以将各项组合数的系数化为相等，再利用性质 可得到证明证：由k =n 得 n（） n .例3求证：分析： 观察到，等式左边各项的组合数的上标和下标存在联系：上标m下标，而且各项下标是递增1的由此我们想到性质（2），将左边自第二项各项裂项相消，然后整理而得到求证证：由性质（2）可得 =+ （iN） 即令i1，2，k1，并将这k1个等式相加，得.技巧：例2和例3的证明分别利用性质（3）（5）、（2）此方法的技巧关键在于观察，分析各项组合数存在的联系，读者应在平时实践做题总结，把它们对号入座，什么样的联系用什么样的性质来解决3. 利用二项式定理证明我们都知道二项式定理：，对于某些比较特殊的组合恒等式可以用它来证明，下面以两个例子说明31直接代值例4求证：（1）（2）分析：以上两题左边的各项组合数都是以 的形式出现，这样自然会联想到二项式定理证：设 令a1，b3，代入，得 即，(2) 令a2，b1，代入，得即，.技巧：此方法的关键在于代值，在一般情况，a，b值都不会很大，一般都是0， 1，1，2，2 , 3，3这些数，而且a，b值与恒等式右边也有必然的联系，如上题中13，21=1,在做题的时候要抓住这点3. 2求导代值例5求证： （n2）分析：观察左边各项组合数的系数发现不可以直接运用二项式定理，但系数也有一定的规律，系数都是i(i-1) i=2,3,n 我们又知道（xi）=i(i-1)xi-2 由此我们想到了求导的方法证：对 两边求二阶导数，得 令x=1得 （n2）技巧：此方法证明组合恒等式的步骤是，先对恒等式 两边对x求一阶或二阶导数，然后适当选取x的值代入4. 比较系数法比较系数法主要利用二项式定理中两边多项式相等的充要条件为同次幂的系数相等加以证明例6求证： （范德蒙恒等式）分析：本题若考虑上面所讲和方法来证明是比较困难的，注意到等式左边各项恰是二项展开式中各项二项式系数的平方，考虑二项展开式 =和这两个展开式乘积中常数项且好式是 证： =（） （）又有，比较两边的常数项，左边常数项为 右边的常数项为，根据二项展开式中对应项的唯一性得 技巧：此方法关键是适当地选择一个已知的恒等式，然后比较两边x同次幂的系数当然，已知恒等式的选择不是唯一的，例5也可以选择已知恒等式 ，只须比较恒等式中两边含有的系数即可得证，证明留给读者5. 利用数列求和方法证明回到例2，除了利用组合数的性质，我们还可以有其他方法观察，恒等式左边的各项组合数的系数为等差数列，现在我们仿照求和公式的证明来证明例2证：设 则 得 技巧：此方法的证明有一定的特殊性,分析等式中组合数系数的变化规律尤其重要,知识的迁移在此方法是一个很好的见证6. 利用数学归纳法证明我们都知道数学归纳法，在证明数列的题目中，我们就体会了数学归纳法的好处，只要按照数学归纳法的两个步骤进行就可以了那么，组合恒等式的证明可不可以用数学归纳法来证明呢？看下面的一个例题例7已知是任意的等差数列，且n2，求证：分析：由于本题恒等式左边的各项组合数系数是一个不确定的等差数列，用上面的方法处理就比较困难，又因为等式含有数列，我们不妨用数学归纳法试试 证：i) 当n2时，因为所以，故等式成立，ii) 假设，当nk（k2）时等式成立，即对任何等差数列，有， 则当nk1时，利用组合数性质，有 因为根据归纳假设，当nk时，对任意等差数列式都成立，所以上式右端的两个方括号都等于零于是我们证明了当nk1时等式也成立，根据（1）和（2）可知，等式对n2的任何自然数都成立技巧：用本方法证明的思路清晰，只须分两步进行即可，但归纳法的关键是由“假设nk成立，推导到nk1也成立”这一步中间的变换过程比较复杂，在“无路可走”的情况之下，归纳法也是一个好的选择7. 利用组合分析方法证明所谓组合分析法就是通过构造具体的组合计数模型，采用了“算两次”的方法，再根据组合数的加法原理和乘法原理得到恒等式两边相等例8证明： （n2）证明：算右边，假设有2n个球，现要在2n个球中任取出（n1个，取法有 种，算左边，把2n个球分成两堆，每堆个n个，现要 在2n个球在中取出（n1）个，取法是，在第一堆取0个，第二堆取（n1）个，或第一堆取1个，第二堆 取（n2）个，或或第一堆取（n1）个，第二堆 取0.再根据加法原理总的取法有 又因为 所以，左右两边都是在2n个球中取出（n1）个球，因此有， （n2）技巧：用组合分析法证明组合恒等式的步骤是：选指出式子的一边是某个问题的解，然后应用加法原理和乘法原理等去证明式子的另一边也是该组合问题的解用此方法也可以证明例6，证明过程非常简洁8概率法证排列组合基本理论是古典概型计算的基石能否用古典概型来解决某些排列组合问题？我们来看下面的例子例9 证明组合数加法题推公式：分析：把特征等式经过适当变形，使之右端变为1，而左端为若干项之和，根据左端和式中各项的特点，构造以概率模型，并找到样本空间的一个特殊分化，使之相应概率等于左端和式的各项，从而得证证明：我们将公示变形为下面利用超几何分布概率公式构建摸球模型来证明：设袋中有只球，其中有1只黑球，1只白球，现随机地抽取k只球.设事件A：“抽取的k只球中含有黑球”，B：“抽取的k只球中含有白球”，则由全概率公式得=由,立即得证该公式技巧：利用概率对立事件发生的概率和为1，或是在某种情况下必然事件的概率也为1.可以与实际相结合，容易理解9 几何法例10 证明分析：主要是利用组合的几何意义来证明无重组合的几何意义表示平面坐标上的（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可知等式的左边，表示从（0,0）到（0，n）点的增路径，表示从（0,0）到（1，n-1）点的增路径数， ，表示从（0,0）到（n-1,1）点的的增路径数，表示从（0,0）到（n,0）点的的增路径数1，而这所有的地增路径之和就是从（0,0）点到斜边上的整点的递增路径另一方面，从（0,0）点到斜边上任何一整点的递增路径是n步步长，每一步是x或者y，有两种选择，由乘法法则，n步的不同方法的总数为2，所以等式成立10 用幂级数法我们知道，可展成如下幂级数： 现在我们用次展开式证明下列等式例11 证明 证明：因为 = 左边应为：= 右边应为：比较两边的系数可知，原等式成立技巧：对组合求和，当组合下标变动时，常用幂级数方法11微积分法例11 求证：分析：利用微分与积分的相互转化是问题得以解决，求导后再积回去，不改变原等式的性质证明：令 则 ，= =即上式两边同时求积分得 所以 从而 12 递推公式法上述例12是否还可以用递推公式的方法解决，我们来看一下证明：令 （）则 ，当时，= = =所以 = =13 生成函数法首先介绍生成函数相关定义和定理定义1 设是一个数列，做形式幂级数 称为数列的生成函数定义2 对任何实数r和整数k有 定理1 设数列的生成函数为，若，则定理2 设m是一个有理数，有例13 设nN,有证明：设数列的生成函数A(x),即A(x)=设,先求A(x),由=对上式两边求导得：两边同乘x得：对上式两边求导得：=两边同乘x得：=A(x)由定理1由式得中的系数为，中 的系数为.因此展开式中的系数为=因此 =14 牛顿公式法相关定理及定义:定义1 设为任一数列，令 =- 这里成为差分算子定义2 设为任一数列，令 这里称E移位算子定义3 设为任一数列，令 这里称为恒等因子定理1 设为任一数列，则+，约定：定理2 （牛顿公式） =（+） 例14 =(其中， ，)，有=证明：由牛顿公式，,实际上是证明=对用数学归纳法证明当时，有=0当时，令（），假设时命题成立，当且时，令显然（），由归纳法设=（）=0设（其中）对n用归纳法证明当时，令 =假设时命题成立当时，由有 由归纳假设有 =因此 （）=+=因此，命题成立结束语关于组合恒等式的证明方法还有很多，例如，倒序求和法，二项式反演公式法，母函数等等本文介绍的主要是几种方法中，大多是以高中知识为基础，也可以说是组合恒等式证明的初等方法，也有大学学的方法，比较深入，不是很好理解通过学习，我们要学会具体问题具体分析和解决问题多样化的思想顺便指出，以上例题的解法不是唯一的，本文也有提及细心的话也可以留意到，各种方法之间也存在着一定的联系，在这里就不再累赘了参考文献陈智敏，组合恒等式新的证明方法，广州大学学报，（）侯为波、卓泽强，古典概型在排列组合恒等式证明中的应用，淮北师范大学学报，（）概率在证明组合恒等式中的应用，淮南师范大学学报，（）周棉刚，关于组合恒等式的几种证法，黔南民族师范学院学报，（）何宗祥，漫谈组合恒等式的证明，中国数学月刊（）几何法，数学教学，（）杨青文，有关组合恒等式的几种证法，青海师专学报，（）杜庆坤，组合恒等式的证明技巧，临沂师范学报，（）曹汝成，组合数学，华南理工大学出版社，广州，卢开澄，组合数学，清华大学出版社（第二版），北京