2. 直接證明、反證法與歸納法

設 $P(n)$ 是關於整數 $n\ge n_0$ 的陳述，$n_0$ 固定。數學歸納法說明：

1. 證明基礎情形 $P(n_0)$。
2. 對任意整數 $k\ge n_0$，假設 $P(k)$，並證明 $P(k+1)$。
3. 得出對每個整數 $n\ge n_0$ 都有 $P(n)$。

第 2 步的假設是歸納假設，它是條件性的，不是預先假設最終定理成立。基礎情形啓動鏈條，蘊含則將任意有效一環延伸到下一環。

可用非負整數的最小元素性質說明：若有反例，則存在最小反例 $m\ge n_0$。基礎情形排除 $n_0$，於是 $m-1\ge n_0$ 不是反例，歸納步驟迫使 $P(m)$ 成立，矛盾。

對於任意整數起點 $n_0$，將指標平移為 $m-n_0\ge0$，即可用最小元素性質證明上面的最小反例步驟。

反過來，正整數上的普通歸納法蘊含最小元素性質。假設非空集合 $S\subseteq\{1,2,3,\ldots\}$ 沒有最小元素。令 $P(n)$ 表示 $1,\ldots,n$ 均不屬於 $S$。若 $1\in S$，它就是最小元素，故 $P(1)$ 成立。若 $P(k)$ 成立而 $k+1\in S$，則 $k+1$ 是 $S$ 的最小元素，矛盾。因此 $P(k)\Rightarrow P(k+1)$。歸納法給出每個正整數 $n$ 都滿足 $P(n)$，於是 $S$ 為空，與其非空假設矛盾。所以每個非空正整數集合都有最小元素。用 $n\mapsto n-n_0+1$ 平移指標，即得任意整數起點 $n_0$ 的對應歸納版本。

學習目標

寫出直接證明、逆否證明及反證；分別證明存在性與唯一性；使用歸納法和最小反例論證。證明解釋為何每個允許的情形都由定義和已知事實推出。檢查許多實例可以提示定理，但不能代替全稱論證。

證明結構

直接證明 $P\Rightarrow Q$ 時，假設 $P$ 並推出 $Q$。使用逆否命題時，假設 $\neg Q$ 並推出 $\neg P$。反證法假設前提及所需結論的否定，從中推出不可能的結果。矛盾必須來自已聲明的假設，而不是無關的假命題。

對存在斷言 $\exists x\ P(x)$，構造明確見證通常最有力。證明對象唯一時，先證明至少存在一個，再假設兩個候選對象滿足定義條件並證明它們相同。每個候選對象都必須滿足某方程只證明必要性；在代回驗證候選值前，還沒有證明存在性。

例：奇偶性。 若整數 $n$ 為奇數，寫 $n=2k+1$。則 $n^2=4k^2+4k+1=2(2k^2+2k)+1$ 為奇數。取逆否命題可知平方為偶數的整數本身必為偶數。這裏沒有假設每個整數都在 $\mathbb Z$ 中有平方根。

定理：由良序性推出歸納法

設 $P(n)$ 是整數 $n\ge n_0$ 上的謂詞。若 $P(n_0)$ 為真，且對每個 $n\ge n_0$ 有 $P(n)\Rightarrow P(n+1)$，則對所有這樣的整數 $P(n)$ 均成立。

證明。 假設不成立的指標集合非空。由良序性，它有最小元素 $m$。由於基礎情形成立，$m$ 不等於 $n_0$，故 $m-1\ge n_0$。由最小性，$P(m-1)$ 成立；歸納蘊含推出 $P(m)$，與其不成立矛盾。故失敗集合為空。

強歸納在歸納步驟中以從 $n_0$ 到 $n$ 的全部情形代替單獨假設 $P(n)$；同樣的最小反例證明可為其提供依據。當構造使用多個較小輸入而非僅用緊鄰前一項時，它很有用。

例題

有限求和。 證明對 $n\ge1$，$1+3+\cdots+(2n-1)=n^2$。當 $n=1$，兩邊都為一。假設公式在 $n$ 成立，加上下一個項 $2n+1$ 得 $n^2+2n+1=(n+1)^2$，正是下一情形。該步驟使用已知公式，而不是假設所需的下一個等式。

線性方程解的存在性與唯一性。 對實數 $a\ne0,b$，方程 $ax+b=0$ 恰有一個解。$x=-b/a$ 存在，代入可驗證。若 $x,y$ 都是解，相減得 $a(x-y)=0$，故 $x=y$。若 $a=0$，則無解（$b\ne0$）或有無窮多個解（$b=0$），說明該假設不可省略。

分層練習

1. 基礎。 從定義證明兩個奇整數之和為偶數。
2. 核心。 用歸納法證明對 $n\ge1$，$\sum_{k=1}^n k=n(n+1)/2$。
3. 核心。 證明整數 $n\ge0$ 滿足 $2^n\ge n+1$，並指出基礎情形的作用。
4. 證明。 用強歸納證明每個整數 $n\ge2$ 都是素數的乘積。不要從這一證明聲稱分解唯一。

詳解

1. 若兩個整數為 $2r+1$ 和 $2s+1$，其和為 $2(r+s+1)$，是整數的兩倍，故為偶數。
2. 當 $n=1$，$1=1\cdot2/2$。若公式在 $n$ 成立，下一項和為 $n(n+1)/2+(n+1)=(n+1)(n+2)/2$。歸納法給出所有 $n\ge1$ 的結論。
3. 當 $n=0$，$1=0+1$。若 $2^n\ge n+1$，則由於 $n\ge0$，有 $2^{n+1}\ge2(n+1)\ge n+2$。因此蘊含成立，而真的基礎情形啓動了歸納鏈；僅有蘊含不能證明任何特定情形。
4. 當 $n=2$，該數本身為素數。假設從 $2$ 到 $n-1$ 的所有整數都有該性質。若 $n$ 為素數，它本身是單因子的乘積；否則 $n=ab$，其中整數 $2\le a,b<n$。由假設兩因子均為素數乘積，連接兩個分解即得 $n$ 的分解。這裏只證明存在；唯一性需要額外的整除論證。

總結與術語

見證實現存在性；唯一性排除不同候選對象。歸納假設只在歸納步驟內部用作條件假設。最小反例是良序下最小的不成立整數。選擇方法前先寫目標。基礎情形、例外參數及必要與充分的區別都是論證本身，而非可有可無的說明。