第15课时5.2.2数学归纳法应用ppt课件

1、第第5章章 数学证明数学证明 5.2数学归纳法数学归纳法5.2.25.2.2数学归纳法应用数学归纳法应用第第15课时课时1;.2数学归纳法应用数学归纳法应用例例2：某次象棋比赛共有人参加，每两个都应对奕，且一定决出胜负：某次象棋比赛共有人参加，每两个都应对奕，且一定决出胜负.证明：比赛证明：比赛结束后，可将这个人列为一队，使队列中的每一个人都曾战胜过紧跟在他后面的结束后，可将这个人列为一队，使队列中的每一个人都曾战胜过紧跟在他后面的那个人那个人.3例例3有有2n+1个飞机场，每个机场都有一架飞机，各个机场间的距离都不相等，让所有的飞个飞机场，每个机场都有一架飞机，各个机场间的距离都不相等，让所

2、有的飞机一起起飞，飞向最近的机场降落。机一起起飞，飞向最近的机场降落。求证：必存在一个机场，没有飞机降落。求证：必存在一个机场，没有飞机降落。1当当n=1时，时，3个机场为个机场为A、B、C，且且BCAC,BCAB则则B、C间的飞机必定对飞，间的飞机必定对飞，于是不管于是不管A机场的飞机飞向机场的飞机飞向B还是还是C机场，机场，A机场都没有飞机降落。机场都没有飞机降落。2假设假设n=k时命题成立，则当时命题成立，则当n=k+1即即2k+3个机场时，个机场时，由于各机场间距离都不相等，必有两个机场间距离最短，这两处的飞机对开。由于各机场间距离都不相等，必有两个机场间距离最短，这两处的飞机对开。将

3、这两机场将这两机场“撤出撤出”，由假设，剩下的，由假设，剩下的2k+1个机场中，必存在一个机场个机场中，必存在一个机场P没有飞机降落。没有飞机降落。再把再把“撤出撤出”的两机场复归，则机场的两机场复归，则机场P仍无飞机降落，仍无飞机降落，得得n=k+1时命题仍成立。时命题仍成立。4第二数学归纳法第二数学归纳法例举例举例例4、有两堆棋子，数目相等。两人玩耍，每人可以在一堆里任意取几棵，但不能同时在两堆、有两堆棋子，数目相等。两人玩耍，每人可以在一堆里任意取几棵，但不能同时在两堆里取，规定取得最后一棵者胜。问先取者得胜，还是后取者可以得胜？试加以证明。里取，规定取得最后一棵者胜。问先取者得胜，还是

4、后取者可以得胜？试加以证明。猜测猜测“后取者可以得胜后取者可以得胜”。证明：证明：（1）当当n=1时，必是后取者得胜。时，必是后取者得胜。（2）假设当）假设当nk时命题成立，对于时命题成立，对于n=k+1，当先取者在一堆里取棋子，当先取者在一堆里取棋子m (1mk+1)颗时颗时，后取者则在另一堆里取棋子后取者则在另一堆里取棋子m颗，两堆棋子仍都是颗，两堆棋子仍都是(k+1-m)颗。颗。这样就变成了这样就变成了n=k+1-m的问题，按照归纳假设，后取者可以得胜，即的问题，按照归纳假设，后取者可以得胜，即n=k+1命题也成立。命题也成立。由第二数学归纳法，证明了：对于任意正整数由第二数学归纳法，证

5、明了：对于任意正整数n，后取者按上述策略都可以得胜。后取者按上述策略都可以得胜。思考：若两堆棋子的数目不同，则思考：若两堆棋子的数目不同，则先取者和后取者哪个有必胜的策略？先取者和后取者哪个有必胜的策略？案例案例1多面体欧拉公式多面体欧拉公式5;.6多面体欧拉公式的证明及其在平面上的推广多面体欧拉公式的证明及其在平面上的推广连通平面图的特征连通平面图的特征外部面外部面“海洋海洋”，内部面。，内部面。连通图：图中任意两点都有路相通连通图：图中任意两点都有路相通。如果一个连通的平面图如果一个连通的平面图G有有V个顶点，个顶点，E条边，条边，F个个面，那么面，那么V-E+F=2。对平面图的边数用数学

6、归纳法证明对平面图的边数用数学归纳法证明7如果一个连通的平面图如果一个连通的平面图G有有V个顶点，个顶点，E条边，条边，F个面，那么个面，那么V-E+F=2。思考：对思考：对V,E,F哪个量进行归纳比较合适？哪个量进行归纳比较合适？对边数对边数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条边，使它仍为连通图时，有哪些条边，使它仍为连通图时，有哪些情形？情形？8连通平面图连通平面图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