第15課時(shí)5.2.2數(shù)學(xué)歸納法應(yīng)用

1、第第5章章 數(shù)學(xué)證明數(shù)學(xué)證明 5.2數(shù)學(xué)歸納法數(shù)學(xué)歸納法5.2.25.2.2數(shù)學(xué)歸納法應(yīng)用數(shù)學(xué)歸納法應(yīng)用第第15課時(shí)課時(shí)數(shù)學(xué)歸納法應(yīng)用數(shù)學(xué)歸納法應(yīng)用 例例2：某次象棋比賽共有人參加，每?jī)蓚€(gè)：某次象棋比賽共有人參加，每?jī)蓚€(gè)都應(yīng)對(duì)奕，且一定決出勝負(fù)都應(yīng)對(duì)奕，且一定決出勝負(fù).證明：比賽證明：比賽結(jié)束后，可將這個(gè)人列為一隊(duì)，使隊(duì)列結(jié)束后，可將這個(gè)人列為一隊(duì)，使隊(duì)列中的每一個(gè)人都曾戰(zhàn)勝過緊跟在他后面中的每一個(gè)人都曾戰(zhàn)勝過緊跟在他后面的那個(gè)人的那個(gè)人. 例例3有有2n+1個(gè)飛機(jī)場(chǎng)，每個(gè)機(jī)場(chǎng)都有一架飛機(jī)，各個(gè)飛機(jī)場(chǎng)，每個(gè)機(jī)場(chǎng)都有一架飛機(jī)，各個(gè)機(jī)場(chǎng)間的距離都不相等，讓所有的飛機(jī)一起起飛，個(gè)機(jī)場(chǎng)間的距離都不相等

2、，讓所有的飛機(jī)一起起飛，飛向最近的機(jī)場(chǎng)降落。飛向最近的機(jī)場(chǎng)降落。 求證：必存在一個(gè)機(jī)場(chǎng)，沒有飛機(jī)降落。求證：必存在一個(gè)機(jī)場(chǎng)，沒有飛機(jī)降落。 1當(dāng)當(dāng)n=1時(shí)，時(shí)，3個(gè)機(jī)場(chǎng)為個(gè)機(jī)場(chǎng)為A、B、C，且且BCAC,BCAB 則則B、C間的飛機(jī)必定對(duì)飛，間的飛機(jī)必定對(duì)飛， 于是不管于是不管A機(jī)場(chǎng)的飛機(jī)飛向機(jī)場(chǎng)的飛機(jī)飛向B還是還是C機(jī)場(chǎng)，機(jī)場(chǎng)，A機(jī)場(chǎng)都沒機(jī)場(chǎng)都沒有飛機(jī)降落。有飛機(jī)降落。 2假設(shè)假設(shè)n=k時(shí)命題成立，則當(dāng)時(shí)命題成立，則當(dāng)n=k+1即即2k+3個(gè)機(jī)場(chǎng)時(shí)，個(gè)機(jī)場(chǎng)時(shí)， 由于各機(jī)場(chǎng)間距離都不相等，必有兩個(gè)機(jī)場(chǎng)間距離最由于各機(jī)場(chǎng)間距離都不相等，必有兩個(gè)機(jī)場(chǎng)間距離最短，這兩處的飛機(jī)對(duì)開。短，這兩處的飛機(jī)對(duì)

3、開。 將這兩機(jī)場(chǎng)將這兩機(jī)場(chǎng)“撤出撤出”，由假設(shè)，剩下的，由假設(shè)，剩下的2k+1個(gè)機(jī)場(chǎng)個(gè)機(jī)場(chǎng)中，必存在一個(gè)機(jī)場(chǎng)中，必存在一個(gè)機(jī)場(chǎng)P沒有飛機(jī)降落。沒有飛機(jī)降落。 再把再把“撤出撤出”的兩機(jī)場(chǎng)復(fù)歸，則機(jī)場(chǎng)的兩機(jī)場(chǎng)復(fù)歸，則機(jī)場(chǎng)P仍無飛機(jī)降落，仍無飛機(jī)降落， 得得n=k+1時(shí)命題仍成立。時(shí)命題仍成立。第二數(shù)學(xué)歸納法第二數(shù)學(xué)歸納法例舉例舉 例例4、有兩堆棋子，數(shù)目相等。兩人玩耍，每人可以在一堆里、有兩堆棋子，數(shù)目相等。兩人玩耍，每人可以在一堆里任意取幾棵，但不能同時(shí)在兩堆里取，規(guī)定取得最后一棵者勝。任意取幾棵，但不能同時(shí)在兩堆里取，規(guī)定取得最后一棵者勝。問先取者得勝，還是后取者可以得勝？試加以證明。問先取

4、者得勝，還是后取者可以得勝？試加以證明。 猜測(cè)猜測(cè)“后取者可以得勝后取者可以得勝”。 證明證明：（1）當(dāng)當(dāng)n=1時(shí)，必是后取者得勝。時(shí)，必是后取者得勝。 （2）假設(shè)當(dāng)）假設(shè)當(dāng)nk時(shí)命題成立，對(duì)于時(shí)命題成立，對(duì)于n=k+1，當(dāng)先取者在一堆里，當(dāng)先取者在一堆里取棋子取棋子m (1mk+1)顆時(shí)顆時(shí)， 后取者則在另一堆里取棋子后取者則在另一堆里取棋子m顆，兩堆棋子仍都是顆，兩堆棋子仍都是(k+1-m)顆。顆。 這樣就變成了這樣就變成了n=k+1-m的問題，按照歸納假設(shè)，后取者可以得的問題，按照歸納假設(shè)，后取者可以得勝，即勝，即n=k+1命題也成立。命題也成立。 由第二數(shù)學(xué)歸納法，證明了：對(duì)于任意正整

5、數(shù)由第二數(shù)學(xué)歸納法，證明了：對(duì)于任意正整數(shù)n，后取者按上后取者按上述策略都可以得勝。述策略都可以得勝。 思考：若兩堆棋子的數(shù)目不同，則思考：若兩堆棋子的數(shù)目不同，則先取者和后取者哪個(gè)有必勝先取者和后取者哪個(gè)有必勝的策略？的策略？案例案例1多面體歐拉公式多面體歐拉公式多面體歐拉公式的證明及其在平面上的推廣多面體歐拉公式的證明及其在平面上的推廣連通平面圖的特征連通平面圖的特征 外部面外部面“海洋海洋”，內(nèi)部，內(nèi)部面。面。 連通圖：圖中任意兩點(diǎn)都有連通圖：圖中任意兩點(diǎn)都有路相通路相通。 如果一個(gè)連通的平面圖如果一個(gè)連通的平面圖G有有V個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，E條邊，條邊，F(xiàn)個(gè)面，那個(gè)面，那么么V-E+F=2

6、。 對(duì)平面圖的邊數(shù)用數(shù)學(xué)歸納對(duì)平面圖的邊數(shù)用數(shù)學(xué)歸納法證明法證明如果一個(gè)連通的平面圖如果一個(gè)連通的平面圖G有有V個(gè)頂點(diǎn)，個(gè)頂點(diǎn)，E條條邊，邊，F(xiàn)個(gè)面，那么個(gè)面，那么V-E+F=2。 思考：思考：對(duì)對(duì)V,E,F哪個(gè)量進(jìn)行歸納哪個(gè)量進(jìn)行歸納比較合適？比較合適？ 對(duì)邊數(shù)對(duì)邊數(shù)E進(jìn)行歸納試試看！進(jìn)行歸納試試看！ 證明：證明： 1）若）若G只有只有1條邊條邊,則則 V=2,E=1,F=1,故故V-E+F=2成立。成立。 2）假設(shè)假設(shè)G為有為有k條邊的連通的平條邊的連通的平面圖，公式面圖，公式Vk-Ek+Fk=2成立成立。 考察考察G為（為（k+1）條邊時(shí)的情況。條邊時(shí)的情況。 即當(dāng)圖即當(dāng)圖G由由k條邊增

7、加條邊增加1條邊，使條邊，使它仍為連通圖時(shí)，有哪些情形？它仍為連通圖時(shí)，有哪些情形？連通平面圖連通平面圖G有有V-E+F=2成立成立 （2） 當(dāng)當(dāng)G為（為（k+1）條邊時(shí)條邊時(shí),只有兩種情形：只有兩種情形： 1）增加一個(gè)新頂點(diǎn)增加一個(gè)新頂點(diǎn)v/，則則v/必與圖中的一點(diǎn)必與圖中的一點(diǎn)v相連。相連。 此時(shí)，此時(shí)，Vk與與Ek都增加都增加1，而，而Fk不變，不變， 故故Vk+1-Ek+1+Fk+1 =(Vk+1)-(Ek+1)+Fk=Vk-Ek+Fk=2. 2）用一條邊連結(jié)圖中兩個(gè)頂點(diǎn)用一條邊連結(jié)圖中兩個(gè)頂點(diǎn)u和和v。 這時(shí)，這時(shí)，Ek和和Fk都增加都增加1，而頂點(diǎn)數(shù)，而頂點(diǎn)數(shù)Vk沒有變，沒有變， 故故Vk+1-Ek+