数学归纳法应用.ppt

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

1、第5章 数学证明 5.2数学归纳法5.2.2数学归纳法应用,第15课时,数学归纳法应用,例2：某次象棋比赛共有人参加，每两个都应对奕，且一定决出胜负.证明：比赛结束后，可将这个人列为一队，使队列中的每一个人都曾战胜过紧跟在他后面的那个人.,例3有2n+1个飞机场，每个机场都有一架飞机，各个机场间的距离都不相等，让所有的飞机一起起飞，飞向最近的机场降落。 求证：必存在一个机场，没有飞机降落。 1当n=1时，3个机场为A、B、C，且BCAC,BCAB 则B、C间的飞机必定对飞， 于是不管A机场的飞机飞向B还是C机场，A机场都没有飞机降落。 2假设n=k时命题成立，则当n=k+1即2k+3个机场时，

2、 由于各机场间距离都不相等，必有两个机场间距离最短，这两处的飞机对开。 将这两机场“撤出”，由假设，剩下的2k+1个机场中，必存在一个机场P没有飞机降落。 再把“撤出”的两机场复归，则机场P仍无飞机降落， 得n=k+1时命题仍成立。,第二数学归纳法例举,例4、有两堆棋子，数目相等。两人玩耍，每人可以在一堆里任意取几棵，但不能同时在两堆里取，规定取得最后一棵者胜。问先取者得胜，还是后取者可以得胜？试加以证明。 猜测“后取者可以得胜”。 证明：（1）当n=1时，必是后取者得胜。 （2）假设当nk时命题成立，对于n=k+1，当先取者在一堆里取棋子m (1mk+1)颗时， 后取者则在另一堆里取棋子m颗

3、，两堆棋子仍都是(k+1-m)颗。 这样就变成了n=k+1-m的问题，按照归纳假设，后取者可以得胜，即n=k+1命题也成立。 由第二数学归纳法，证明了：对于任意正整数n，后取者按上述策略都可以得胜。 思考：若两堆棋子的数目不同，则先取者和后取者哪个有必胜的策略？,案例1,多面体欧拉公式,多面体欧拉公式的证明及其在平面上的推广连通平面图的特征,外部面“海洋”，内部面。 连通图：图中任意两点都有路相通。 如果一个连通的平面图G有V个顶点，E条边，F个面，那么V-E+F=2。 对平面图的边数用数学归纳法证明,如果一个连通的平面图G有V个顶点，E条边，F个面，那么V-E+F=2。,思考：对V,E,F哪

4、个量进行归纳比较合适？ 对边数E进行归纳试试看！ 证明： 1）若G只有1条边,则 V=2,E=1,F=1,故V-E+F=2成立。 2）假设G为有k条边的连通的平面图，公式Vk-Ek+Fk=2成立。 考察G为（k+1）条边时的情况。 即当图G由k条边增加1条边，使它仍为连通图时，有哪些情形？,连通平面图G有V-E+F=2成立,（2） 当G为（k+1）条边时,只有两种情形： 1）增加一个新顶点v/，则v/必与图中的一点v相连。 此时，Vk与Ek都增加1，而Fk不变， 故Vk+1-Ek+1+Fk+1 =(Vk+1)-(Ek+1)+Fk=Vk-Ek+Fk=2. 2）用一条边连结图中两个顶点u和v。 这时，Ek和Fk都增加1，而顶点数Vk没有变， 故Vk+1-Ek+1+Fk+1 =Vk-(Ek+1)+(Fk+1)=Vk-Ek+Fk=2. 所以，E=k+1时，公式V-E+F=2也成立。 由数学归纳法，命题对任何正整数E都成立。,