# Chapter5 - 歸納與遞迴 Induction & Recursion

## 數學歸納法 M.I.
> **前情提要** : 假設我們有一個無限高度的梯子，並且我們知道以下兩件事 :
> 1. 我們可以爬到梯子的第一階
> 2. 如果我們可以爬到梯子的某一階，那我們就能爬到下一階
>
> **我們能否得到結論 : 我們可以爬到梯子的每一階**

* 說明 :
* 數學歸納法只能證明已其他方式得到的結果，它並非發現公式或定理的工具
* 數學歸納法是一個強大又嚴謹的計數，用以證明命題函數 $P(n)$ 對每個自然數 $n$ 皆成立，無論 $n$ 值多大

* 定理 : 假設每個正整數 $n$ 都有一個命題 $P(n)$
* 基本步驟 : $P(1)$ 為真
* 歸納步驟 : 若 $P(k)$ 為真(**歸納假設**)，則對於所有正整數 $k$ 來說， $P(k+1)$ 為真
* 因此對於每個正整數 $n$ 來說 $P(n)$ 為真

* 證明求和公式 : 證明若 $n$ 為正整數，則 $1+2+ \cdots + n = n(n+1)/2$
* 基本步驟 : 當 $n = 1$ 時，命題為真，因為 $1 = 1(1+1)/2$
* 歸納步驟 : 假設 $n = k \Rightarrow 1+2+ \cdots +k = k(k+1) / 2$ 為真

當 $n = k+1$ 時，
$1+2+ \cdots +k+(k+1) = k(k+1)/2 + (k+1) = [k(k+1) + 2(k+1)]/2 = (k^2 + 3k + 2)/2 = (k+1)(k+2)/2$
最後一個等號證明，當 $n = k+1$ 時命題也成立

我們完成了基本步驟和遞迴步驟，因此根據數學歸納法，我們證明出 若 $n$ 為正整數，則 $1+2+ \cdots + n = n(n+1)/2$

* 證明不等式 : 證明不等式 $n > 2^n$，$n$ 為正整數

令 $P(n)$ 為命題 $n < 2^n$
* 基本步驟 : $P(1)$ 為真，因為 $1 < 2^1 = 2$
* 歸納步驟 : 設 $P(k)$ 為真( $k$ 為正整數)，因此 $k < 2^k$。我們需要證明 $P(k+1)$ 為真 : $k+1 < 2^{k+1}$ : $k+1 < 2^k+1 ≦ 2^k + 2^k = 2^{k+1}$

我們證明了基於 $P(k)$ 為真的情況下， $P(k+1)$ (也就是 $k+1 < 2^{k+1}$)為真。遞迴步驟已完成。因此根據數學歸納法，$n > 2^n$ ($n$ 為正整數)得證

* 證明整除規則 : 證明 $n^3 - n$ 可被3整除，$n$ 為正整數

令 $P(n)$ 為命題$n^3 - n$ 可被3整除
* 基本步驟 : $P(1)$ 為真，因為 $1^3-1=0$ 可被3整除
* 歸納步驟 : 設 $P(k)$ 為真，因此 $k^3 - k$ 可被3整除。我們需要證明 $P(k+1)$ 為真 : $(k+1)^3 - (k+1) = (k^3 + 3k^2 + 3k + 1) - (k + 1) = (k^3 - k) + 3(k^2 + k)$

因為 $k^3 - k$ 和 $3(k^2 + k)$ 都可被3整除，因此 $(k^3 - k) + 3(k^2 + k)$ 亦可被3整除。所以根據數學歸納法 $n^3 - n$ 可被3整除 ($n$ 為正整數)得證

* 證明集合論定理 : 證明若 $S$ 為一有 $n$ 個元素的有限集合( $n$ 為非負整數)，則 $S$ 有 $2^n$ 個子集合

令 $P(n)$ 為命題一個有 $n$ 個元素的集合，擁有 $2^n$ 個子集合
* 基本步驟 : $P(0)$ 為真，因為0個元素的集合為空集合，只有 $2^0 = 1$ 個子集合
* 歸納步驟 : 設 $P(k)$ 為真(對於任意非負整數 $k$ 而言)，因此有 $k$ 個元素的集合擁有 $2^k$ 個子集合。我們需要證明 $P(k+1)$ 為真 : 有 $k+1$ 個元素的集合擁有 $2^{2k+1}$ 個子集合

令 $T$ 為有 $K+1$ 個元素的集合，且 $S = T - \{ a \}$ (從 $T$ 中提取一個元素，使 $S$ 長度為 $k$)。對於 $S$ 的每個子集合 $X$，有兩個會對應到 $T$ 的子集合，一個是 $X$ (不含 $a$)，另一個是 $X \cup a$ (含 $a$)。這樣每個 $X$ 都產生兩個不同的 $T$ 的子集合，而且不會重複，也不會漏掉任何可能（因為每個 $T$ 的子集合不是含 $a$ 就是不含 $a$)。由於 $S$ 有 $2^k$ 個子集合，而每個 $X$ 對應兩個 $T$ 的子集合，所以 $T$ 一共有 $2 \cdot 2^k = 2^{k+1}$ 個子集合，得證

* 數學歸納法的證明錯誤(謬誤)
* 在使用數學歸納法得證明中，我們必須完成一個正確的基本步驟和歸納步驟
* 有時很難找到數學歸納法中的證明錯誤

## 強歸納法和良序 Strong Induction & Well-Ordering
* 強歸納法有時被稱為數學歸納法的第二個原理或完全歸納法

* 定理 : 假設每個正整數 $n$ 都有一個命題 $P(n)$
* 基本步驟 : 證明 $P(1)$ 為真
* 歸納步驟 : 證明 $[P(1) \vee P(2) \vee \dots \vee P(k)] \rightarrow P(k+1)$ 為真 (對所有正整數 $k$ 而言)
---
* 例題 : 有一個遊戲，它的規則是兩名玩家輪流從兩堆火柴中各取出任意數量的火柴，取出最後一支火柴的玩家贏得遊戲。請證明如果兩堆火柴的初始數量相同，則第二位玩家總是保證獲勝

$Ans:$ 令 $P(n)$ 為命題第二為玩家總是能在初始每堆內有 $n$ 支火柴的情況下獲得勝利
* 基本步驟 : $P(1)$ 為真，因為兩堆火柴都各為一支，第一位成員只能拿取其中一根，剩下一根只能由第二位成員拿取，使第二位玩家獲勝
* 歸納步驟 : 設 $P(j)$ 為真( $1 ≦ j ≦ k$ )，因此在遊戲開始時，兩堆火柴各有 $1 ≦ j ≦ k$ 支火柴，第二位玩家總是可以贏得比賽。我們需要證明 $P(k+1)$ 為真，並假設第一位玩家從某堆火柴取出了 $r$ 支( $1 ≦ r ≦ k$ )，而這堆火柴內只剩下 $k+1-r$ 支。第二位玩家再從另一堆火柴內取出相同數量的火柴，因此兩堆的火柴數都剩下 $k+1-r$ 支。因為 $1 ≦ k+1-r ≦ k$，所以我們證明了第二位玩家總是可以贏得比賽。

* 另一種形式的強歸納法
* 基本步驟 : 驗證命題 $P(b), P(b+1), \dots, P(b+j)$ 為真
* 歸納步驟 : 證明 $[P(b), P(b+1), \dots, P(k)] \rightarrow P(k+1)$ 為真 ( $k ≧ b+j$ )
---
* 例題 : 證明所有金額為12美分或以上的郵資都可以只使用4美分和5美分的郵票來構成

$Ans:$
* 基本步驟 :
$12 = 3 \times 4 + 0 \times 5$
$13 = 2 \times 4 + 1 \times 5$
$14 = 1 \times 4 + 2 \times 5$
$15 = 0 \times 4 + 3 \times 5$
$\therefore P(j) \text{ 成立 } (12 ≦ j ≦ 15)$
* 歸納步驟 : 設 $P(j)$ 為真( $12 ≦ j ≦ k, k>15)$，我們需要證明 $P(k+1)$ 為真 : 使用 $P(k-3)$ 的郵資加上4美分郵票就可以組成 $k+1$ 的郵資

* 良序原理 : 數學歸納法與強歸納法的有效性皆來自整數集合的一個基本公理
* 例題 : 在循環賽中，每位選手與其他所有選手各交手一次，每場比賽都產生勝者和負者。我們稱選手 $p_1, p_2, ..., p_m$ 構成一個循環，如果 $p_1$ 勝 $p_2$，$p_2$ 勝 $p_3$，…，$p_{m-1}$ 勝 $p_m$，且 $p_m$ 勝 $p_1$。利用良序原理證明，如果循環賽中存在長度為 $m (m ≥ 3)$ 的循環，則必然存在由這三位選手組成的循環

$Ans:$ 我們假設不存在三人循環。由於循環賽中至少存在一個循環，因此存在長度為 $n$ 的循環的所有正整數 $n$ 的集合非空。根據良序性，此正整數集合存在最小元素 $k$，根據假設，$k$ 必須大於 3。因此，存在一個由 $p_1, p_2, p_3, \dots, p_k$ 組成的循環，且不存在較短的循環。由於不存在三人循環，我們知道 $k > 3$。考慮該循環的前三個元素 $p_1$、$p_2$ 和 $p_3$。 $p_1$ 和 $p_3$ 的比賽有兩種可能的結果。如果 $p_3$ 戰勝 $p_1$，則 $p_1$、$p_2$、$p_3$ 構成一個長度為 3 的循環，這與我們假設不存在三人循環相矛盾。因此，必然是 $p_1$ 戰勝 $p_3$。這表示我們可以從循環 $p_1, p_2, p_3, \dots, p_k$ 省略 $p_2$，得到長度為 $k$ 的循環 $p_1, p_2, p_3, \dots, p_k$，這與最小循環長度為 $k$ 的假設相矛盾。由此我們得出結論：必然存在長度為 3 的循環。

## 遞迴定義與結構歸納
* 遞迴定義函數 : 分成兩部分定義
* 基礎步驟 : $f(0)$
* 遞迴步驟 : 從 $f(n)$ 找到 $f(n+1)$

* 費波那契數列
$$
\begin{cases}
f(0) = 0 \\
f(1) = 1 \\
f(n) = f(n-1) + f(n-2)
\end{cases}
$$

* 例題 : 證明 $n ≧ 3$ 時， $f(n) > \alpha^{n-2}$，在 $\alpha = (1 + \sqrt 5) / 2$ 處

$Ans:$ 使用強歸納法，令 $P(n)$ 符合 $f(n) > \alpha^{n-2}$ 敘述
* 基本步驟 :
* $\alpha < 2 = f(3) \Rightarrow P(3)$ 成立
* $\alpha ^2 = (3 + \sqrt 5) / 2 < 3 = f(4) \Rightarrow P(4)$ 成立
* 歸納步驟 :
* 設 $P(j)$ 成立，也就是 $f(j)> \alpha ^{j-2}$，對所有符合 $3 ≦ j ≦ k \ (k ≧ 4)$ 的整數 $j$ 而言。我們需要證明 $P(k+1)$ 成立，也就是 $f(k+1) > \alpha ^{k-1}$ 成立
* 已知 $\alpha$ 為 $x^2 - x - 1 = 0$ 的解，所以 $\alpha^2 = \alpha + 1$。將其代入 : $\alpha ^{k-1} = \alpha ^ 2 \times \alpha ^{k-3} = (\alpha + 1) \times \alpha ^{k-3} = \alpha ^{k-2} \times \alpha ^{k-3}$
* 根據強歸納假設，當 $k ≧ 4$ 時 : $f(k-1) > \alpha ^{k-3}, \ f(k) > \alpha ^{k-2}$
* 因此我們得到 $f(k+1) = f(k) + f(k-1) > \alpha ^{k-2} + \alpha ^{k-3} = \alpha ^{k-1}$
* $f(k+1) > \alpha ^{k-1}$ ，因此 $P(k)$ 成立，得證

* 遞迴定義集合與結構
* 基礎步驟 : 指定初始元素集合
* 遞迴步驟 : 根據集合中已知元素，形成新的元素

* 所有字串的集合 $\Sigma^*$
* 基本步驟 : $\lambda \in \Sigma^*$ ($\lambda$是空字串)
* 遞迴步驟 : 若 $w \in \Sigma^*$ 且 $x \in \Sigma$，則 $wx \in \Sigma ^*$

* 有根樹(rooted tree)定義
* 基本步驟 : 一個單一節點 $r$ 為一有根樹
* 遞迴步驟 : 如果 $T_1,T_2,\cdots,T_n$ 是互不相交、根分別為 $r_1,r_2,\cdots,r_n$ 的有根樹，那麼再加一個新頂點 $r$ 並從 $r$ 向每個 $r_i$ 連邊所得到的圖也是一棵有根樹

* 完滿二元樹(full binary tree)定義
* 基本步驟 : 有一完滿二元樹只由一個節點 $r$ 組成
* 遞迴步驟 : 若一棵二元樹的根剛好有左、右兩棵子樹，且這兩棵子樹本身都是完滿二元樹，那這棵二元樹就是完滿二元樹

* 結構化歸納法
* 基本步驟 : 證明那些在集合基礎步驟中所定義的成員是符合題意的要求的
* 遞迴步驟 : 假設那些用來建造新成員的成員符合題意的要求，之後要證明用集合遞迴規則所建造的新成員亦符合題意的要求

## 遞迴演算法
* 遞迴 recursive : 藉由把問題簡化到更小輸入的相同問題，來解決原問題的演算法(不斷呼叫自己)。例 : 費波那契數列、階層、最大公因數、二元搜尋法等
* 虛擬碼 : 以費波那契數列為例

        procedure fibonacci(n: nonnegative)
        if n = 0 then return 0
        else if n = 1 then return 1
        else return fibonacci(n−1) + fibonacci(n−2)

* 迭代 iterative : 從基礎步驟開始，使用遞迴步驟找到函數在連續更大整數的值(由小找到大)
* 虛擬碼 : 以費波那契數列為例

        procedure iterative fibonacci(n: nonnegative integer)
        if n = 0 then return 0
        else
        x : = 0; y := 1;
        for i := 1 to n−1
        z := x + y; x := y; y := z
        return y
        {y is the nth Fibonacci number}