1．數學歸納法的理論依據
歸納法和演繹法都是重要的數學方法．歸納法中的完全歸納法和演繹法都是邏輯方法；不完全歸納法是非邏輯方法，只適用於數學發現思維，不適用數學嚴格證明．
數學歸納法既不是歸納法，也不是演繹法，是一種遞迴推理，其理論依據是下列佩亞諾公理ⅰ—ⅴ中的歸納公理：
ⅰ．存在乙個自然數0∈n；
ⅱ．每個自然數a有乙個後繼元素a′，如果a′是a的後繼元素，則a叫做a′的生成元素；
ⅲ．自然數0無生成元素；
ⅳ．如果a′=b′，則a=b；
ⅴ．(歸納公理)自然數集n的每個子集合m，如果m含有0，並且含有m內每個元素的後繼元素，則m＝n
自然數就是滿足上述佩亞諾公理的集合n中的元素．關於自然數的所有性質都是這些公理的直接推論．由佩亞諾公理可知，0是自然數關於「後繼」的起始元素，如果記0′＝1，1′=2，2′=3，…，n′=n＋1，…，則
n=｛0，1，2，…，n，…｝
由佩亞諾公理所定義的自然數與前面由集合所定義的自然數，在本質上是一致的．90年代以前的中學數學教材中，將自然數的起始元素視作1，則自然數集即為正整數集．現在已統一採取上面的記法，將0作為第乙個自然數．
定理1(最小數原理)自然數集n的任一非空子集a都有最小數．
這本是自然數集n關於序關係∈(＜)為良序集的定義．現在用歸納公理來證明．
證設m是不大於a中任何數的所有自然數的集合，即
m=｛n｜n∈n且n≤m，對任意m∈a｝
由於a非空，至少有一自然數a∈a，而 a＋1(＞a)不在m中．所然，就有
1° 0∈m(0不大於任一自然數)；
2° 若m∈m，則m＋1∈m．
根據歸納公理，應有m＝n．此與m≠n相矛盾．
這個自然數m0就是集合a的最小數．因為對任何a∈a，都有m0意a∈a，於是m0＋1∈m，這又與m0的選取相矛盾．
反之，利用最小數原理也可以證明歸納公理．因此，最小數原理與歸納公理是等價的．
定理2(數學歸納法原理)乙個與自然數相關的命題t(n)，如果
1° t(n0)(n0≥0)為真；
2° 假設t(n)(n≥n0)為真，則可以推出t(n＋1)也為真．
那麼，對所有大於等於n0的自然數n，命題t(n)為真．
證用反證法．若命題t(n)不是對所有自然數n為真，則
m=｛m｜m∈n，m≥n0且t(m)不真｝
非空．根據定理1，m中有最小數m0．由1°， m0＞n0，從而m0－1≥n0且t(m0-1)為真．由2°，取n=m0-1即知t(m0)為真．此與t(m0)不真相矛盾．從而證明了定理2．
在具體運用數學歸納法進行數學證明時，有多種不同形式．運用定理2中兩個步驟進行證明的，為ⅰ型數學歸納法．經常使用的還有ⅱ型數學歸納法，ⅱ型數學歸納法是：
如果命題t(n)滿足
1° 對某一自然數n0≥0，t(n0)為真；
2° 假設對n0≤k≤n的k， t(k)為真，則可以推出 t(n＋1)也真．
那麼．對所有大於等於n0的自然數，命題t(n)都真．
定理3 ⅰ型數學歸納法和ⅱ型數學歸納法等價．
證假設命題 t(n)對n=n0為真，於是只須證明「由t(n)(n≥n0)為真，可以推出t(n＋1)也為真」的充要條件為「由t(k)(n0≤k≤n)為真，可以推出t(n+1)也為真．」
1° 充分性
若「由t(n)(n≥n0)為真，可以推出 t(n＋1)也為真」，則對n0≤k≤n，t(k)為真，特別 t(n)為真，因此 t(n＋1)也為真．
2° 必要性
用反證法．若「由 t(k)(n0≤k≤n)為真，可以推出 t(n＋1)也為真」，但並非對所有大於等於n0的自然數n，由t(n)為真，可以推出 t(n＋1)也為真，則 m=｛m｜m∈n， m≥n0且由t(n)為真推不出t(n＋1)也為真｝非空．由定理1，m中有最小數m0，且對n0≤k＜m0的k，由t(k)為真，可以推出t(k＋1)也為真．特別由 t(n0)為真可知 t(n0+1)為真，由t(n0＋1)為真可知 t(n0＋2)為真，……，由t(m0－1)為真可知 t(m0)為真．現已知t(n0)為真，所以t(n0)， t(n0+1)，…， t(m0)都為真，由此可知 t(m0＋1)也為真，所以由 t(m0)為真推出了t(m0＋1)也為真．這與m0的選取矛盾．
由定理3可知，ⅱ型數學歸納法也是合理的推理方法．
2．數學歸納法在應用中要注意的問題
第一，證明的兩個步驟缺一不可第一步是歸納的基礎，第二步是歸納的傳遞．尤其是不可忽視第一步的驗證．
例1試證
1＋3＋5＋…＋(2n＋1)＝(n＋1)2＋1
證假設當n=k時公式成立，則
1＋3＋5＋…＋(2n-1)＋(2n+1)
1＋3＋5＋…＋(2n-1)］＋(2n＋1)
n2＋1＋2n＋1＝(n＋1)2＋1
完成了數學歸納法的第二步，但結論顯然是錯誤的．為什麼？因為缺少第一步．事實上，當n=0時，公式不成立．
如果缺了第二步，則不論對多少個自然數來驗證命題t(n)的正確性，都不能肯定命題對所有自然數都正確．例如，哥德**猜想「任何不小於6的偶數都可以表成兩個奇素數之和」，雖然對大量偶數進行了具體驗證，但因缺少第二步歸納傳遞，所以仍只停留在歸納的第一步上．它至今仍只是個猜想而已．
第二，第二步在證明t(n＋1)為真時，一定要用到歸納假設，即要把「t(n)為真推出 t(n＋1)為真」或「t(n0)， t(n0＋1)，…，t(k-1)為真推出t(k)為真」的實質蘊含真正體現出來．否則不是數學歸納法證明．
例2 設a1，…，an為n個正數，b1，…，bn是它的乙個排列．試證
證1°當n=1時，命題顯然成立．
2°假設(*)式對n=k成立，則當n=k＋1時
根據數學歸納法原理，(*)式對所有大於等於1的自然數n都成立．
這裡雖然形式上完成了數學歸納法的兩個步驟，但第二步在證(*)式對n＋1成立的過程中，並沒用到(*)對n成立的歸納假設．因此，不能說上述證法是採用了數學歸納法．事實上，在上述證明中無須用數學歸納法，用平均值不等式證明就行了．
第三，並不是凡與自然數相關的命題t(n)，都要用數學歸納法來證明；而且也不是所有這類命題都能用數學歸納法給以證明的．
這一命題是與自然數相關的命題，儘管可以對n＝0，1，2，…進行驗證，但無法實現數學歸納法的第二步，因此不能用數學歸納法進行證明．
事實上，數學歸納法只適用於具有遞迴性的命題t(n)．
3．遞迴函式
乙個定義在自然數集n上的函式f(n)，如果它對於每個自然數n的值可以用如下方式確定：
(1)f(0)=a(a為已知數)；
(2)存在遞推關係組s，當已知/f(0)，f(1)，…，f(n-1)值以後，由s唯一地確定出f(n)的值：
f(n)=s［f(0)，f(1)，…，f(n-1)］
那麼，就把這個函式f(n)，稱作歸納定義的函式．簡稱遞迴函式．
在具體的遞迴函式例子中，關係組s可能有幾個表示式，或者沒有明確的解析表示式，也可能需要給出f(n)的開頭若干個值．
這樣定義函式是合理的，因為我們有：
定理4 當遞推關係組s給定後，定義在n上的滿足上述條件(1)、(2)的函式f(n)是存在而且唯一的．
證首先指出：對任一自然數k，總可以在片斷｜0，k｜上定義乙個函式fk(n)，使fk(0)=a，對於片斷上其他自然數 n，f(n)=s［f(0)，…，f(n-1)］．這個函式fk(n)是在｜0，k｜上唯一確定的．
現對k進行歸納證明：
1° 當k＝0時，f0(0)＝a是唯一確定的；
2°假定在｜0，k｜上已經由(1)、(2)定義了乙個唯一確定的函式fk(n)，令
則fk+1(n)在片斷｜0，k＋1｜上有定義，且
(1)fk+1 (0)=fk(0)=a；
(2)fk+1(n)=s［fk(0)，…，fk(n－1)］
=s［fk+1(0)，…，fk+1(n－1)］，
n=1，2，…，k．
因此，函式人fk+1(n)滿足條件(1)、(2)．由數學歸納法知，對任何自然數k，函式fk(n)在片斷｜0，k｜上唯一確定，且滿足(1)、(2)．又若k1＜k2，則 fk1(n)與fk2(n)在片斷｜0，k1｜上完全一致．
現作一新的函式：f(n)=fn(n)， n∈n．
首先，函式f(n)對任一n∈n都有定義，且
f(n)=fn(n)=s［fn－1(0)，…，fn-1(n－1)］
=s［f0(0)，…，fn-1(n-1)］
=s［f(0)，…，f(n-1)］
又顯然f(0)＝f0(0)=a．故函式f(n)是定義在n上且滿足(1)、(2)的唯一確定的函式．
例4 設函式f∶n→n，且
(1) f(0)=2，f(1)=3；
(2) f(n＋1)＝3f(n)－2f(n－1)，n≥1．
證明： f( n)＝2n＋1．
這裡給出的遞迴函式由f(0)、f(1)兩個值和乙個關係式給定的關係組s確定．但有的遞迴函式f(0)的值隱含於關係組s之中而未直接給出．
例5(imo－19試題)設f：n+→n＋，且
(s) f(n＋1) ＞ f(f(n))， n∈n+
求證：對於任意n∈n＋，f(n)＝n．
證先用數學歸納法證明命題an：任意正整數n，若m≥n，則f(m)≥ n．
顯然 a1真．假設an-1真，則對任意m≥n，f(m－1)≥n-1，故f(m)＞f(f(m－1))≥2n－1，於是f(m)≥n，從而 an真．
由此可知，f(n)≥n，f(n＋1)＞f(f(n))≥f(n)．於是f單調增加．又如果有乙個n使f(n)＞n，則f(n)≥n+1，f(f(n))≥f(n+1)，與已知條件(s)矛盾．故只能有 f(n)=n．
本題給出的遞迴函式，f(1)的值沒有明顯給出，但實際上隱含於關係組(s)中．
4．遞迴命題
乙個與自然數相關的命題t(n)，一般來說，它未必是乙個函式問題．現在採取如下方式來構造命題t(n)的真值函式f∶n→｛1，0｝．
如果命題t(n)的真值函式f(n)是遞迴函式，即
1° f(0)=1；
2° f(n＋1)= s［f(0)，…，f(n)］，且當f(0)=…=f(n)=1時， f( n＋1)=1．
數學歸納法
數學歸納法製作人 徐凱 精講部分 年級 高三科目 數學型別 同步 難易程度 中建議用時 20 25min 一.知識點 1 數學歸納法的定義 一般地，證明乙個與正整數n有關的命題，可按下列步驟進行 只要完成這兩個步驟，就可以斷定命題對從n0開始的所有正整數n都成立 這種證明方法叫做數學歸納法 2 數學...
數學歸納法
最小數原理 已知，則，使得。證明若是有限集，且，那麼中元素可以按小到大的順序排列，取為其中最小的那個元素，則，使得。若為無限集，且，那麼是可列的，因而中元素可以按小到大的順序列出，取為其中最小的那個元素，則，使得。綜上所述，若，則，使得。定理 設a是乙個非空集合，對，命題p n 成立 假如，命題p ...
數學歸納法 整理
數學歸納法 資料 學歸納法證明與遞迴定義法的合法性依據 如何避免乙個表面上的 惡性迴圈 即用歸納法定義自然數，然後由此出發來證明自然數上數學歸納法的可行性?算術理論的形式展開 乙個少年時代的疑問之終結 如何嚴格證明加法與乘法的結合律，交換律與分配律?定律 postulates 轉化為 定理 theo...