数学归纳法大字.pdf

《数学归纳法大字.pdf》由会员分享，可在线阅读，更多相关《数学归纳法大字.pdf（15页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数学归纳法数学归纳法 Mathematical InductionMathematical Induction1 1 归纳原理归纳原理 the principle of mathematicalthe principle of mathematicalinductioninduction如果如果 A A N,AN,A 是自然数集合是自然数集合 N N 的具有以下性的具有以下性质的子集：质的子集：a)a)0 0A Ab)b)k kA Ak+1k+1A A那么那么 A=N A=N证明证明.我们只要证明我们只要证明A=。设设A,由由 N N 是归纳集，是归纳集，A有最小元有最小元k k，k k A,

2、k,k A.由由 a)a)有有 k0,k-1k0,k-1 0 0。于是有。于是有 k-1 k-1 A,k-1k-1 A.由由 b)b)有有 k k A A，得到矛盾。，得到矛盾。因此因此A=,A=N,A=N。第一归纳法第一归纳法 Mathematical Induction Mathematical Induction关于自然数的一个性质关于自然数的一个性质 P(x),P(x),如果有如果有a)a)P(0)P(0)成立，成立，b)b)P(k)P(k)P(k+1),kP(k+1),k 0 0则则n n N P(n)N P(n)成立。成立。证明证明令令 A=nA=n N|P(n),AN|P(n),

3、A N.N.则满足则满足a)a)0 0 A,A,b)b)k kA Ak+1k+1A.A.由归纳原理由归纳原理 A=N,A=N,即即n n N P(n)N P(n)成立。成立。第一归纳法的应用例 1证明 12+22+32+n(n 1)(2n 1)+n2=6证明证明.a)n=1,1.a)n=1,12 2=1=1 2 2 3/6.3/6.k(k 1)(2k 1)b)b)设设 1 12 2+2+22 2+3+32 2+k+k2 2=6则则1 12 2+2+22 2+3+32 2+k+k2 2+(k+1)+(k+1)2 2k(k 1)(2k 1)2 2=+(k+1)+(k+1)6k(2k 1)6(k 1

4、)(k 1)=6(k 1)(k 2)(2k 3)=6(k 1)(k 1)1)(2(k 1)1)=6例 2 证明容斥原理|Ai|=|Ai|Ai Aj|i1i,j1i1i jnnn(1)k1i1,i2,ik11|Ani1 Ai2 Aik|(1)n1|A1 A2 An|证明证明 n=1 n=1，2 2 显然。显然。|Ai|=|Ai An1|i1i1n1nAi|+|+|A A|-|-|Ai An1|=|n n+1+1i1i1nnAi|+|+|A A|-|-|(Ai An1)|=|n n+1+1i1i1|A|A A=iii1i,j1i jnnjnn|(1)k1i1,i2,ik11|Anni1 Ai2 A

5、ik|(1)n1|A1 A2 An|+|+|A An n+1+1|-|-(|Ai An1|Ai An1 Aj An1|i1i,j1i jn(1)k1i1i1,i2,ik11|Ain Ai2 Aik An1|(1)n1i1in1|A1 A2 An An1|)j|A|A A=i,j1i jn1|(1)k1i1i1,i2,ik11|An1 Ai2 Aik|(1)n|A1 A2 An1|例 3 Function SQ(A)1.C1.C0 0 2.D 2.D0 0 3.while(D 3.while(D A)A)a.C a.CC+AC+A b.D b.DD+1D+1 4.Return(C)4.Retur

6、n(C)End of Function SQEnd of Function SQ解解.先猜测结果先猜测结果第一轮第一轮 C C1 1=A,D=A,D1 1=1=1第二轮第二轮 C C2 2=A+A=2A,D=A+A=2A,D2 2=2=2第三轮第三轮 C C3 3=2A+A=3A,D=2A+A=3A,D3 3=3=3猜猜 C Cn n=D=Dn nA A证明证明设设 C Ck k=D=Dk kA,A,则则 C Ck+1k+1=C=Ck k+A=D+A=Dk kA+AA+A =(D =(Dk k+1)A=D+1)A=Dk+1k+1A A所以所以 C Cn n=D=Dn nA A程序终止时程序终止

7、时 C=Cn,D=Dn=A.C=A*A=A2.例 4证明以下程序得到 X,Y 的最大公约数Function GCD(X,Y)Function GCD(X,Y)1.While (XWhile (X Y)Y)a)a)If(XY)ThenIf(XY)Then1.X1.XX-YX-Y b)Else b)Else 1.Y 1.YY-XY-X2.Return(X)2.Return(X)End of Function GCDEnd of Function GCD证明证明令令 X X0 0=X,Y=X,Y0 0=Y=Y X Xk+1k+1=X=Xk k-Y-Yk k 0 0 Y Yk+1k+1=Y=Yk k-

8、X-Xk k 0 0返回值为返回值为 X Xn n=Y=Yn n我们有我们有1)1)GCD(XGCD(X0 0,Y,Y0 0)=GCD(X,Y)=GCD(X,Y)2)GCD(X 2)GCD(Xk+1k+1,Y,Yk+1k+1)=GCD(X)=GCD(Xk k,Y,Yk k)由归纳法对任意由归纳法对任意 n,GCD(Xn,GCD(Xn n,Y,Yn n)=GCD(X,Y)=GCD(X,Y)当当 X Xn n=Y=Yn n时，时，GCD(XGCD(Xn n,Y,Yn n)=X)=Xn n。所以返回值即所以返回值即 GCD(X,Y)GCD(X,Y)。第一归纳法的推广关于整数的一个性质关于整数的一个性

9、质 P(x),P(x),如果有如果有a)P(na)P(n0 0)成立，成立，n n0 0 Z Zb)P(k)b)P(k)P(k+1),kP(k+1),k n n0 0.则则n n n n0 0P(n)P(n)成立。成立。例例 4.4.证明存在证明存在 n n0 0 Z,Z,使使n n n n0 0(2(2n nnn3 3)2 第二归纳原理如果如果 A A N,AN,A 是自然数集合是自然数集合 N N 的具有以下性的具有以下性质的子集：质的子集：a)a)0 0A Ab)b)sk(ss0k0。并且。并且sk(ssk(s A，于是，于是有有sk(ssk(sA)A)。由由 b)b)有有 k k A

10、A，得到矛盾。，得到矛盾。因此因此A=,A=N,A=N。第二归纳法 strong form of mathematicalinduction,Strong InductionStrong Induction关于自然数的一个性质关于自然数的一个性质 P(x),P(x),如果有如果有a)a)P(0)P(0)成立，成立，b)b)skP(s)s0k0。于是有于是有 skP(s)skP(s)成立成立.由由 b)b)有有P(k)P(k)成立，得到矛盾。成立，得到矛盾。因此因此nP(n)nP(n)成立。成立。第二归纳法的推广：关于整数的一个性质关于整数的一个性质 P(x),P(x),如果有如果有 n n0

11、0 Z Z 使使c)c)P(n P(n0 0)成立，成立，d)d)s s Z(nZ(n0 0 skskP(s)P(s)P(k),P(k),则则n n n n0 0P(n)P(n)成立。成立。例例 6 6 每个大于每个大于 1 1 的正整数的正整数 n n 都能唯一地都能唯一地表示为素因子的乘积：表示为素因子的乘积：n=pn=p1 1 1 1p p2 2 2 2p ps s s s,其中其中p p1 1pp2 2 pps s都是素数。都是素数。a a）n=2n=2 时命题成立，因为时命题成立，因为 2 2 是素数。是素数。b)b)设设 n=2,3,n=2,3,k-1,k-1 时命题真。时命题真。

12、我们证明我们证明 n=kn=k 时也真。时也真。i i 如果如果 k k 是素数，命题成立。是素数，命题成立。ii ii 如果如果 k k 不是素数，不是素数，k=lmk=lm,2 2 l l k-1k-1,2 2 m m k-1k-1.对对 l,ml,m 命题成立命题成立:l l=q=q1 1 1 1q q2 2 2 2q qu u u u,m m=t=t1 1 1 1t t2 2 2 2t tv v v v,则则k=k=lmlm=q=q1 1 1 1q q2 2 2 2q qu u u u t t1 1 1 1t t2 2 2 2t tv v v v=p=p1 1 1 1p p2 2 2

13、2p ps s s s。如果如果 p pi i=q=qj,j,i i=j j;如果如果 p pi i=t=tw,w,i i=w w;如果如果p pi i=q=qj j=t=tw,w,i i=j j+w w.由由 l l，m m 唯一分解，知唯一分解，知 k k 唯一分解。唯一分解。归纳完成，因此任意大于归纳完成，因此任意大于 1 1 的正整数都有的正整数都有唯一分解。唯一分解。例例.设设 A(pA(p1 1,p,p2 2,p,pn n)是一个不含联结词是一个不含联结词，的命题公式，的命题公式，A*A*是是 A A 的对偶公式，的对偶公式，则则1)A(p1)A(p1 1,p,p2 2,p,pn

14、n)A*(pA*(p1 1,p,p2 2,p,pn n)2)A2)AB B 当且仅当当且仅当 A*A*B*B*证明证明 1)1)对公式的复杂性对公式的复杂性(联结词的个数联结词的个数 n)n)归纳，归纳，a)a)n=0,n=0,即公式即公式 A(pA(p1 1,p,p2 2,p,pn n)=p)=pi i,是单个是单个命题变元没有联结词命题变元没有联结词.A(pA(p1 1,p,p2 2,p,pn n)=p)=pi iA*(pA*(p1 1,p,p2 2,p,pn n)=p)=pi i.b)b)设对少于设对少于 k k 个联结词的命题公式，个联结词的命题公式，1 1）都成立。我们证明对有都成立

15、。我们证明对有 k k 个联结词的命个联结词的命题公式，题公式，1 1）也成立。）也成立。设设 A A 有有 k k 个命题联结词。个命题联结词。情形情形 i)A=Bi)A=B。这时。这时 A*=B*A*=B*，B B 所含所含联结词少于联结词少于 k k 个，归纳假设个，归纳假设 1)1)对对 B B 成成立。立。A(pA(p1 1,p,p2 2,p,pn n)=B(p)=B(p1 1,p,p2 2,p,pn n)B*(pB*(p1 1,p,p2 2,p,pn n)A*(pA*(p1 1,p,p2 2,p,pn n)情形情形 ii)A=Bii)A=B C C。这时。这时 A*=B*A*=B*

16、C*C*，B,CB,C所含联结词少于所含联结词少于 k k 个，归纳假设个，归纳假设 1)1)对对B,CB,C 都成立。都成立。A(pA(p1 1,p,p2 2,p,pn n)=B(p=B(p1 1,p,p2 2,p,pn n)C(pC(p1 1,p,p2 2,p,pn n)B*(p B*(p1 1,p,p2 2,p,pn n)C*(pC*(p1 1,p,p2 2,p,pn n)(B*(p(B*(p1 1,p,p2 2,p,pn n)C*(pC*(p1 1,p,p2 2,p,pn n)A*(pA*(p1 1,p,p2 2,p,pn n)情形情形 iii)A=Biii)A=B C.C.这时这时

17、A*=B*A*=B*C*C*，B,CB,C所含联结词少于所含联结词少于 k k 个，归纳假设个，归纳假设 1)1)对对B,CB,C 都成立。都成立。A(pA(p1 1,p,p2 2,p,pn n)=B(p=B(p1 1,p,p2 2,p,pn n)C(pC(p1 1,p,p2 2,p,pn n)B*(p B*(p1 1,p,p2 2,p,pn n)C*(pC*(p1 1,p,p2 2,p,pn n)(B*(p(B*(p1 1,p,p2 2,p,pn n)C*(pC*(p1 1,p,p2 2,p,pn n)A*(pA*(p1 1,p,p2 2,p,pn n)归纳完成，因此归纳完成，因此 1)1)

18、对任意不含联结词对任意不含联结词，的命题公式成立。的命题公式成立。2 2）可以由）可以由 1)1)推出：推出：由由 1)1)A(pA(p1 1,p,p2 2,p,pn n)A*(pA*(p1 1,p,p2 2,p,pn n)A*(pA*(p1 1,p,p2 2,p,pn n)A(pA(p1 1,p,p2 2,p,pn n)B*(pB*(p1 1,p,p2 2,p,pn n)B(pB(p1 1,p,p2 2,p,pn n)A(pA(p1 1,p,p2 2,p,pn n)B(p B(p1 1,p,p2 2,p,pn n)A(pA(p1 1,p,p2 2,p,pn n)B(pB(p1 1,p,p2

19、2,p,pn n)因此因此 2 2）成立。）成立。3 双重归纳法关于自然数的一个性质关于自然数的一个性质 P(x,y),P(x,y),如果有如果有a)P(0,0)a)P(0,0)成立，成立，b)P(s,t)b)P(s,t)P(s+1,t)P(s+1,t)P(s,t+1)P(s,t+1)则则xyP(x,y)xyP(x,y)成立。成立。证明证明 1)1)xP(x,0)xP(x,0)成立：成立：a)a)P(0,0)P(0,0)成立，成立，b)b)P(s,0)P(s,0)P(s+1,0)P(s+1,0)由第一归纳法由第一归纳法xP(x,0)xP(x,0)成立。成立。2 2）x P(x,t)x P(x,

20、t)x P(x,t+1)x P(x,t+1)a)P(x,t)a)P(x,t)成立成立 b)P(x,t)b)P(x,t)P(x,t+1)P(x,t+1)由第一归纳法由第一归纳法xyP(x,y)xyP(x,y)成立。成立。HomeworkP69P698,15,16,18,26,27,32,348,15,16,18,26,27,32,34补补 1.1.证明将命题公式中的命题变元用命题公证明将命题公式中的命题变元用命题公式代换得到的仍然是命题公式：式代换得到的仍然是命题公式：设设 A(pA(p1 1,p,p2 2,p,pn n)是一个命题公式，是一个命题公式，B B1 1,B B2 2,B,Bn n都是命题公式，则分别用都是命题公式，则分别用 B Bi i代换代换A A 中所有中所有 p pi i得到的得到的 表达式表达式 A(pA(p1 1/B/B1 1,p,p2 2/B B2 2,p,pn n/B/Bn n)是命题公式。是命题公式。补补 2.2.已知数列已知数列aan n 的递推关系是的递推关系是a an+1n+1=2a=2an n+1(n+1(nN)N)，a a1 1=1=1，求数列的通项公，求数列的通项公式式 a an n.