原理

最簡單和常見的數學歸納法是證明當n等於任意一個自然數時某命題成立。證明分下面兩步：

證明當n= 1時命題成立。

假設n=m時命題成立，那麼可以推匯出在n=m+1時命題也成立。（m代表任意自然數）

這種方法的原理在於：首先證明在某個起點值時命題成立，然後證明從一個值到下一個值的過程有效。當這兩點都已經證明，那麼任意值都可以透過反覆使用這個方法推匯出來。把這個方法想成多米諾效應也許更容易理解一些。例如：你有一列很長的直立著的多米諾骨牌，如果你可以：

證明第一張骨牌會倒。

證明只要任意一張骨牌倒了，那麼與其相鄰的下一張骨牌也會倒。

那麼便可以下結論：所有的骨牌都會倒下。

這種方法的原理在於第一步證明起始值在表示式中是成立的，然後證明一個值到下一個值的證明過程是有效的。如果這兩步都被證明了，那麼任何一個值的證明都可以被包含在重複不斷進行的過程中。 　　

簡介

數學歸納法是一種重要的論證方法。它們通常所說的“數學歸納法”大多是指它的第一種形式而言，本文想從最小數原理出發，對它的第二種形式即第二數學歸納法進行粗略的探討，旨在加深對數學歸納法的認識。

原理

第二數學歸納法

第二 數學歸納法原理是設有一個與正整數n有關的命題，如果：

（1）當n=1時，命題成立；

（2）假設當n≤k（k∈N）時，命題成立，由此可推得當n=k+1時，命題也成立。

那麼根據①②可得，命題對於一切正整數n來說都成立。

證明

用反證法證明。

假設命題不是對一切自然數都成立。命N表示使命題不成立的自然數所成的集合，顯然N非空，於是，由最小數原理N中必有最小數m，那麼m≠1，否則將與（1）矛盾。所以m－1是一個自然數。但m是N中的最小數，所以m－1能使命題成立。這就是說，命題對於一切≤m－1自然數都成立，根據（2）可知，m也能使命題成立，這與m是使命題不成立的 自然數集N中的最小數矛盾。因此定理獲證。

當然，定理2中的（1），也可以換成n等於某一整數k。

對於證明過程的第一個步驟即n=1（或某個整數a）的情形無需多說，只需要用n=1（或某個整數a）直接驗證一下，即可斷定欲證之命題的真偽。所以關鍵在於第二個步驟，即由n≤k到n=k+1的驗證過程。事實上，我們不難從例1的第二個步驟的論證過程中發現，證明 等式在n=k+1時成立是利用了假設條件；等式在n=k及n=k－1時均需成立。同樣地，例2也不例外，只是形式的把n=k及n=k－1分別代換成了n=k－1和n=k－2。然而例3就不同了，第二個步驟的論證過程，是把論證命題在n=k+1時的成立問題轉化為驗證命題在n=k－2+1時的成立問題。換言之，使命題在n=k+1成立的 必要條件是命題在n=k－2+1時成立，根據1的 取值範圍，而命題在n=k－k+1互時成立的實質是命題對一切≤k的自然數n來說都成立。這個條件不是別的，正是第二個步驟中的歸納假設。以上分析表明，假如論證命在n=k+1時的真偽時，必須以n取不大於k的兩個或兩個以上乃至全部的自然數時命題的真偽為其論證的依據，則一般選用第二 數學歸納法進行論證。之所以這樣，其根本原則在於第二數學歸納法的歸納假設的要求較之 第一數學歸納法更強，不僅要求命題在n=k時成立，而且還要求命題對於一切小於k的自然數來說都成立，反過來，能用第一數學歸納法來論證的數學命題，一定也能用第二數學歸納進行證明，這一點是不難理解的。不過一般說來，沒有任何必要這樣做。

第二數學歸納法和第一數學歸納法一樣，也是數學歸納法的一種表達形式，而且可以證明第二數學歸納法和第一數學歸納法是等價的，之所以採用不同的表達形式，旨在更便於我們應用。

遞推的基礎：證明當n=1時表示式成立。 　　遞推的依據：證明如果當n=m時成立，那麼當n=m+1時同樣成立。 　　這種方法的原理在於第一步證明起始值在表示式中是成立的，然後證明一個值到下一個值的證明過程是有效的。如果這兩步都被證明了，那麼任何一個值的證明都可以被包含在重複不斷進行的過程中。 　　或許想成多米諾效應更容易理解一些，如果你有一排很長的直立著的多米諾骨牌那麼如果你可以確定： 　　第一張骨牌將要倒下，只要某一個骨牌倒了，與之相鄰的下一個骨牌也要倒，那麼你就可以推斷所有的的骨牌都將要倒。 　　這樣就確定出一種遞推關係，只要滿足兩個條件就會導致所有骨牌全都倒下： 　　（1）第一塊骨牌倒下； 　　（2）任意兩塊相鄰骨牌，只要前一塊倒下，後一塊必定倒下。 　　這樣，無論有多少骨牌，只要保證（1）（2）成立，就會全都倒下。