數(shù)學(xué)歸納法的應(yīng)用
數(shù)學(xué)歸納法的應(yīng)用非常廣泛,在實際的教學(xué)研究中也得到了很大的重視 接下來學(xué)習(xí)啦小編為你整理了數(shù)學(xué)歸納法的應(yīng)用,一起來看看吧。
數(shù)學(xué)歸納法的原理
數(shù)學(xué)歸納法是一種研究與自然數(shù)有關(guān)的證明,它可以巧妙的證明結(jié)果含有n的結(jié)論。它避免了無窮次的步驟推導(dǎo)引起的邏輯問題,是一種嚴(yán)格的演繹推理,所以它與普通的歸納法有著很大的區(qū)別。已知最早的使用數(shù)學(xué)歸納法的證明出現(xiàn)于F·莫羅利科(Francesco Maurolico)的《算數(shù)》(Arithmeticorum libri duo)(1575AD)。莫羅利科利用遞推關(guān)系巧妙地證明出前n個奇數(shù)的總和是n^2,由此總結(jié)出了數(shù)學(xué)歸納法。
數(shù)學(xué)歸納法最基本格式為:(1)n= n0時,成立。(2)假設(shè)n= k時成立,當(dāng)n=k+1時命題也成立。于是根據(jù)(1)(2)可知命題對于任意n成立。舉個例子,就像一排多米諾骨牌(這個例子很經(jīng)典形象),我們知道第一個被推倒了,我們也知道每一個與之相鄰的下一個骨牌要倒,那么你就可以推斷所有的的骨牌都將要倒。
如:證1+2+3+„+n=n*(n+1)/2 。按順序1.當(dāng)n=1時,顯然成立。2.假設(shè)n=k時成立,當(dāng)n=k+1時,S= k*(k+1)/2+(k+1) = (k+2) (k+1)/2. 于是結(jié)果成立。
數(shù)學(xué)歸納法的應(yīng)用
1. 所有馬都一個顏色。(即任意n匹馬都只有一個顏色)
證:當(dāng)只有1匹馬,命題成立。假設(shè)任意k匹馬都只有一個顏色,當(dāng)n=k+1時,我從中任意挑取k匹馬,這k匹馬顏色相同;我再用剩下的那只馬去換掉這群馬中的任意一只,組成新的馬群,依然有k匹馬,顏色還是相同;根據(jù)集合交并原理,可知k+1時也成立。證畢。
原來真的所有馬都一種顏色嗎?怎么可能!現(xiàn)在,我們來分析一下究竟是哪里出的錯。我們可以看到,在第二步,當(dāng)k=1時,兩匹馬不能出現(xiàn)交集,不能推出k=2時成立。這個證明鏈在第二節(jié)斷掉了,雖然后面是連著的,但卻推不出正確結(jié)論了。所以這提示我們,即使前面第一步證明了n=1成立,第二步依然要保證n=k對任意所涉及的數(shù)也成立,包括1.
2.n人一人一頂帽子,有m頂白帽子,其余都是黑帽子。每次敲鐘,都要求所有能判斷自己為白帽子的人離開。正在這n個無聊的人苦苦思索的時候,突然來了一個人,說:“這里居然有人帶白帽子!”,然后飄走了。黑帽子的人很想說“廢話!”,卻發(fā)現(xiàn)過了一會所有白帽子的人都走了(他們判斷出自己的帽子顏色了),這是怎么回事?
好吧,我們還是用數(shù)學(xué)歸納法做一做:
命題1:我們假設(shè)只有1人白帽子,他發(fā)現(xiàn)所有人都戴黑帽子,當(dāng)飄走的那個人說完話后,他可以立刻知道自己是白的。于是第1聲鐘響后這1個白帽可確認(rèn)。
命題2:假設(shè)只有2個人白,其中一個人發(fā)現(xiàn)有只有1個人白帽,如果命題1成立,即只有他是白帽,他應(yīng)該鐘響1下后立刻離開,可他不走。所以說明命題1不成立,一定有2個白帽——自己和他!于是第2聲鐘響后這2個白帽可確認(rèn)。
假設(shè)命題k成立,命題n=k+1時,假設(shè)只有k+1個白帽,其中一人發(fā)現(xiàn):有k個白帽,如果是命題k,他們在第k聲鐘響后應(yīng)該全部離開,可是沒走,所以一定自己是白帽子讓他們不能判斷。于是在第k+1聲鐘響后,k+1白帽可全部確認(rèn)離開。結(jié)論成立。
所以,那句廢話雖然對黑帽子沒有,但對白帽子而言是卻是歸納法的第一塊多米諾骨牌。
3.在《不可思議?》這本書里還有一個更那啥的題,經(jīng)改編如下:有一個殺人狂把兩個人分別關(guān)在兩個密室,分別告訴他們兩個相鄰正自然數(shù),兩個人雖然知道數(shù)字相鄰,卻不知道對方的數(shù)。計時開始后,每分鐘他們都有一次機(jī)會選擇確認(rèn)按鈕,確認(rèn)的消息可以被雙方聽見。只有知道另一方數(shù)字是多少的人才能出去。快快,生路在哪里?
這看起來好像無解,假如我知道自己的數(shù)是27,怎么判斷對方究竟是26還是28,難道出去的概率是50%?
不,概率是100%,唯一的生路在那個每分鐘一次確認(rèn)按鈕上(且確認(rèn)消息可通知雙方)。當(dāng)A的數(shù)是1,則在第1分鐘便可知道B的數(shù)是2(因為不是0)。當(dāng)A的數(shù)是2,則有兩種情況,B是1或3,如果是1,B在第一分鐘會確認(rèn),如果B沒確認(rèn),則B是3。所以假設(shè)當(dāng)A為k時,A會在第k分鐘推理出B的數(shù)字,則當(dāng)A=k+1時,如果第k分鐘B沒有動靜,則可以判斷B的數(shù)不是k,而是k+2,所以在下一分鐘即k+1分鐘時A推理出數(shù)字,結(jié)論成立。