第五章：歸納法
歸納法是證明關於無限集合（通常是自然數）命題的最強大工具。它與第二章的良序原理在邏輯上是等價的，但在應用上更為直觀。
5.1 普通歸納法原理
歸納法原理：
若要證明對所有非負整數 $n$，命題 $P(n)$ 為真，只需證明兩件事：
若要證明對所有非負整數 $n$，命題 $P(n)$ 為真，只需證明兩件事：
- 基礎步驟： $P(0)$ 為真。
- 歸納步驟： 對於所有 $n$，若 $P(n)$ 為真，則 $P(n+1)$ 也為真。
這就像是一排無限長的多米諾骨牌：
- 基礎步驟證明了你推倒了第一塊骨牌。
- 歸納步驟證明了如果任何一塊骨牌倒下，它會撞倒下一塊。
- 結論：所有骨牌都會倒下。
🧪 歸納法多米諾模擬器
點擊下方按鈕，觀察歸納法的兩個步驟如何協同工作。
5.2 強歸納法
有時候，為了證明 $P(n+1)$，僅僅依靠 $P(n)$ 是不夠的，我們可能需要用到 $P(0), P(1), ..., P(n)$ 這些所有的前置結論。
強歸納法原理：
- 基礎步驟： $P(0)$ 為真。
- 歸納步驟： 對於所有 $n$，若 $P(0), P(1), ..., P(n)$ 全部都為真，則 $P(n+1)$ 也為真。
視覺化比較
普通歸納法： 當前一步成立 $\rightarrow$ 下一步成立。
強歸納法： 之前所有步驟成立 $\rightarrow$ 下一步成立。
何時使用強歸納法？
例如在證明「每個大於 1 的整數都可以分解為質數乘積」時，為了證明 $n$ 可以分解，我們可能需要利用比 $n$ 小的某個因數的性質，而不僅僅是 $n-1$。
🧪 互動：歸納步驟逐步展開
定理：1 + 2 + ⋯ + n = n(n+1)/2。點選「下一步」，逐步觀察每個歸納步驟的代數推導過程。
4
教材來源：Mathematics for Computer Science (Lehman, Leighton, Meyer)