學(xué)必求其心得，業(yè)必貴于專(zhuān)精學(xué)必求其心得，業(yè)必貴于專(zhuān)精學(xué)必求其心得，業(yè)必貴于專(zhuān)精數(shù)學(xué)歸納法一、數(shù)學(xué)歸納法最小數(shù)原理：已知，則，，使得。證明若是有限集，且，那么中元素可以按小到大的順序排列，取為其中最小的那個(gè)元素，則，,使得。若為無(wú)限集，且，那么是可列的，因而中元素可以按小到大的順序列出，取為其中最小的那個(gè)元素，則,,使得。綜上所述，若，則，，使得。定理：設(shè)A是一個(gè)非空集合，，對(duì),命題P(n)成立;假如，命題P（n）成立，能推出時(shí)，命題P(n)成立；則對(duì)，命題P(n）成立。證明(反證法)假設(shè)，使得P（）不成立;∵，則，使得，令,則，且；由最小數(shù)原理可知，B中定有最小正整數(shù)，，使得不成立。又∵，命題P（n)成立，∴≠1，那么-1≥2；由的假設(shè)可知，，P（n）成立。再由定理?xiàng)l件，命題P（n）成立,能推出時(shí)，命題P（n）成立知,,命題P（n)成立。這與B中定有最小正整數(shù)，，使得不成立矛盾。故原假設(shè)不成立。即定理結(jié)論成立.特別的：(1）第一數(shù)學(xué)歸納法取，當(dāng)n=1（即）時(shí)，P(1）成立，假如n=k（即)時(shí)，P（k)成立，能推出n=k+1（）時(shí)，P（k+1）成立；則對(duì)，命題P（n)成立。（2）第二數(shù)學(xué)歸納法取，，當(dāng)n=1（即）時(shí)，P（1）成立，假如(即）時(shí)，P（k）成立，能推出（）時(shí)，P（k+1）成立；則對(duì)，命題P（n）成立。（3)此為跳躍歸納法取，，…，（）,當(dāng)時(shí)，驗(yàn)證P（1），P（2），…,P(m）成立,假如時(shí),P［（k—1）m+1],P[（k-1）m+2］，…,P［(k—1)m+m］=P(km)成立，能推出當(dāng)時(shí)，P（km+1),P（km+2)，…,P［（k+1)m］成立;則對(duì),命題P(n）成立。m稱(chēng)為跨度.（4）倒退歸納法設(shè)，取，，…,，當(dāng)n=m（）時(shí)，P（m）成立；假如n=k（)（k＜m）時(shí)，P(k）成立，能推出n=k—1(）時(shí)，P(k-1）成立。則對(duì),命題P(n）成立.二、用數(shù)學(xué)歸納證明的方法（一）加大歸納的跨度例1由3角和5角的郵票，可以任意支付郵資n（n≥8）解當(dāng)n=8、9、10時(shí)，8=5+3、9=3×3、10=5×2，結(jié)論成立假設(shè)當(dāng)n=k時(shí),結(jié)論成立，即郵資k、k+1、k+2都可由3角和5角的郵票支付;那么當(dāng)n=k+3時(shí)，k+3=（k）+3、k+4=（k+1）+3、k+5=（k）+5，即結(jié)論成立所以由跳躍歸納法知，結(jié)論成立。例2證明:對(duì)任意正整數(shù),方程都有正整數(shù)解。證當(dāng)時(shí)，任取正整數(shù),，并取，則,，即為方程的一組解.當(dāng)時(shí)，取一組夠股數(shù)即可，例如。假設(shè)當(dāng)時(shí)命題成立，，,是方程的一組正整數(shù)解。取，，,則有,從而,，時(shí)方程的一組正整數(shù)解，即時(shí)命題也正確。所以對(duì)一切正整數(shù),命題正確。（二）起點(diǎn)前移或起點(diǎn)后移例3已知a，b是正實(shí)數(shù)，且QUOTE1a+1b=1。求證對(duì)一切正整數(shù)n，都有證n=1時(shí)，命題顯然成立。假設(shè)n=k時(shí)命題成立，即因?yàn)椋?。于?所以，從而，即命題在n=k+1時(shí)也成立綜上所述，對(duì)一切正整數(shù)n，命題都成立。例4已知對(duì)任意有QUOTEan>0且，求證:證當(dāng)n=1時(shí)，由及，得，命題成立.假設(shè)當(dāng)時(shí)，命題成立.即當(dāng)n=k+1時(shí)，因?yàn)镼UOTE又于是因?yàn)椋琷=1，2，…，k，所以又因?yàn)?，故。解得或（舍?.所以n=k+1時(shí)命題也成立.從而，，命題成立。例5將質(zhì)數(shù)由小到大編上序號(hào):，，,…求證：第個(gè)質(zhì)數(shù)。證當(dāng)時(shí)，,命題成立。假設(shè)時(shí)命題成立，即，將上面這個(gè)不等式相乘，得所以因?yàn)椋?…，都不能整除，所以的質(zhì)因數(shù)不可能是，，…，，只能大于或等于,于是有即綜上可知，對(duì)任何正整數(shù),都有.例6對(duì)怎樣的正整數(shù)，集合，…可以分成5個(gè)互不相交的子集，每個(gè)子集的元素和相等.解我們先找一個(gè)必要條件,若集合，…能分成5個(gè)互不相交的子集,各個(gè)子集的元素和相等，則…=能被5整除,所以或。顯然，當(dāng)時(shí)，上述條件不是充分的,下面用數(shù)學(xué)歸納法證明,當(dāng)時(shí)條件是充分的。當(dāng),即時(shí),我們將集合分別作如下分析：，…,，…=.當(dāng)，即時(shí),，…=,…=因?yàn)槿艏?…能分成5個(gè)互不相交的子集，且它們各自的元素和相等，則,……，也能分成5個(gè)互不相交的子集，且它們每個(gè)的元素和相等，事實(shí)上,若,…=,其中互不相交，的元素和與的元素和相等，則令，，,，，于是，…=,且互不相交,每個(gè)子集元素和相等。假設(shè)對(duì)于，，命題正確，由上面的討論知，對(duì)于，命題也成立，從而證得對(duì)于，或時(shí)，集合，…可以分成5個(gè)互不相交的子集，且它們各自的元素和相等。故命題得證。（三）先猜后證例7,當(dāng)n≥3時(shí),求證分析要證明，考慮余數(shù)不為0即可（m為某整數(shù))再考慮的前面幾項(xiàng)依次為：1、2、7;29、22、23;49、26、—17、—163；…………1、2、3；1、2、3；1、2、3;1、…（mod4)即猜想：（k≥0)，下面證明之證明當(dāng)k=0時(shí)，由分析可知結(jié)論成立假設(shè)對(duì)于k結(jié)論成立，即從而可知那么對(duì)于k+1時(shí),,即對(duì)于k+1時(shí)結(jié)論成立所以由數(shù)學(xué)歸納法知，，模4不同余于0，所以，即（四）加強(qiáng)命題例8設(shè)，求證：當(dāng)時(shí)，有。證我們把命題加強(qiáng)為……①當(dāng)時(shí)，，,故①式成立.假設(shè)時(shí)命題成立,即，則=+==+即當(dāng)時(shí)，①式也成立。所以，對(duì)正整數(shù),①式都成立,從而原命題也成立。（五）命題活化例9真分?jǐn)?shù)都可以表示成不同的正整數(shù)的倒數(shù)之和證明對(duì)m（<n）進(jìn)行歸納當(dāng)m=1時(shí)，，結(jié)論成立假設(shè)m＜k時(shí)，結(jié)論成立那么當(dāng)m=k時(shí)，若，則，結(jié)論成立.否則k不整除n則由帶余除法知,n=qk—r，qk=n+r（0＜r＜k，)從而①而r＜k，由歸納假設(shè)知，（）且（i=1，2,……s）否則為假分?jǐn)?shù)從而，且，故m=k時(shí)，,結(jié)論成立。由第二數(shù)學(xué)歸納法知，真分?jǐn)?shù)都可以表示成不同的正整數(shù)的倒數(shù)之和.注意：①式中不能直接用進(jìn)行歸納，否則,就不能保證，滿(mǎn)足不了題目要求。例10在20052005的方格表中任意去掉一格,證明:剩下的圖形一定可以用若干個(gè)“”型恰好蓋住它。證直接對(duì)20052005的方格表考慮比較困難，我們把命題一般化，證明對(duì)一切正整數(shù)，方格表滿(mǎn)足題設(shè)性質(zhì)(。當(dāng)時(shí)，對(duì)方格表，由于對(duì)稱(chēng)性，只需考慮去掉的方格為如圖8。1.1所示的帶陰影的方格。把它們分成三種情況,分別有圖8.1。2所示給出具體的蓋法。從而時(shí)命題成立。設(shè)時(shí)命題正確，我們考慮方格表.可知因?yàn)樽笊辖?、左下角、右上角、右下?個(gè)方格（有重疊)中至少有一個(gè)含有被去