算法设计基础 上海交通大学软件学院课件2010 第2章.pptVIP

算法设计 上海交通大学计算机系 lphuang@ 第2章 数学归纳法 2.1 绪论 本章将通过一些例子简要介绍一下数学归纳法，这些例子有些比较简单，有些则相对较难。对那些从未用过归纳法进行命题证明的读者来说，学习本章的内容可能比较困难。其实构造证明的过程和设计算法的过程其实是类似的，具备使用归纳法进行命题证明的经验对算法设计来说是有所裨益的。本书后续章节将逐步介绍数学归纳法在算法设计中的重要作用。 数学归纳法 其原理如下：设T为欲证的定理，若T中含有变量n，n取一切自然数（即正整数），那么不必直接证明对于所有n，T都成立，只需证明下面两个条件成立， 1.当n=1时，T成立； 2.对任意n1，如果n-1时T成立，那么n时T也成立。 定理2.1 对任意的自然数x和n，xn-1能被x-1除尽。 证明：对n进行归纳。当n=1时，定理显然成立。 假设n-1时定理仍然成立，即假设对任意自然数x，xn-1-1能被x-1除尽。 接下来要证明的就是xn-1能被x-1除尽。 证明思路就是用xn-1-1来表达xn-1。 根据归纳假设xn-1-1能被x-1除尽，即： xn-1=x(xn-1-1) + (x-1) 由归纳假设，等式右边的第一项能被x-1除尽，而第二项本身就是x-1。 归纳法原理 如果对于带有参数n的命题P，当n=1时P成立；对每一个n，n1，若n-1时P成立可推出n时P也成立；那么对任意自然数，P都成立。 如果对于带有参数n的命题P，当n=1时P成立；对每一个n，n≥1，若n时P成立能推出n+1时P也成立；那么对任意自然数，P都成立。 如果对于带有参数n的命题P，当n=1时P成立；对每一个n，n1，若对任意小于n的自然数P成立能推出对n命题P也成立；那么对任意自然数，P都成立。 简单变形 如果对于带有参数n的命题P，当n=1和n=2时P都成立；对每一个n，n2，若n-2时P成立能推出n时P也成立；那么对任意自然数，P都成立。 用这个变形，我们将沿着两条平行的路进行归纳。n=1作为归纳基础，通过归纳能得到命题在任意奇数时成立；n=2作为归纳基础，通过归纳能得到命题在任意偶数时成立。 变形 如果对于带有参数n的命题P，当n=1时P成立；对每一个n（n大于1且是2的整数幂），若n/2时命题P成立能推出对n命题P也成立；那么对任意一个2的整数幂的自然数，P都成立。 这个变形就是把最初的归纳法原理中的参数n写作2k，然后对参数k（从k=0开始）进行归纳。 2.2三个简单的例子 前n个自然数之和为n(n+1)/2。 证明：对n进行归纳。 当n=1时，有S(1)=1=1×(1+1)/2，故命题成立。 假设前n个自然数之和S(n)为n(n+1)/2。 接着证前n+1个自然数之和S(n+1)=(n+1)(n+2)/2。 根据S(n)的定义， 有S(n+1)=S(n)+n+1， 又由假设S(n)= n(n+1)/2，于是可以推得S(n+1)=n(n+1)/2+n+1=(n+2)(n+1)/2，命题得证。 T(n)=8+13+18+23+…+(3+5n)。 根据上例的结果，已有S(n)等于n2/2+n/2，而本例式中的每一项都是上例中对应项的五倍，因此不妨假设T(n)也能用二次多项式表示。设G(n)=c1n2+c2n+c3。这里引入三个待定系数c1、c2和c3，然后通过计算开始的几项来确定这些系数。若n=0，则和为0，因此c3一定为0。对n=1和n=2，则分别有以下二式： （1） 1·c1 + 1·c2 = 8 （2） 4·c1 + 2·c2 = 13+8 (2)式减去(1)式乘2的积，有2c1=5，从而c1=2.5，c2=5.5。 先假设G(n)=2.5n2+5.5n就是所求的表达式，然后用归纳法证明G(n)=T(n)。 现在假设G(n)=T(n)，然后来证明G(n+1)=T(n+1)： T(n+1) =T(n)+5(n+1)+3=（根据归纳法）G(n)+5(n+1)+3 = 2.5n2+5.5n+5n+8=2.5n2+5n+2.5+5.5n+5.5 = 2.5(n+1)2+5.5(n+1)=G(n+1)。 定理2.4 若n是自然数，且1+x0，则 (1+x)n≥1+nx。 对n进行归纳 n=1时，(2.1)式的两边都等于1+x。 假设(1+x)n≥1+nx对所有满足1+x0的x都成立 下面来考虑n+1时的情况。 要证明的是对所有满足1+x0的x， (1+x)n+1≥1+(n+1)x成立。 (1+x)n+1=(1+x)(1+x)n≥（根据归纳法）(1+x)(1+nx) =1+(n+1)x+nx2≥1+(n+