用戶:Dz902/沙盒/數學歸納法

數學歸納法是一種數學證明方法，通常被用於證明某個給定命題在整個（或者局部）自然數範圍內成立。除了自然數以外，廣義上的數學歸納法也可以用於證明一般良基結構，例如：集合論中的樹。這種廣義的數學歸納法應用於數學邏輯和計算機科學領域，稱作結構歸納法。

需要留意的是，數學歸納法雖然名字中有「歸納」，但是實際上數學歸納法並不屬於不嚴謹的歸納推理法，實際上是屬於完全嚴謹的演繹推理法。

定義

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

骨牌一個接一個倒下，就如同一個值到下一個值的過程。

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

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

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

$1+2+3+\cdots +n={\frac {n(n+1)}{2}}$

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

第一步證明的是這個公式在 n = 0 時成立（即 P(0) 成立）。這裏要注意的是 0 = 0，而 0(0 + 1) / 2 = 0，所以這個公式在 n = 0 時成立。證明的第一步完成。

第二步我們需要證明如果假設 n = m 時公式成立（即 P(m) 成立），那麼可以推導出 n = m+1 時公式也成立（即 P(m+1) 成立）。證明步驟如下。

我們先假設 n = m 時公式成立。即

$1+2+\cdots +m={\frac {m(m+1)}{2}}$ （等式 1）

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

$1+2+\cdots +m+(m+1)={\frac {m(m+1)}{2}}+(m+1)$ （等式 2）

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

$={\frac {m(m+1)}{2}}+{\frac {2(m+1)}{2}}={\frac {(m+2)(m+1)}{2}}={\frac {(m+1)(m+2)}{2}}={\frac {(m+1)((m+1)+1)}{2}}.$

也就是說

$1+2+\cdots +(m+1)={\frac {(m+1)((m+1)+1)}{2}}$

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

在這個證明中，歸納推理的過程如下：

在應用，數學歸納法常常需要採取一些變化來適應實際的需求。下面介紹一些常見的數學歸納法變體。

如果我們想證明的命題並不是針對全部自然數，而只是針對所有大於等於某個數字 b 的自然數，那麼證明的步驟需要做如下修改：

用這個方法可以證明諸如「當 n ≥ 3 時，n² > 2n」這一類命題。