為甚麼需要歸納法
MATH1025 中不少命題不是關於某一個數，而是關於所有正整數。例如
13+23+⋯+n3=(2n(n+1))2
在 n=1,2,3,4 時都成立，但這仍然只是有限次檢查。命題真正聲稱的是
無限多個情況同時成立。數學歸納法正是把「一個起點」和「可重複的下一步」
合成為完整證明的原理。
核心直覺是：如果第一個命題是真的，而且每一個真命題都必然推出下一個，
那麼這條鏈便不能中斷。
以整數為索引的命題
定義
索引命題
索引命題是一族命題 P(n)，其中每一個允許的整數 n 都對應一個命題。
P(n) 可以在某些 n 成立，在另一些 n 不成立。
寫歸納證明前，必須先清楚寫出 P(n) 是甚麼。否則很容易在證明途中使用了
一個沒有明確內容的「歸納假設」。
定理
數學歸納法原理
設 P(n) 是每個 n∈Z+ 對應的一個命題。若：
P(1) 成立；- 對任意整數 k≥1，若
P(k) 成立，則 P(k+1) 成立；
則 P(n) 對所有 n∈Z+ 成立。
第二項不是直接宣稱 P(k+1) 成立，而是在假設 P(k) 的條件下證明
P(k+1)。這是歸納步驟最重要的邏輯位置。
標準證明格式
一個完整的歸納證明通常包含四部分：
- 定義
P(n)；
- 驗證基本情況；
- 假設某個任意的
P(k) 成立，並推出 P(k+1)；
- 引用歸納法原理作結。
這些步驟不是形式主義，而是讓讀者看清無限命題如何被證明。
例題
立方和公式
證明對所有 n∈Z+，
13+23+⋯+n3=4n2(n+1)2.令 P(n) 為上述等式。當 n=1 時，左邊為 1，右邊為
412(1+1)2=1,所以 P(1) 成立。
現在假設 P(k) 對某個 k≥1 成立，即
13+23+⋯+k3=4k2(k+1)2.則
13+⋯+k3+(k+1)3=4k2(k+1)2+(k+1)3=(k+1)2(4k2+k+1)=(k+1)24(k+2)2.這正是 P(k+1)。因此，根據數學歸納法，公式對所有正整數成立。
關鍵不是單純代數化簡，而是把前 k 項的和用歸納假設替換。
整除命題
歸納法也常用於整除命題。
定義
整除
若 m,n∈Z，且存在 q∈Z 使得 m=nq，則稱 m 被 n 整除，
記作 n∣m。
例題
一個整除證明
證明對所有 n∈Z+，3∣(n3−n)。
令 P(n) 為命題 3∣(n3−n)。當 n=1 時，
13−1=0=3⋅0，所以基本情況成立。
假設 P(k) 成立，即 k3−k=3q，其中 q∈Z。則
(k+1)3−(k+1)=k3+3k2+3k+1−k−1=(k3−k)+3k2+3k=3q+3k2+3k=3(q+k2+k).因為 q+k2+k 是整數，所以 P(k+1) 成立。
常見失誤
常見錯誤
歸納步驟必須接得上基本情況
若一個歸納論證在 n=1 到 n=2 的過渡已經失效，即使之後的語句看似有
道理，也不能證明任何無限命題。基本情況和第一個歸納過渡必須真正連接。
常見錯誤
有限例子不是證明
驗算 P(1), P(2), P(3) 可以幫助發現規律，但不能代替歸納步驟。
證明必須處理任意的 k。
變形
若命題從 n0 開始，基本情況就是 P(n0)，歸納步驟要從任意
k≥n0 推到 k+1。若命題分奇偶，也可用 P(k) 推 P(k+2)，
但必須分別處理相應的起點。
定理
強歸納法
若 P(1) 成立，且對每個 k≥1，從
P(1),P(2),…,P(k) 全部成立可推出 P(k+1)，則 P(n) 對所有
n∈Z+ 成立。
強歸納法適合下一步需要依賴多個較早情況的證明。
快速檢查
快速檢查
在歸納步驟中，P(k) 和 P(k+1) 的角色有何不同？
快速檢查
為甚麼只檢查 n=1,2,3 不能證明所有正整數情況？
快速檢查
若命題聲稱對所有 n≥5 成立，基本情況應該是哪一個？
練習
- 用歸納法證明
1+2+\cdots+n=n(n+1)/2。
- 證明對所有 n∈Z+，4∣(5n−1)。
- 證明對所有整數 n≥5，n2<2n。
- 說明「重疊子集」的錯誤歸納證明為何在第一個非平凡步驟失效。
引導解答
- 在歸納步驟中，把 k+1 加到
1+\cdots+k=k(k+1)/2 兩邊並化簡。
- 若 5k−1=4q，則 5k+1−1=5(4q+1)−1=4(5q+1)。
- 從 n=5 開始。若 k2<2k，且 k≥5，則利用
2k+1<2k 得 (k+1)2<2k+1。
- 從一個物件到兩個物件時，兩個一元素子集沒有重疊，因此不能把性質傳遞過去。