為什麼推倒第一張骨牌，整排都會倒？歸納、反證與構造

為什麼推倒第一張骨牌，整排都會倒？

想像你面前排著一長列骨牌，每一張都立得好好的。你想說服朋友：「只要我推倒第一張，後面全部都會倒。」朋友半信半疑：「你怎麼知道？你又沒有真的一張一張推給我看，何況這排骨牌延伸到看不見的遠方，甚至有無限多張。」

這時你只需要保證兩件事：第一，你確實推倒了第一張；第二，骨牌之間的間距夠近，任何一張倒下時，一定會撞倒它後面那一張。只要這兩件事成立，邏輯上整排骨牌必然全倒——即使有無限多張、即使你永遠看不到最後一張。

這正是數學歸納法（mathematical induction）的精神。它讓我們得以一口氣證明「對所有正整數 $n$ 都成立」這類涉及無限多個情況的命題，而不必、也不可能逐一驗證。本文要談的，正是歸納法以及它的兩個證明夥伴——反證法（proof by contradiction）與構造法（constructive proof），看看數學家如何把「我覺得這應該對」變成「這必然為真」。

數學歸納法：兩步搭一座無限的橋

把骨牌的比喻翻譯成數學語言。設 $P(n)$ 是一個關於正整數 $n$ 的敘述（命題）。要證明「對所有 $n \geq 1$，$P(n)$ 都成立」，我們只需完成兩步：

1. 基底步驟（base case）：證明 $P(1)$ 成立——推倒第一張骨牌。
2. 歸納步驟（inductive step）：證明對任意 $k \geq 1$，假設 $P(k)$ 成立（這個假設稱為歸納假設，inductive hypothesis），則 $P(k+1)$ 也成立——保證每一張倒下都會撞倒下一張。

一旦這兩步都完成，由歸納原理（principle of induction）可知：$P(1)$ 成立 $\Rightarrow$ $P(2)$ 成立 $\Rightarrow$ $P(3)$ 成立 $\Rightarrow \cdots$，骨牌效應啟動，命題對所有正整數成立。

這裡有個常被誤解的關鍵：歸納步驟裡我們「假設 $P(k)$ 成立」，這不是循環論證，不是「假設結論成立再證明結論」。我們證明的是一個蘊含關係（implication）：$P(k) \Rightarrow P(k+1)$。我們從未斷言 $P(k)$ 本身為真，只是說「如果它真，那麼下一個也真」。真正讓骨牌倒下的動力，來自基底步驟。

看一個例子：前 $n$ 個正整數之和

讓我們證明那個著名的公式：

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

設 $P(n)$ 為「$\displaystyle\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$」。

基底步驟：當 $n=1$，左式 $= 1$，右式 $= \dfrac{1 \cdot 2}{2} = 1$。兩邊相等，$P(1)$ 成立。

歸納步驟：假設 $P(k)$ 成立，即 $$\sum_{i=1}^{k} i = \frac{k(k+1)}{2}.$$ 我們要證 $P(k+1)$，也就是 $\displaystyle\sum_{i=1}^{k+1} i = \frac{(k+1)(k+2)}{2}$。從左式出發： $$\sum_{i=1}^{k+1} i = \left(\sum_{i=1}^{k} i\right) + (k+1) = \frac{k(k+1)}{2} + (k+1).$$ 注意第二個等號用上了歸納假設。接著通分整理： $$\frac{k(k+1)}{2} + (k+1) = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}.$$ 這正是 $P(k+1)$ 的右式。歸納步驟完成。

由數學歸納法，公式對所有正整數 $n$ 成立。$\blacksquare$

傳說高斯（Gauss）小時候用「首尾配對」瞬間算出 $1$ 到 $100$ 的和，那是一個漂亮的構造性論證；而歸納法則提供了另一條嚴謹的路徑，兩者殊途同歸。

動手試試：一個不等式

請你試證：對所有 $n \geq 1$，$2^n \geq n+1$。

基底步驟：$n=1$ 時 $2^1 = 2 \geq 1+1 = 2$，成立。歸納步驟：假設 $2^k \geq k+1$，則 $$2^{k+1} = 2 \cdot 2^k \geq 2(k+1) = 2k+2 \geq k+2 = (k+1)+1,$$ 其中最後一步用到 $k \geq 0$ 所以 $2k+2 \geq k+2$。完成。你會發現，難點往往在歸納步驟裡「如何把 $P(k+1)$ 拆出一塊 $P(k)$ 用得上的形狀」。

強歸納法：當一張骨牌需要前面好幾張一起撞

有時候，要證明 $P(k+1)$，光靠 $P(k)$ 不夠，你需要 $P(1), P(2), \ldots, P(k)$ 全部都成立才推得動。這時用強歸納法（strong induction）：

歸納步驟改為——假設對所有 $1 \leq j \leq k$，$P(j)$ 都成立，據此證明 $P(k+1)$。

強歸納法與普通歸納法在邏輯上等價（可以互相推導），但在某些問題上表達更自然。經典範例是「每個大於 $1$ 的整數都可以分解為質數的乘積」：

設 $n > 1$。若 $n$ 是質數，本身就是分解。若 $n$ 是合數，則 $n = a \cdot b$，其中 $1 < a, b < n$。此時單用 $P(n-1)$ 毫無幫助，但強歸納假設保證 $a$ 與 $b$（都小於 $n$）各自可分解為質數乘積，把它們拼起來就得到 $n$ 的質因數分解。這正是算術基本定理（fundamental theorem of arithmetic）存在性部分的證明骨架。

反證法：假設它是錯的，然後撞牆

歸納法擅長處理「對所有 $n$」，但有些命題用另一種武器更鋒利——反證法。它的邏輯是：要證明命題 $Q$ 為真，先假設 $Q$ 為假，然後從這個假設推導出一個矛盾（contradiction），例如推出 $0 = 1$，或推出某個既定為真的事實的反面。既然假設導致荒謬，這個假設必為錯，故 $Q$ 為真。

看一個例子：$\sqrt{2}$ 是無理數

這是數學史上最古老、最優雅的反證法之一，據傳令畢達哥拉斯學派震撼不已。

假設 $\sqrt{2}$ 是有理數。那麼可寫成最簡分數 $$\sqrt{2} = \frac{p}{q},$$ 其中 $p, q$ 為整數、$q \neq 0$，且 $\gcd(p, q) = 1$（已約到最簡，無公因數）。兩邊平方： $$2 = \frac{p^2}{q^2} \quad\Longrightarrow\quad p^2 = 2q^2.$$ 於是 $p^2$ 是偶數，因此 $p$ 必為偶數（奇數的平方仍是奇數）。設 $p = 2m$，代回： $$(2m)^2 = 2q^2 \quad\Longrightarrow\quad 4m^2 = 2q^2 \quad\Longrightarrow\quad q^2 = 2m^2.$$ 這又說明 $q^2$ 是偶數，故 $q$ 也是偶數。但這樣一來 $p$ 與 $q$ 同時是偶數，有公因數 $2$，與「$\gcd(p,q)=1$ 最簡分數」的前提矛盾。

矛盾出現了。故假設錯誤，$\sqrt{2}$ 不是有理數。$\blacksquare$

反證法的威力在於：它把「無理數」這種「不存在某種表示」的否定性敘述，轉化成一個我們可以動手操作的等式 $p^2 = 2q^2$。要小心的迷思是——並非所有反證都是好證明。如果你只是把命題「$A \Rightarrow B$」改寫成「假設 $A$ 且非 $B$，推出非 $A$」，那其實是對位證明（proof by contrapositive），是直接證明的變形，邏輯上更乾淨，不必硬扯「矛盾」二字。真正的反證法是推出一個與已知事實（而非與假設本身）相牴觸的結論。

構造法：不只說它存在，還把它造出來

第三種風格是構造法。當命題說「存在某個物件滿足某性質」，構造性證明不滿足於間接論證它「必定存在」，而是直接給出一個具體的例子或演算法把它造出來。

歐幾里得（Euclid）證明「質數有無限多個」就帶有強烈的構造色彩，且常以反證法包裝。假設質數只有有限個：$p_1, p_2, \ldots, p_n$。構造一個新數 $$N = p_1 p_2 \cdots p_n + 1.$$ $N$ 除以任何一個 $p_i$ 都餘 $1$，所以 $N$ 不被清單上任何質數整除。於是 $N$ 要嘛本身是質數，要嘛有不在清單上的質因數——無論哪種，都出現了清單外的質數，與「質數只有這些」矛盾。故質數無限多。

這裡值得玩味的是：構造法與反證法常常搭配出場。我們構造出 $N$ 這個具體物件，再用它撞出矛盾。

構造法與存在性證明（non-constructive existence proof）形成有趣對照。有些定理只證明「某物存在」卻給不出它長什麼樣子——例如用鴿籠原理（pigeonhole principle）論證「必有兩人生日同月」，卻說不出是哪兩人。數學上兩者都算嚴謹的證明，但構造性證明在計算機科學裡格外珍貴，因為它往往直接對應一個可執行的演算法。

重點回顧

• 數學歸納法 = 基底步驟 + 歸納步驟。先推倒第一張骨牌（$P(1)$），再保證每張都會撞倒下一張（$P(k) \Rightarrow P(k+1)$），即可證明對所有正整數成立。
• 歸納步驟證的是蘊含關係而非結論本身，所以「假設 $P(k)$」不是循環論證；真正的證明動力來自基底步驟。
• 強歸納法在「需要前面所有情況」時派上用場，與普通歸納法邏輯等價；質因數分解的存在性是典型應用。
• 反證法：假設命題為假，推出與已知事實的矛盾。$\sqrt{2}$ 為無理數是經典範例。注意區分真正的反證法與對位證明。
• 構造法：直接造出滿足性質的物件或演算法，比間接的存在性論證更「實用」，在計算機科學中尤其重要。

深入探討（研究所視角）

歸納法的邏輯地基：良序原理與皮亞諾公理。為什麼歸納法「合法」？它並非憑空成立，而是與自然數的本質結構綁定。在皮亞諾公理（Peano axioms）的體系裡，歸納公理本身就是一條公理，定義了自然數「是什麼」。等價地，歸納原理可由良序原理（well-ordering principle，即每個非空自然數子集都有最小元素）推出：若 $P(n)$ 不對所有 $n$ 成立，則「反例集合」非空，取其最小反例 $m$，再論證 $m-1$ 或更小者導致矛盾——這套「最小反例法」（minimal counterexample）其實是反證法與歸納法的合體，在數論與組合學中極為常用。

超越自然數：超限歸納（transfinite induction）。歸納法不限於可數的步進。在序數（ordinal）上，我們有超限歸納：證明分為後繼序數（successor ordinal，像 $k+1$）與極限序數（limit ordinal，如 $\omega$，沒有直接前驅）兩種情況。極限序數需要的不再是「前一個」，而是「之前所有元素」的資訊——這正是強歸納的超限版本。良序定理（依賴選擇公理 axiom of choice）保證任何集合都能良序化，使超限歸納成為集合論證明的核心工具。

構造主義與排中律的張力。反證法默默倚賴一條經典邏輯定律——排中律（law of excluded middle）：$P \lor \neg P$ 恆真。但直覺主義邏輯（intuitionistic logic）與構造主義數學（如 Brouwer 的學派）拒絕無條件使用排中律：他們認為「證明 $\neg\neg P$」不等於「證明 $P$」，因為前者沒有真正造出 $P$ 的見證（witness）。在這個框架下，用反證法得到的「純存在性」結論被視為較弱。這不只是哲學爭論——它有實際後果。透過 Curry–Howard 同構（Curry–Howard correspondence），構造性證明與電腦程式一一對應：一個構造性的存在證明 $\exists x.\, \phi(x)$ 可以「萃取」（extract）出一個實際計算出 $x$ 的程式。Coq、Agda、Lean 等證明輔助器（proof assistant）正是建立在這套對應上，讓「證明定理」與「寫出可驗證的程式」融為一體。

跨領域連結：歸納與遞迴、演算法分析。歸納法在計算機科學裡無所不在。結構歸納法（structural induction）把骨牌效應從數字推廣到遞迴定義的資料結構（如串列、樹、語法樹），是程式正確性證明的基石。迴圈不變量（loop invariant）本質上是對迴圈執行次數的歸納。而遞迴演算法的時間複雜度——例如合併排序（merge sort）的遞迴關係 $T(n) = 2T(n/2) + \Theta(n)$ 解得 $T(n) = \Theta(n \log n)$——其推導與正確性證明都依賴歸納。可以說，每當我們相信一段遞迴程式「對所有輸入大小都正確」，背後撐著的就是這套「推倒第一張骨牌」的古老智慧。