# 0.3 數學歸納法

除了0.1小節提到的反證法外，數學歸納法是另一種重要的證明方式，常用於證明涉及整數的命題。本節先介紹數學歸納法，將其應用於有限多個數的求和，再揭示數學歸納法與正整數公理的關係。

## 數學歸納法

:::warning
**定義0.3.1（數學歸納法）**
令$P(n)$為涉及整數$n$的敘述，下列證明方式稱為<font color=red>數學歸納法（proof by induction）</font>。

給定整數$n_1$，一旦驗證了下列條件，就能確認$P(n)$在$n\geq n_1$時均成立：
1. $P(n_1)$成立。
2. 對任意不小於$n_1$的整數$k$而言，只要$P(k)$成立，$P(k+1)$便亦成立。

第一個條件稱為歸納起點（base case），第二個條件則是歸納步驟（induction step）；
在歸納步驟中，「$P(k)$成立」的假設稱為歸納假設（induction hypothesis）。
:::

在許多證明中，$n_1=1$。數學歸納法可以類比成骨牌效應：一旦知道第一張骨牌倒下，而且下一張骨牌在前一張骨牌倒下後總會跟著倒下，那麼便能肯定所有骨牌都將倒下。

:::info
**範例0.3.2**
令$a,b$為滿足$0<a<b$的實數。
以下利用數學歸納法證明：對任意的正整數$n$而言，$a^n<b^n$。

將不等式$a^n<b^n$記成$P(n)$，$n\in \mathbb{N}$。
1. 先驗證歸納起點：因為$a<b$，所以$P(1)$成立。
2. 再論證歸納步驟：對任意的正整數$k$而言，只要$P(k)$成立，就有$a^k<b^k$。
因此，$a^{k+1} = a^k\times a < b^k\times a < b^k\times b = b^{k+1}$；故$P(k+1)$亦成立。

那麼根據數學歸納法，$P(n)$對任意的正整數$n$均成立，即$a^n<b^n$。
:::

論證歸納步驟時往往需要用到歸納假設。範例0.3.2中的歸納假設是不等式$a^k<b^k$；我們將其兩側同乘以$a$，得到$a^k\times a<b^k\times a$。注意到$b^k\times a<b^k\times b$源於將$a<b$的兩側同乘以$b^k$，這一步須先確認$b^k>0$；讀者應嘗試用數學歸納法從$b>0$推得$b^k>0$。

實際運用數學歸納法時，習慣直接驗證歸納起點和歸納步驟，而不會明確訂定敘述$P(n)$。
特別留意這兩個條件都要檢驗，缺一不可。

:::info
**範例0.3.3**
考慮「等式」$1+\cdots+n=(2n+1)^2/8$，$n\in \mathbb{N}$：
對任意的正整數$k$而言，若此式於$n=k$時成立，則
$$1+\cdots+(k+1) = \frac{(2k+1)^2}{8} + (k+1) = \frac{(2(k+1)+1)^2}{8}$$ 故此式於$n=k+1$時亦成立。

然而因為歸納起點並未驗證，所以無法由數學歸納法確認此式成立。
事實上，$1+\cdots+n$會小於$(2n+1)^2/8$（見命題0.3.5）。
:::

## 求和符號

實數$a_1,\dots,a_n$的總和記為$a_1+\cdots+a_n$；為了簡化版面，將這個表示法濃縮成
$$\sum_{i=1}^{n} a_i$$ 其中$i$為編號（dummy index），$\sum_{i=1}^n$表示$i$從$1$數到$n$，$a_i$則呈現了第$i$個相加實數的樣貌。
在此$i$可替換成其他符號，不影響求和結果；有時候我們會讓$i$從其他的正整數$m$算起，此時
$$\sum_{i=m}^{n} a_i = a_{m}+\cdots+a_n$$ 假如第一個相加的實數記作$a_0$，也能讓$i$從$0$開始。

:::info
**範例0.3.4**
1. $\sum_{i=1}^{3} 1 = 1+1+1 = 3$
2. $\sum_{i=1}^{4} i = 1+2+3+4 = 10$
3. $\sum_{k=2}^{5} 2^k = 2^2+2^3+2^4+2^5 = 60$
:::

注意到不同的求和形式可能得到相同結果，例如$\sum_{i=1}^{6} 2^{i-1} = \sum_{j=0}^{5} 2^j = \sum_{k=2}^{7} 2^{7-k}$。

數學歸納法與有限多個數的求和密不可分，其中一個原因在於它能用來推導求和公式。

:::danger
**命題0.3.5**
令$r$為非$0$或$1$的實數。下列等式對任意的正整數$n$均成立：
$$\sum_{i=1}^{n} i = \frac{n(n+1)}{2},\qquad \sum_{i=1}^{n} r^{i-1} = \frac{1-r^n}{1-r}$$
:::

以下僅證明右側的等式，記作$(\star)$；左側的等式留給讀者練習。

:::success
**證明**
等式$(\star)$於$n=1$時成立：
$$\sum_{i=1}^{1} r^{i-1} = 1 = \frac{1-r^1}{1-r}$$ 對任意的正整數$k$而言，若等式$(\star)$於$n=k$時成立，則
$$\sum_{i=1}^{k+1} r^{i-1} = \left(\sum_{i=1}^{k} r^{i-1}\right)+r^k = \frac{1-r^k}{1-r}+r^k = \frac{1-r^{k+1}}{1-r}$$ 發現該等式於$n=k+1$時仍然成立。

因此根據數學歸納法，等式$(\star)$對任意的正整數$n$均成立。
:::

另一個原因在於數學歸納法可以讓我們透過遞迴（recursion）的方式明確定義求和符號。

:::warning
**定義0.3.6（有限和）**
對任意的正整數$n$而言，實數$a_1,\dots,a_n$的<font color=red>總和（sum）</font>記作$\sum_{i=1}^{n} a_i$，定義如下：
1. 令$\sum_{i=1}^{1} a_i = a_1$。
2. 當$n\geq 2$時，令$\sum_{i=1}^{n} a_i = \left(\sum_{i=1}^{n-1} a_i\right)+a_n$。

至於$a_1+\cdots+a_n$僅是$\sum_{i=1}^{n} a_i$的另一種表示方法。
:::

如此一來，$\sum_{i=1}^{n} a_i$對每個正整數$n$都有定義；例如
$$\sum_{i=1}^{3} a_i = (a_1+a_2)+a_3,\quad \sum_{i=1}^{4} a_i = ((a_1+a_2)+a_3)+a_4$$ 由此便能嚴格地證明求和符號的基本性質。

:::danger
**命題0.3.7**
下列等式對任意的正整數$n$均成立（所有的$a_i,b_i$和$c$都是實數）：
1. $\sum_{i=1}^{n} (a_i+b_i) = \sum_{i=1}^{n} a_i + \sum_{i=1}^{n} b_i$
2. $\sum_{i=1}^{n} (ca_i) = c\sum_{i=1}^{n} a_i$
3. $\sum_{i=1}^{n} (a_{i+1}-a_i) = a_{n+1}-a_1$
:::

以下僅證明第一個等式，其餘等式留給讀者練習。

:::success
**證明**
根據求和符號的定義，第一個等式在$n=1$時成立。
對任意的正整數$k$而言，若第一個等式於$n=k$時成立，則
\begin{align}
\sum_{i=1}^{k+1} (a_i+b_i) &= \left(\sum_{i=1}^{k} (a_i+b_i)\right) + (a_{k+1}+b_{k+1})\\[6pt]
&= \left(\sum_{i=1}^{k} a_i + \sum_{i=1}^{k} b_i\right) + (a_{k+1}+b_{k+1})\\[6pt]
&= \left(\left(\sum_{i=1}^{k} a_i\right) + a_{k+1}\right) + \left(\left(\sum_{i=1}^{k} b_i\right) + b_{k+1}\right) = \sum_{i=1}^{k+1} a_i + \sum_{i=1}^{k+1} b_i
\end{align} 這顯示該等式於$n=k+1$時亦成立。

因此根據數學歸納法，$\sum_{i=1}^{n} (a_i+b_i) = \sum_{i=1}^{n} a_i + \sum_{i=1}^{n} b_i$對任意的正整數$n$均成立。
:::

仿照定義0.3.6的作法，有限多個集合$A_1,\dots,A_n$的聯集$\bigcup_{i=1}^{n} A_i$也可以用遞迴的方式定義：
1. 令$\bigcup_{i=1}^{1} A_i = A_1$。
2. 當$n\geq 2$時，令$\bigcup_{i=1}^{n} A_i = \left(\bigcup_{i=1}^{n-1} A_i\right)\cup A_n$。

又將$\bigcup_{i=1}^{n} A_i$記為$A_1\cup \cdots\cup A_n$。
同樣地，$A_1,\dots,A_n$的交集亦能依此方式定義，以$\bigcap_{i=1}^{n} A_i$或$A_1\cap \cdots\cap A_n$表示。

## 良序原理

為什麼數學歸納法可行呢？原因在於它奠基於正整數的基本公理。

:::warning
**定義0.3.8（良序原理）**
下列敘述稱為<font color=red>良序原理（well-ordering principle）</font>：
對任意$\mathbb{N}$的非空子集合$S$而言，$S$中存在最小的正整數。
:::

這個「最小的正整數」小於或等於$S$中所有的正整數。

:::danger
**命題0.3.9**
數學歸納法可由良序原理導出。

具體而言，任意給定涉及整數$n$的敘述$P(n)$，令$n_1$為整數。
已知$P(n_1)$成立，而且對任意不小於$n_1$的整數$k$而言，$P(k)$成立會使$P(k+1)$成立。
那麼良序原理保證$P(n)$在$n\geq n_1$時均成立。
:::

證明採取反證法的策略。

:::success
**證明**
假設$P(n)$在$n=n^{*}$時不成立，$n^{*}$為某個大於或等於$n_1$的整數。
考慮下列$\mathbb{N}$的子集合：
$$S = \{m\in \mathbb{N}:P(m+n_1-1)不成立\}$$ 由於$n^{*}\geq n_1$且$P(n^{*})$不成立，$n^{*}-n_1+1$為$S$中的元素。
這表示$S$非空；根據良序原理，$S$中存在最小的正整數$m_1$。

因為歸納起點$P(n_1)$成立，所以$1\notin S$。
這使得$m_1>1$，那麼$m_1-1$也是正整數；由此可知：
* $m_1+n_1-2$為不小於$n_1$的整數。
* $m_1-1\notin S$（否則$m_1$不是$S$中最小的正整數），故$P(m_1+n_1-2)$成立。

因此根據歸納步驟的推論，$P(m_1+n_1-1)$亦成立。

然而$m_1\in S$表示$P(m_1+n_1-1)$不成立，矛盾產生。
因此假設錯誤，$P(n)$應在$n\geq n_1$時均成立。
:::

:::danger
**命題0.3.10**
良序原理可由數學歸納法導出。
具體而言，只要$S$是$\mathbb{N}$的非空子集合，數學歸納法就保證$S$中有最小的正整數。
:::

同樣以反證法進行證明。

:::success
**證明**
假設$S$是$\mathbb{N}$的非空子集合，但無法從中找到最小的正整數。
令敘述$P(n)$為「正整數$1,\dots,n$皆不屬於$S$」。

首先，$1\notin S$，否則$1$就是$S$中最小的正整數；故$P(1)$成立。
再者，對任意的正整數$k$而言，若$P(k)$成立，則正整數$1,\dots,k$皆不屬於$S$。
如此一來，$k+1$也不能落在$S$中，否則$k+1$會成為$S$中最小的正整數。
因此，$1,\dots,k+1$皆不屬於$S$，即$P(k+1)$成立。

那麼根據數學歸納法，$P(n)$對任意的正整數$n$均成立。
這意味著$S$中不含任何正整數；然而$S\subseteq \mathbb{N}$，於是$S=\emptyset$，矛盾產生。
因此假設錯誤，只要$S$是$\mathbb{N}$的非空子集合，必能從中找到最小的正整數。
:::

命題0.3.9和命題0.3.10顯示數學歸納法與良序原理等價，所以也常直接作為正整數的基本公理。
儘管如此，某些命題反而更適合用良序原理論證。

:::info
**範例0.3.11**
以下利用良序原理證明：每個有理數都能化簡成最簡分數。

任意給定有理數$r$，考慮
$$D = \left\lbrace n\in \mathbb{N}:存在滿足\frac{m}{n}=r的整數m\right\rbrace$$ 基於$r$為有理數，$D$為$\mathbb{N}$的非空子集合；根據良序原理，$D$中存在最小的正整數$n_1$。
因為$n_1\in D$，所以可取整數$m_1$使得$r = m_1/n_1$。
倘若$m_1/n_1$能繼續約分，則約分後的分母將小於$n_1$且仍屬於$D$，與$n_1$的最小性違背。
因此，$m_1/n_1$無法繼續約分，正是$r$的最簡分數；命題得證。
:::