A-level 數學/OCR/FP1/數學歸納法

數學歸納法證明 是一種演繹推理方法，可以產生完全嚴格的數學證明

• 步驟 1 證明結果對起始值成立，例如 $n=1$。這稱為基本情況。
• 步驟 2 假設結果對某個值成立，$k$
• 步驟 3 證明如果結果對 $n=k$ 成立，它對 $n=k+1$ 也成立。
• 步驟 4 總結命題對所有正整數都成立。

由於我們已經證明了結果對一般值 $k$ 成立，那麼如果我們證明它對下一個值 $k+1$ 成立，我們可以合乎邏輯地得出結論，它將對下一個值，下一個值，以及下一個值等等無限地成立。

一個例子

證明序列： $1+2+3+\cdots +n={\frac {n(n+1)}{2}}$

步驟 1： 當 $n=1$ : LHS = $1$ ，RHS = ${\frac {1(1\cdot 2)}{2}}=1$ 。因此，我們已經證明了假設對一個值成立…

步驟 2： 現在令 $n=k$ ，並證明這一點。

讓我們使用符號 $s$ 來表示級數 $1+2+3+\cdots +(k-2)+(k-1)+k$

然而，$s$ 也表示 $k+(k-1)+(k-2)+\cdots +3+2+1$ （這與同一個級數相同，但順序不同）

如果我們將這兩個級數加在一起，我們得到

$2s=(k+1)+(k+1)+(k+1)+\cdots +(k+1)+(k+1)+(k+1)=k(k+1)$

$s={\frac {k(k+1)}{2}}$

步驟 3： 現在令 $n=k+1$

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

但是，上面一行中*斜體*的部分已經是已知的。因此

$s+(k+1)={\frac {(k+1)(k+2)}{2}}$

${\frac {k(k+1)}{2}}+(k+1)={\frac {(k+1)(k+2)}{2}}$

當我們展開等式左側時，我們得到

${\frac {k^{2}}{2}}+{\frac {3k}{2}}+1={\frac {k^{2}+3k+2}{2}}={\frac {(k+1)(k+2)}{2}}$

步驟 4 等式左側等於右側，因此我們可以得出結論，根據數學歸納法的原理，由於它對 $n=1$ 成立，並且如果它對 $n=k$ 成立，那麼它對 $n=k+1$ 成立，它對任何正整數都成立。

另一個例子

證明序列： $\sum {r^{2}}={\frac {n(n+1)(2n+1)}{6}}$

步驟 1

證明當 $n=1$ 時成立

$1^{2}={\frac {1(1+1)(2+1)}{6}}$

$1={\frac {6}{6}}$

LHS = RHS 因此成立

步驟 2

假設當 $n=k$ 時成立

$1+4+9+\cdots +k^{2}={\frac {k(k+1)(2k+1)}{6}}$

步驟 3

證明當 $n=k+1$ 時成立

$1+4+9+\cdots +k^{2}+(k+1)^{2}={\frac {(k+1)(k+1+1)(2(k+1)+1)}{6}}$

我們假設 $1+4+9+\cdots +k^{2}={\frac {k(k+1)(2k+1)}{6}}$ 是正確的。因此，我們現在可以假設 ${\frac {k(k+1)(2k+1)}{6}}+(k+1)^{2}={\frac {k(k+1)(k+1+1)(2(k+1)+1)}{6}}$

也將是正確的。但是這次我們需要證明它。這一部分可能會讓人困惑，但我們所要做的就是重新排列等式的兩邊，這樣我們就可以看到它們是相等的。

${\frac {(k+1)(k(2k+1)+6(k+1))}{6}}={\frac {(k+1)((k+1+1)(2(k+1)+1))}{6}}$ (左側：提取了 ${\tfrac {k+1}{6}}$ ) (右側：無)

${\frac {(k+1)(2k^{2}+7k+7)}{6}}={\frac {(k+1)((k+2)(2k+3))}{6}}$ (左側：展開括號) (右側：簡化括號)

${\frac {(k+1)(k+2)(2k+3)}{6}}={\frac {(k+1)((k+2)(2k+3))}{6}}$ (左側：分解括號) (右側：無)

右側 = 左側，因此正確

這是 FP1 (A-level 數學 的進一步純粹數學 1 模組) 的一部分。