各种数学归纳法.docx

《各种数学归纳法.docx》由会员分享，可在线阅读，更多相关《各种数学归纳法.docx（34页珍藏版）》请在三一办公上搜索。

1、各种数学归纳法1.5 归纳法原理与反归纳法 数学归纳法是中学教学中经常使用的方法中学教材中的数学归纳法是这样叙述的：如果一个命题与自然数有关，命题对n=1正确；若假设此命题对n1正确，就能推出命题对n也正确，则命题对所有自然数都正确通俗的说法：命题对n=1正确，因而命题对n=2也正确，然后命题对n=3也正确，如此类推，命题对所有自然数都正确对于中学生来说，这样形象地说明就足够了；但是毕竟自然数是无限的，因而上述描述是不够严格的，有了皮阿罗公理后，我们就能给出归纳法的严格证明 定理1.19 如果某个命题，它的叙述含有自然数，如果命题对n=1是正确的，而且假定如果命题对n的正确性就能推出命题对n+

2、1也正确，则命题对一切自然数都成立 证明 设是使所讨论的例题正确的自然数集合，则 (1) 1M 设nM，则命题对n正确，这时命题对n+1=n也正确，即 (2) nM 所以由归纳公理，含有所有自然数，即命题对所有自然数都成立 下面我们给出一个应用数学归纳法的命题 例 求证 1+2+L+n222=n(n+1)(2n+1)6证明 (1)当n=1时，有 1=21(1+1)+(21+1)6=1 所以n=1，公式正确 (2)假设当k=n时，公式正确，即 1+2+L+n222=n(n+1)(2n+1)6那么当k=n时，有 1+2+L+n+(n+1)=(1+2+L+n)+(n+1)= n(n+1)(2n+1)

3、6+(n+1)222222222= n(n+1)(2n+1)+6(n+1)62= (n+1)n(2n+1)+6(n+1)6= (n+1)(2n+7n+6)6(n+1)(n+2)(2n+3)662= = = (n+1)(n+1)+1)(2(n+1)+1)所以公式对n+1也正确 在利用数学归纳法证明某些命题时，证明的过程往往归纳到n-1或n-2，而不仅仅是n-1，这时上述归纳法将失败，因而就有了第二数学归纳法在叙述第二归纳法以前，我们先证明几个与自然数有关的命题 命题 若ab，则a+cb+c 证明 因为ab 所以 a=b+k a+c=b+k+c=(b+c)+k a+cb+c 所以 命题 是自然数中

4、最小的一个 证明 若a1，则a有前元b，所以 b=a,a=b+1(a1.) 命题3 若ba，则ba+1 证明 若ba,则b=a+k 因为k1，所以a+ka+1，即ba+1 由上述有关自然数大小的命题，我们得出下面定理，有时也称为最小数原理 定理1.20 自然数的任何非空集合含有一个最小数，即存在一个数aA，使得对集合中任意数b，均有ba 证明 设M是这样的集合： 对于M中任意元素mM，对A中任意元素a，均有 am 则M是非空集合 因为1M，由归纳公理(4)知，一定存在一个元素mM 但mM，即m+1M， 否则由mMmM得，这显然不可能 现在我们证明 mA因为若 mA， 则中任意元素am am+1

5、 所以m+1M，与m+1M矛盾，所以m即为中最小元素 上述定理也称为最小数原则，有的作者把它当成公理，用它也可以证明数学归纳法，下面我们给出所谓第二数学归纳法 定理1.21 对于一个与自然数有关的命题，若 (1)当n=时命题正确； (2)假设命题T对n1，所以对一切nk,命题T成立，又由(2)推出命题T对k正确结论矛盾 下面我们给出两个只能应用第二数学归纳法而不能应用第一归纳法解题的例子 例 已知数列a-1,a0,a1a2LanL，有 an=3an-1-2an-2且 a-1=32,a0=2 求证an=2n+1 证明 对n=1，有a1=3a0-2a31=32-22=2+1 所以命题对n=1正确

6、假设命题对nk正确，则 ak=3ak-1-2ak-2=3(2k-1+1)-2(2k-2+1)= 32k-1+3-2k-1-2=2k+1 所以命题对n=k正确 由第二数学归纳法本题得证 例 已知任意自然数nN均有 nna3i=a2i i=1i=1求证an=n 证明 (1)当n=1时，由a31=a21，得a1=1 所以命题对n=1正确 (2)假设对nk命题正确，这时 a1=1,a2=2,L,ak=k， 当n=k+1时， k+1a3k3k33i=ai+ak+1=(a2i)+ak+1 i=1i=1i=1k+1k+1k但是 a322i=(ai)=(ai+ak+1)= i=1i=1i=1kk+1(a22i

7、)+2(ai)ak+1+ak+1 i=1i=1又因为归纳假设对nk命题正确，所以 a1=1,a2=2,L,ak=k k所以 ak(k+1)i=i=12由(1)和(2)式得 (1) (2) ka3k+1=2ak+1ai+ak+1 i=12消去ak+1，得 解得 ak+1=k(k+1)+ak+1 2ak+1=k+1(ak+1=-k舍去） 所以命题对n=k+1也正确 上边的两个例子，实际上例命题归结到n-1和n-2，而例则需要归结到1,2,k，由此可见，第二数学归纳法的作用是不能由第一归纳法所替代的 现在我们继续讲数学归纳法当然，归纳并一定从n=1开始，例如例数列的例子，也可以从某数k开始数学归纳法

8、还有许多变形，其中著名的有跳跃归纳法、双归纳法、反归纳法以及跷跷板归纳法等，下面我们就逐个介绍这些归纳法 跳跃归纳法 若一个命题对自然数1,2,Ll,都是正确的；如果由假定命题对自然数k正确，就能推出命题对自然数k+l正确则命题对一切自然数都正确 证明 因为任意自然数 n=lq+r0rl 由于命题对一切0rm n证明 (1)当m=1,n=1时，命题显然正确，即 2111,21 1(2)设命题对自然数对m与n正确，即 2mnnm 这时 2(m+1)n=2mn2nm2nnnn=(2m)(m+1) 即命题对数对正确； 另一方面 2m(n+1)=2mn2mnm2m=(2n)m(n+1) m即命题对数对

9、(m,n+1)也正确，由双归纳法知，命题对一切自然数对(m,n)都成立 反归纳法 若一个与自然数有关的命题，如果 (1)命题对无穷多个自然数成立； (2)假设命题对n=k正确，就能推出命题对n=k-1正确则命题对一切自然数都成立； 上述归纳法称为反归纳法，它的合理性我们做如下简短说明： 设是使命题不正确的自然数，如果是非空集合，则中存在最小数m，使得命题对k=m不正确；由于命题对无穷多个自然数正确，所以存在一个n0m，且命题T对n0正确；由于命题T对m不正确，所以命题对m=m+1也不正确，否则由命题T对m=m+1正确就推出命题T对m正确矛盾！这样，命题对m+2也不正确，经过n0-m次递推后，可

10、得命题对n0也不正确这与已知矛盾，所以是空集合 反归纳法又称倒推归纳法，法国数学家柯西首次用它证明了n个数的算术平均值大于等于这n个数的几何平均值 例6 求证n个正实数的算术平均值大于或等于这n个数的几何平均值，即 a1+a2+L+annna1a2Lan 证明 当n=2时， a1+a22a1a2 因此命题对n=2正确 当n=4时， a1a2a3a4(a1+a22)(2a3+a42)(2a1+a2+a3+a44) 4因此命题对n=4正确 同理可推出命题对n=23=8，n=24,，n=2s都正确，所以命题对无穷多个自然数成立 设命题对nk正确，令 sk=a1+a2+L+akk,sk-1=a1+a2

11、+L+ak-1k-1则 sk-1=a1+a2+L+ak-1+sk-1k 由归纳假设命题对nk正确，所以 sk-1=(ka1+a2+L+ak-1+sk-1ksk-1a1a2Lak- k-1)a1a2Lak-1sk-1 所以 即 a1+a2+L+ak-1k-1k-1a1a2Lak-1 命题对n =k-1也正确，由反归纳法原理知，命题对一切自然数成立 由于上述不等式是著名不等式，我们再给出几种证明： 前已证明，命题对n=2时正确，设n，令 b1=a1,b2=a2,L,bn=an, bn+1=bn+2=L=b2m=a1+a2+Lann=s mm这时我们有 b1b2LbnLb2m=(a1a2Lan)Sm

12、2-nm(b1+b2+L+b2m22mm)2m= (ns+(2-n)s2m)2m=s nm即a1a2Lans命题对n2正确 利用数学归纳法证明 不妨设n个数为0a1a2LaiLajLan 却增加了而当a1=a2=L=an时， na1a2Lan=a1+a2+L+ann所以n个数的算术平均值大于等于几何平均值 下面我们给出应用上述不等式的例子 例 在体积一定的圆柱形中，求其中表面积最小的一个 解 设圆柱的高为x，底圆半径为y，体积为常数，表面积为，则 V=pxy S=2pxy+2py 22其中为常数，欲求的极小值 已知S=2pxy+2py=pxy+pxy+2py，所以 22pxy+pxy+2py3

13、2pxypxy2py 2即 (S3)2pp32xy=2pV 242显然只有当pxy=pxy=2py2时，取最小值即当x=2y时，值最小 例 求证在所有具有相同面积的凸四边形中，正方形的周长最短 证明 用abcd表示四边形的四条边，如图j为a与b的夹角，j为c与d的夹角，用表示四边形的面积，则 2A=absinj+cdsinja+b-2abcosj=c+d2222L(1)-2cdcosjL(2)由式得 16A2=4a2b2sin2j+4c2d2sin2j+8abcdsinjsinj (a+b-c-d)=(2abcosj-2cdcosj)=4abcosj+4cd2222222222-8abcdco

14、sjcosj由式得 16A+(a+b-c-d)= 4ab+4cd2222222222+8(abcd)(sinjsinj-cosjcosj)2224ab+4cd2-8abcdcosq 其中q=j+j 再利用半角公式cosq=2cos2q22-1，得 2222216A+(a+b-c-d)= 4ab+4cd2222-8(abcd)(2cos22q2-1)= 4(ab+cd)-16abcdcos2222222q22所以16A=4(ab+cd)-(a+b-c-d)-16abcdcos222222q2222=2(ab+cd)-(a+b-c-d)2(ab+cd)+(a+b-c-d)-16cos=(c+d)-

15、(a-b)(a+b)-(c-d)-16abcdcos22222q2q22=(c+d+b-a)(c+a+d-b)(a+b+d-c)(a+b+c-d)-16abcdcos如令a+b+c+d=2p=四边形周长，得 q216AA22=16(p-a)(p-b)(p-c)(p-d)-16abcdcos22q2=(p-a)(p-b)(p-c)(p-d)-abcdcosq2因为abcdcos22q20，所以 p-a+p-b+p-c+p-d4=(P24A(p-a)(p-b)(p-c)(p-d)(4p-2p4A2)= 4)4p2) 4 要使p最小，只有当上式取等号时即当 a=b=c=d， 且cos2q2=0,q=

16、90，这样的四边形只能是正方形 最后，我们给出跷跷板归纳法 有两个与自然数有关的命题An与Bn，若 (1)A1成立； (2)假设Ak成立，就推出Bk成立，假设Bk成立就推出Ak+1成立 则对一切自然数n, An与Bn都成立 A1 B1 A2 B2 M Ak Bk M Ak+1 M 这里我们只给出一个例子说明上述归纳法 例 已知 0a1,a1=1+a,an=a+1an-1,n2 求证 1an11-a1证明 令 Ak:ak1 (1)当n=1时， a=1+a=1-a21-a11-a所以A1成立 (2) a2=1a1+a=11+a+a= 1+a+a1+a2(1+a)1+a2=1+a111-aak1 +a=1-a+a=1 即k成立 若k成立，则 ak+1=1ak+a1+a=1-a21-a-1，且x0,nN,n2，求证 (1+x)1+nx n