第一數學歸納法

第一數學歸納法可以概括為以下三步：

(1)歸納奠基：證明時命題成立；

(2)歸納假設：假設時命題成立；

(3)歸納遞推：由歸納假設推出時命題也成立．

從而就可斷定命題對於從所有正整數都成立。

數學歸納法的正確性證明：

假設我們已經完成下面的推理

歸納基礎：P(0)真；

歸納推理：對於任意

但是還並非所有自然數都有性質P。

將這些不滿足性質P的自然數構成一個非空自然數子集，這樣，子集中必定有一個最小的自然數，設為m。

顯然，記做，這樣n一定具有性質P，即P(n)為真

存在對於任意的不滿足╞╡對於任意的不滿足

假設推理結果與已經完成的歸納推理矛盾，所以假設錯誤。

所有自然數都有性質P。

假設我們要證明下面這個公式（）：

其中n 為任意自然數。這是用於計算前n 個自然數的和的簡單公式。證明這個公式成立的步驟如下。

第一步是驗證這個公式在時成立。我們有左邊 = 1，所以這個公式在 時成立。第一步完成。

第二步

第二步我們需要證明如果 假設 時公式成立，那麼可以 推導出時公式也成立。證明步驟如下。

我們先假設時公式成立。即（等式 1）

然後在等式等號兩邊分別加上得到

（等式 2）

這就是 時的等式。我們現在需要根據等式 1 證明等式 2 成立。通過因式分解合併，等式 2 的右手邊

也就是說這樣便證明了從 P(m) 成立可以推導出 也成立。證明至此結叢，結論：對於任意自然數n，P(n) 均成立。