數學歸納法

數學歸納法 (mathematical induction) 證明「對所有 $n\ge n_0$,$P(n)$ 成立」分兩步:基底 驗證 $P(n_0)$;歸納步驟 假設 $P(k)$ 成立(歸納假設),推出 $P(k+1)$。像推骨牌:第一張倒、每張倒會推倒下一張,全部都倒。

常見誤解:歸納假設只假設一個 $k$,不是假設所有 $n$(那就循環論證了);方向是 $k\to k+1$,不是反過來。強歸納法則假設 $P(n_0),\dots,P(k)$ 全部成立,用在質因數分解這類需要回溯更早情況的證明。

算例:證 $1+2+\cdots+n = \frac{n(n+1)}{2}$。基底 $n=1$:$1 = 1$。歸納:$\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$,成立。同法可證 $\sum_{k=1}^{n} k^2 = \frac{n(n+1)(2n+1)}{6}$、$2^n > n$、$n^3 - n$ 是 6 的倍數。

歸納法與遞迴是一體兩面:遞迴程式的正確性證明、資料結構的不變量、演算法複雜度分析都靠它。