Implication：
$P \Rightarrow Q$
只有在 $P$ 真、 $Q$ 假時為假
逆否等價：
$P \Rightarrow Q \equiv \neg Q \Rightarrow \neg P$
量詞否定：
$\neg (\forall x P (x)) \equiv \exists x \neg P (x)$ $\neg (\exists x P (x)) \equiv \forall x \neg P (x)$
奇數形式：
$n 是奇數 ⟺ n = 2 k + 1$
偶數形式：
$n 是偶數 ⟺ n = 2 k$
$\sqrt{2}$ 無理數證明的核心矛盾：
$gcd (a, b) = 1$
但又推出
$gcd (a, b) \geq 2$
Russell 悖論的核心問句：
$S \in S ?$

第二章：模運算

第二章涵蓋同餘、Bézout 等式、費馬小定理、歐拉定理、RSA 正確性，以及中國剩餘定理

同餘的定義與封閉性：掌握模運算下加法、乘法為何可合法運作
Bézout 等式：說明最大公因數可以表示成整數線性組合，並導出模反元素存在條件
費馬小定理與歐拉定理：提供 RSA 解密正確性的核心工具
RSA 正確性證明：證明若 $e d \equiv 1 (\mod (p - 1) (q - 1))$ ，則對任意訊息 $m$ 都有 $m^{e d} \equiv m (\mod p q) .$
中國剩餘定理：證明線性同餘方程組在兩兩互質模數下不但有解，而且解在總模數下唯一，並給出構造公式

一、模運算基礎理論

1.1 同餘的定義

給定整數 $a, b$ 與正整數 $m$ ，若

m ∣ (a - b)

則稱 $a$ 與 $b$ 模 $m$ 同餘，記作

a \equiv b (\mod m)

這表示 $a, b$ 除以 $m$ 具有相同餘數

1.2 同餘的基本性質

若

a \equiv b (\mod m), c \equiv d (\mod m)

則有：

加法相容性 $a + c \equiv b + d (\mod m)$
乘法相容性 $a c \equiv b d (\mod m)$

1.3 證明：加法相容性

由

a \equiv b (\mod m) \Rightarrow m ∣ (a - b)

c \equiv d (\mod m) \Rightarrow m ∣ (c - d)

可知存在整數 $k_{1}, k_{2}$ 使得

a - b = k_{1} m, c - d = k_{2} m

因此

(a + c) - (b + d) = (a - b) + (c - d) = (k_{1} + k_{2}) m

故

m ∣ ((a + c) - (b + d))

也就是

a + c \equiv b + d (\mod m)

證畢

1.4 證明：乘法相容性

同樣由

a - b = k_{1} m, c - d = k_{2} m

得

a = b + k_{1} m, c = d + k_{2} m

故

\begin{aligned} a c & = (b + k_{1} m) (d + k_{2} m) \\ = b d + m (k_{1} d + k_{2} b + k_{1} k_{2} m) \end{aligned}

因此

m ∣ (a c - b d)

所以

a c \equiv b d (\mod m)

證畢

二、Bézout 等式與模反元素

2.1 Bézout 等式

若 $a, b \in N$ ，且

d = gcd (a, b)

則存在整數 $x, y$ 使得

a x + b y = d

這就是 Bézout's Identity

2.2 證明：良序原理法

考慮集合

S = {a x + b y ∣ x, y \in Z, a x + b y > 0}

首先， $S$ 非空。例如取 $x = 1, y = 0$ ，若 $a > 0$ 則 $a \in S$

由自然數的良序性， $S$ 有最小元素，記為

d^{*} = a x^{*} + b y^{*}

我們要證明 $d^{*} = gcd (a, b)$

第一步：證明每個 $a, b$ 的公因數都整除 $d^{*}$

若 $c$ 同時整除 $a, b$ ，則存在整數 $k_{1}, k_{2}$ 使得

a = c k_{1}, b = c k_{2}

代入得

d^{*} = a x^{*} + b y^{*} = c (k_{1} x^{*} + k_{2} y^{*})

因此 $c ∣ d^{*}$

故所有公因數都不大於 $d^{*}$ ，所以

gcd (a, b) \leq d^{*}

第二步：證明 $d^{*}$ 本身就是 $a, b$ 的公因數

將 $a$ 除以 $d^{*}$ ，依除法演算法可寫成

a = q d^{*} + r, 0 \leq r < d^{*}

則

\begin{aligned} r & = a - q d^{*} \\ = a - q (a x^{*} + b y^{*}) \\ = a (1 - q x^{*}) - b (q y^{*}) \end{aligned}

因此 $r$ 也具有 $a x + b y$ 的形式。若 $r > 0$ ，則 $r \in S$ ，且 $r < d^{*}$ ，與 $d^{*}$ 是 $S$ 中最小正元素矛盾

所以只能有 $r = 0$ ，即

d^{*} ∣ a

同理可證

d^{*} ∣ b

因此 $d^{*}$ 是 $a, b$ 的公因數，故

d^{*} \leq gcd (a, b)

綜合兩步得到

d^{*} = gcd (a, b)

證畢

2.3 推論：模反元素存在條件

對整數 $a, m$ ，若

gcd (a, m) = 1

則存在整數 $x$ 使得

a x \equiv 1 (\mod m)

此時稱 $x$ 為 $a$ 在模 $m$ 下的反元素

證明

由 Bézout 等式，存在整數 $x, y$ 使得

a x + m y = 1

移項得

a x - 1 = - m y

故 $m ∣ (a x - 1)$ ，亦即

a x \equiv 1 (\mod m)

證畢

2.4 如何實際求出 $x, y$ ：擴展歐幾里得演算法

講義提到一個問題：已知存在 $x, y$ 使得

a x + b y = gcd (a, b)

那如何求？方法就是擴展歐幾里得演算法

以 $a = 18, b = 32$ 為例：

\begin{aligned} 32 & = 1 \cdot 18 + 14, \\ 18 & = 1 \cdot 14 + 4, \\ 14 & = 3 \cdot 4 + 2, \\ 4 & = 2 \cdot 2 + 0 \end{aligned}

所以

gcd (18, 32) = 2

代回去：

\begin{aligned} 2 & = 14 - 3 \cdot 4 \\ = 14 - 3 (18 - 14) \\ = 4 \cdot 14 - 3 \cdot 18 \\ = 4 (32 - 18) - 3 \cdot 18 \\ = 4 \cdot 32 - 7 \cdot 18 \end{aligned}

因此

2 = (- 7) \cdot 18 + 4 \cdot 32

所以一組係數為

x = - 7, y = 4

三、費馬小定理

3.1 定理敘述

若 $p$ 為質數，且 $gcd (a, p) = 1$ ，則

a^{p - 1} \equiv 1 (\mod p)

3.2 證明

考慮集合

{1, 2, 3, \dots, p - 1}

將每一個元素都乘上 $a$ ，得到

a, 2 a, 3 a, \dots, (p - 1) a

我們證明這些數在模 $p$ 下恰好是 $1, 2, \dots, p - 1$ 的重新排列

第一步：兩兩不全等

若對某 $1 \leq i, j \leq p - 1$ 有

a i \equiv a j (\mod p)

則

p ∣ a (i - j)

因為 $gcd (a, p) = 1$ ，而 $p$ 是質數，所以必有

p ∣ (i - j)

但 $i, j \in {1, 2, \dots, p - 1}$ ，故 $| i - j | < p$ ，只能推出

i = j

因此 $a, 2 a, \dots, (p - 1) a$ 在模 $p$ 下兩兩不同

第二步：都不會同餘於 $0$

若 $a i \equiv 0 (\mod p)$ ，則 $p ∣ a i$ 。由 $gcd (a, p) = 1$ 可得 $p ∣ i$ ，但 $1 \leq i \leq p - 1$ 不可能

故每個 $a i$ 都同餘於 $1, 2, \dots, p - 1$ 中某個元素

因此

{a, 2 a, \dots, (p - 1) a}

在模 $p$ 下只是

{1, 2, \dots, p - 1}

的一個排列，所以它們的乘積同餘：

(a \cdot 1) (a \cdot 2) \dots (a \cdot (p - 1)) \equiv 1 \cdot 2 \dots (p - 1) (\mod p)

整理得

a^{p - 1} (p - 1)! \equiv (p - 1)! (\mod p)

因為 $p$ 為質數，而 $(p - 1)!$ 的每個因子都小於 $p$ ，故

p ∤ (p - 1)!

因此可消去 $(p - 1)!$ ，得到

a^{p - 1} \equiv 1 (\mod p)

證畢

四、歐拉定理

講義中將此定理作為 remark 提及，此處補上完整複習版證明

4.1 定理敘述

若 $gcd (a, n) = 1$ ，則

a^{φ (n)} \equiv 1 (\mod n)

其中 $φ (n)$ 為 Euler totient function，表示 $1, 2, \dots, n$ 中與 $n$ 互質的正整數個數

4.2 證明

取模 $n$ 下的簡化剩餘系統（reduced residue system）

R = {r_{1}, r_{2}, \dots, r_{φ (n)}}

其中每個 $r_{i}$ 都與 $n$ 互質，且兩兩在模 $n$ 下不同

由於 $gcd (a, n) = 1$ ，則每個 $a r_{i}$ 也與 $n$ 互質，而若

a r_{i} \equiv a r_{j} (\mod n)

則

a (r_{i} - r_{j}) \equiv 0 (\mod n)

因 $a$ 在模 $n$ 下可逆，故推出

r_{i} \equiv r_{j} (\mod n)

所以 $i = j$ 。因此

{a r_{1}, a r_{2}, \dots, a r_{φ (n)}}

只是 $R$ 的另一種排列

故乘積同餘：

(a r_{1}) (a r_{2}) \dots (a r_{φ (n)}) \equiv r_{1} r_{2} \dots r_{φ (n)} (\mod n)

整理得

a^{φ (n)} r_{1} r_{2} \dots r_{φ (n)} \equiv r_{1} r_{2} \dots r_{φ (n)} (\mod n)

由於每個 $r_{i}$ 都與 $n$ 互質，所以其乘積也與 $n$ 互質，可在模 $n$ 下消去，得到

a^{φ (n)} \equiv 1 (\mod n)

證畢

4.3 特例： $φ (p q) = (p - 1) (q - 1)$

若 $p, q$ 為相異質數，則在 $1, 2, \dots, p q$ 中

被 $p$ 整除者有 $q$ 個
被 $q$ 整除者有 $p$ 個
被 $p q$ 同時整除者有 $1$ 個

由容斥原理，被 $p$ 或 $q$ 整除的數共有

p + q - 1

個，因此與 $p q$ 互質的數共有

p q - (p + q - 1) = (p - 1) (q - 1)

故

φ (p q) = (p - 1) (q - 1)

五、RSA 加密系統

5.1 系統設定

令 $p, q$ 為兩個大質數，設

n = p q, φ (n) = (p - 1) (q - 1)

選擇公鑰指數 $e$ ，使得

gcd (e, φ (n)) = 1

再選擇私鑰指數 $d$ 使

e d \equiv 1 (\mod φ (n))

公開金鑰： $(n, e)$
私密金鑰： $d$ （以及通常也保留 $p, q$ ）

若明文為 $m$ （通常假設 $0 \leq m < n$ ），則密文定義為

c \equiv m^{e} (\mod n)

解密時計算

c^{d} (\mod n)

5.2 為什麼 $d$ 一定存在？

因為要求 $gcd (e, φ (n)) = 1$ ，依 Bézout 等式，存在整數 $x, y$ 使得

e x + φ (n) y = 1

模 $φ (n)$ 取同餘得

e x \equiv 1 (\mod φ (n))

所以可取

d \equiv x (\mod φ (n))

這就是 $e$ 在模 $φ (n)$ 下的反元素

5.3 RSA 正確性命題

若 $p, q$ 為相異質數，且

e d \equiv 1 (\mod (p - 1) (q - 1))

則對任意整數 $m$ ，皆有

m^{e d} \equiv m (\mod p q)

這就是 RSA 解密正確性的核心

5.4 證明：對模 $p$ 與模 $q$ 分別驗證

由

e d \equiv 1 (\mod (p - 1) (q - 1))

可知存在整數 $k$ 使得

e d = 1 + k (p - 1) (q - 1)

我們先證明

m^{e d} \equiv m (\mod p)

分兩種情形：

情形 A： $p ∣ m$

則

m \equiv 0 (\mod p)

所以

m^{e d} \equiv 0 \equiv m (\mod p)

情形 B： $gcd (m, p) = 1$

由費馬小定理

m^{p - 1} \equiv 1 (\mod p)

因此

\begin{aligned} m^{e d} & = m^{1 + k (p - 1) (q - 1)} \\ = m \cdot (m^{p - 1})^{k (q - 1)} \\ \equiv m \cdot 1^{k (q - 1)} \\ \equiv m (\mod p) \end{aligned}

故無論哪種情形，都有

m^{e d} \equiv m (\mod p)

同理可證

m^{e d} \equiv m (\mod q)

因此

p ∣ (m^{e d} - m), q ∣ (m^{e d} - m)

而 $p, q$ 為相異質數，故 $gcd (p, q) = 1$ ，可得

p q ∣ (m^{e d} - m)

亦即

m^{e d} \equiv m (\mod p q)

證畢

5.5 用歐拉定理看 RSA

若額外假設

gcd (m, p q) = 1

則由歐拉定理

m^{φ (p q)} \equiv 1 (\mod p q)

且 $e d = 1 + k φ (p q)$ ，所以

m^{e d} = m^{1 + k φ (p q)} = m (m^{φ (p q)})^{k} \equiv m (\mod p q)

這是較簡潔的證法，但要處理一般 $m$ ，仍須像上一節那樣分模 $p, q$ 討論

5.6 安全性直觀

RSA 的安全性核心不在上述正確性，而在於：

已知公開金鑰 $(n, e)$ ，若想求出私鑰 $d$ ，通常需要知道 $φ (n) = (p - 1) (q - 1)$ 而這通常需要先分解 $n = p q$
當 $p, q$ 足夠大時，分解大整數 $n$ 是困難問題，因此能維持系統安全

六、中國剩餘定理（Chinese Remainder Theorem）

6.1 問題形式

考慮同餘方程組

{\begin{cases} x \equiv a_{1} (\mod m_{1}), \\ x \equiv a_{2} (\mod m_{2}), \\ ⋮ \\ x \equiv a_{n} (\mod m_{n}) \end{cases}

其中 $m_{1}, m_{2}, \dots, m_{n}$ 兩兩互質，且皆大於 $1$

中國剩餘定理要回答兩件事：

是否存在解？
若存在，是否唯一？

6.2 唯一性命題

若 $x_{1}, x_{2}$ 都是上述系統的解，則

x_{1} \equiv x_{2} (\mod m_{1} m_{2} \dots m_{n})

也就是說，解在模

M = m_{1} m_{2} \dots m_{n}

下是唯一的

6.3 證明：唯一性

由於 $x_{1}, x_{2}$ 都是解，對每個 $k = 1, 2, \dots, n$ 都有

x_{1} \equiv a_{k} (\mod m_{k})

x_{2} \equiv a_{k} (\mod m_{k})

相減得

x_{1} - x_{2} \equiv 0 (\mod m_{k})

亦即

m_{k} ∣ (x_{1} - x_{2})

對所有 $k$ 都成立

因為 $m_{1}, m_{2}, \dots, m_{n}$ 兩兩互質，所以它們的乘積也整除 $x_{1} - x_{2}$ ：

m_{1} m_{2} \dots m_{n} ∣ (x_{1} - x_{2})

因此

x_{1} \equiv x_{2} (\mod m_{1} m_{2} \dots m_{n})

證畢

6.4 中國剩餘定理

若 $m_{1}, m_{2}, \dots, m_{n}$ 兩兩互質，則系統

{\begin{cases} x \equiv a_{1} (\mod m_{1}), \\ x \equiv a_{2} (\mod m_{2}), \\ ⋮ \\ x \equiv a_{n} (\mod m_{n}) \end{cases}

在模

M = m_{1} m_{2} \dots m_{n}

下有唯一解

6.5 證明：存在性

令

M = m_{1} m_{2} \dots m_{n}, M_{k} = \frac{M}{m_{k}}

因為模數兩兩互質，所以對每個 $k$ ， $M_{k}$ 與 $m_{k}$ 互質：

gcd (M_{k}, m_{k}) = 1

由 Bézout 等式，可得存在整數 $y_{k}, z_{k}$ 使得

\begin{aligned} M_{k} y_{k} + m_{k} z_{k} = 1 \Rightarrow M_{k} y_{k} \equiv 1 (\mod m_{k}) \end{aligned}

現在構造

x = a_{1} M_{1} y_{1} + a_{2} M_{2} y_{2} + \dots + a_{n} M_{n} y_{n}

我們檢查它對每個模數 $m_{k}$ 的同餘值

對固定的 $k$ ，若 $j \neq k$ ，則 $M_{j}$ 包含因子 $m_{k}$ ，故

M_{j} \equiv 0 (\mod m_{k})

因此在模 $m_{k}$ 下，除了第 $k$ 項外其餘都消失：

x \equiv a_{k} M_{k} y_{k} (\mod m_{k})

又因為

M_{k} y_{k} \equiv 1 (\mod m_{k})

所以

x \equiv a_{k} (\mod m_{k})

這對所有 $k$ 都成立，因此 $x$ 確實是整個系統的一組解

再配合前述唯一性命題，便得知此解在模 $M$ 下唯一

證畢

6.6 構造演算法

實作上可以照以下步驟：

計算 $M = m_{1} m_{2} \dots m_{n}$
對每個 $k$ ，計算 $M_{k} = M / m_{k}$
找出 $y_{k}$ 使得 $M_{k} y_{k} \equiv 1 (\mod m_{k})$
令 $x = \sum_{k = 1}^{n} a_{k} M_{k} y_{k}$
最後將 $x$ 化簡成模 $M$ 下的代表元

七、範例：求解

{\begin{cases} x \equiv 2 (\mod 3), \\ x \equiv 3 (\mod 5), \\ x \equiv 2 (\mod 7) \end{cases}

7.1 計算各項

總模數為

M = 3 \cdot 5 \cdot 7 = 105

所以

M_{1} = 35, M_{2} = 21, M_{3} = 15

接著求反元素：

(1) 求 $y_{1}$

35 y_{1} \equiv 1 (\mod 3)

因為 $35 \equiv 2 (\mod 3)$ ，所以

2 y_{1} \equiv 1 (\mod 3)

可取

y_{1} = 2

(2) 求 $y_{2}$

21 y_{2} \equiv 1 (\mod 5)

因為 $21 \equiv 1 (\mod 5)$ ，故可取

y_{2} = 1

(3) 求 $y_{3}$

15 y_{3} \equiv 1 (\mod 7)

因為 $15 \equiv 1 (\mod 7)$ ，故可取

y_{3} = 1

7.2 組合解

由 CRT 公式

\begin{aligned} x & = 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \\ = 140 + 63 + 30 \\ = 233 \end{aligned}

模 $105$ 化簡：

233 \equiv 23 (\mod 105)

因此原方程組的唯一解（模 $105$ ）為

x \equiv 23 (\mod 105)

檢查：

23 \equiv 2 (\mod 3), 23 \equiv 3 (\mod 5), 23 \equiv 2 (\mod 7)

確認沒錯

八、知識結構總整理

8.1 證明鏈條

同餘定義：建立模運算語言
Bézout 等式：保證互質時模反元素存在
費馬小定理：提供質數模數下的冪循環規律
歐拉定理：將費馬小定理推廣到一般模數
RSA 正確性：結合「反元素存在」與「冪模運算定理」得到
中國剩餘定理：把分別在模 $p$ 、模 $q$ 下成立的結果，整合成模 $p q$ 下成立的結果

8.2 考前最該記住的式子

同餘定義：
$a \equiv b (\mod m) ⟺ m ∣ (a - b)$
Bézout 等式：
$gcd (a, b) = d \Rightarrow \exists x, y \in Z, a x + b y = d$
費馬小定理：
$gcd (a, p) = 1 \Rightarrow a^{p - 1} \equiv 1 (\mod p)$
歐拉定理：
$gcd (a, n) = 1 \Rightarrow a^{φ (n)} \equiv 1 (\mod n)$
RSA 關鍵條件：
$e d \equiv 1 (\mod (p - 1) (q - 1))$
RSA 正確性：
$m^{e d} \equiv m (\mod p q)$
CRT 構造公式：
$x = \sum_{k = 1}^{n} a_{k} M_{k} y_{k} M_{k} = \frac{M}{m_{k}} M_{k} y_{k} \equiv 1 (\mod m_{k})$

第三章

執行摘要

第三章涵蓋遞迴定義、Euclidean algorithm、弱歸納法、強歸納法、Fibonacci 數列、Lamé 定理，以及若干典型歸納題：

遞迴（recursion）：把問題拆成更小的同型問題
數學歸納法（induction）：證明某個命題對所有正整數成立
兩者的關聯：遞迴負責「定義或計算」，歸納法負責「證明遞迴或整體性質正確」

一、遞迴與 Euclidean algorithm

1.1 Euclidean algorithm 的基本形式

對於正整數 $a, b$ ，若 $b \neq 0$ ，則可寫成

a = k b + r

其中

k, r \in N \cup {0}, 0 \leq r < b

Euclidean algorithm 的核心事實是：

gcd (a, b) = {\begin{cases} b, & r = 0, \\ gcd (b, r), & r \neq 0 \end{cases}

這給出一個自然的遞迴演算法：

int gcd(int a, int b) // assuming b != 0
{
    int r = a % b;
    if (r == 0)
        return b;
    return gcd(b, r);
}

1.2 為什麼 $gcd (a, b) = gcd (b, r)$ ？

這是 Euclidean algorithm 正確性的核心

定理

若

a = b k + r

則

gcd (a, b) = gcd (b, r)

證明

我們證明兩邊互相不大於對方

先證

gcd (a, b) \leq gcd (b, r)

設 $d$ 是 $a, b$ 的任一公因數。則存在整數 $k_{1}, k_{2}$ 使得

a = k_{1} d, b = k_{2} d

又因為

a = k b + r

故

\begin{aligned} r & = a - k b \\ = k_{1} d - k (k_{2} d) \\ = (k_{1} - k k_{2}) d \end{aligned}

所以 $d ∣ r$ 。因此任何 $a, b$ 的公因數，同時也是 $b, r$ 的公因數

故

gcd (a, b) \leq gcd (b, r)

反過來，若 $d$ 是 $b, r$ 的公因數，則因為

a = b k + r

可知 $d ∣ a$ 。因此任何 $b, r$ 的公因數，也同時是 $a, b$ 的公因數

故

gcd (b, r) \leq gcd (a, b)

綜合可得

gcd (a, b) = gcd (b, r)

證畢

1.3 為什麼要要求 $0 \leq r < b$ ？

講義特別問到：在正確性證明裡，其實只需要 $r$ 是整數就夠了，那為什麼演算法還要要求

0 \leq r < b ?

答案是：為了保證演算法會在有限步內停止

因為每一次遞迴都把第二個參數從 $b$ 換成更小的非負整數 $r$ ，所以參數會嚴格下降：

b > r \geq 0

自然數不可能無限嚴格下降，因此演算法一定有限步結束

這種「每一步都讓某個非負整數嚴格減少，所以過程必停」的思路，在遞迴正確性與終止性證明裡非常常見

二、Euclidean algorithm 的步數上界

2.1 記號設定

令

r_{0} = a, r_{1} = b

不妨設

r_{0} \geq r_{1}

Euclidean algorithm 的每一步可寫成

\begin{aligned} r_{0} & = k_{1} r_{1} + r_{2}, \\ r_{1} & = k_{2} r_{2} + r_{3}, \\ r_{2} & = k_{3} r_{3} + r_{4}, \\ ⋮ \\ r_{n - 2} & = k_{n - 1} r_{n - 1} + r_{n}, \\ r_{n - 1} & = k_{n} r_{n} + 0 \end{aligned}

其中 $n$ 是總除法次數

2.2 第一個粗略上界

講義先給出一個簡單分析：

每一步都滿足 $r_{i - 1} \geq r_{i} > r_{i + 1}$
且每隔一步至少減半： $r_{i - 1} \geq 2 r_{i + 1}$

原因是商 $k_{i} \geq 1$ ，所以

r_{i - 1} = k_{i} r_{i} + r_{i + 1} \geq r_{i} + r_{i + 1} > r_{i + 1} + r_{i + 1} = 2 r_{i + 1}

因此：

r_{2} \leq \frac{r_{0}}{2}, r_{4} \leq \frac{r_{0}}{4}, r_{6} \leq \frac{r_{0}}{8}, \dots

若經過大約 $x$ 次「兩步縮半」，值已經小於 $1$ ，演算法就必須停止。於是可得到：

n \leq 2 \lg r_{0} + 1

這不是最精確的結果，但先說明了步數至多是對數級別

三、數學歸納法公理

3.1 敘述

數學歸納法公理可表述為：若 $S$ 是正整數集合的一個子集合，且滿足

$1 \in S$
$\forall n \in N, n \in S \Rightarrow n + 1 \in S$

則

S = N

3.2 與良序原理的關係

講義指出：這和良序原理（well-ordering axiom） 等價

其直觀意思是：

若一個性質從 $1$ 開始成立
而且只要對 $n$ 成立就會對 $n + 1$ 成立
那它就會一路傳下去，對所有正整數都成立

這是很多「對所有正整數」的證明的標準模板

四、弱歸納法（weak induction）

4.1 標準形式

若要證明命題 $P (n)$ 對所有 $n \geq x$ 成立，需要兩步：

Basis step

證明

P (x)

成立

Inductive step

證明對所有 $k \geq x$

P (k) \Rightarrow P (k + 1)

如此即可推出：對所有 $n \geq x$ ， $P (n)$ 都成立

4.2 弱歸納法的精神

弱歸納法的想法非常簡單：

先把第一塊骨牌推倒
再證明每一塊骨牌倒下都會推倒下一塊
因此所有骨牌都會倒

五、範例一：證明 $1 + 2 + \dots + n = \frac{n (n + 1)}{2}$

5.1 命題

對所有 $n \in N$

1 + 2 + \dots + n = \frac{n (n + 1)}{2}

5.2 證明（弱歸納法）

令

P (n) : 1 + 2 + \dots + n = \frac{n (n + 1)}{2}

Basis step

當 $n = 1$ 時

1 = \frac{1 \cdot 2}{2}

所以 $P (1)$ 成立

Inductive step

假設對某個 $k \in N$ ， $P (k)$ 成立，即

1 + 2 + \dots + k = \frac{k (k + 1)}{2}

要證明 $P (k + 1)$ ，也就是

1 + 2 + \dots + k + (k + 1) = \frac{(k + 1) (k + 2)}{2}

由歸納假設

\begin{aligned} 1 + 2 + \dots + k + (k + 1) & = (1 + 2 + \dots + k) + (k + 1) \\ = \frac{k (k + 1)}{2} + (k + 1) \\ = \frac{k (k + 1) + 2 (k + 1)}{2} \\ = \frac{(k + 1) (k + 2)}{2} \end{aligned}

因此 $P (k + 1)$ 成立

故由數學歸納法，對所有 $n \in N$

1 + 2 + \dots + n = \frac{n (n + 1)}{2}

證畢

六、範例二：12 分以上郵資都可由 4 分與 5 分郵票組成

6.1 命題

對所有 $n \geq 12$ ，金額 $n$ 都可以寫成

4 a + 5 b

的形式，其中 $a, b \in Z_{\geq 0}$

6.2 弱歸納法證明

令

P (n) : 郵資 n 可以由 4 分與 5 分郵票組成。

Basis step

12 = 4 + 4 + 4

所以 $P (12)$ 成立

Inductive step

假設對某個 $k \geq 12$ ， $P (k)$ 成立。也就是說， $k$ 可以用 4 分與 5 分郵票組成。要證明 $P (k + 1)$

講義的想法是分情況：

情況 1：表示 $k$ 的方法中用到了至少一張 4 分郵票

把其中一張 4 分郵票改成 5 分郵票，總金額就會從 $k$ 變成 $k + 1$

因此 $P (k + 1)$ 成立

情況 2：表示 $k$ 的方法中完全沒有 4 分郵票

那麼 $k$ 全由 5 分郵票組成。因為 $k \geq 12$ ，至少有三張 5 分郵票

把三張 5 分郵票換成四張 4 分郵票，總金額由

15

變成

16

因此總金額也增加 1，從 $k$ 變成 $k + 1$

故 $P (k + 1)$ 成立

於是對所有 $n \geq 12$ ， $P (n)$ 都成立

證畢

6.3 這個證明的特點

這個弱歸納證明雖然正確，但技巧性比較強，因為它要分析「表示 $k$ 的方式」長什麼樣子，再用替換郵票的方法把 $k$ 變成 $k + 1$

同一題若用強歸納法，通常概念更乾淨

七、強歸納法（strong induction）

7.1 標準形式

若要證明 $P (n)$ 對所有 $n \geq x$ 成立，強歸納法的結構是：

Basis step

證明

P (x)

成立

Inductive step

對任意 $k \geq x$ ，假設

P (x), P (x + 1), \dots, P (k)

全部都成立，然後證明

P (k + 1)

成立

7.2 與弱歸納法的差別

表面上，強歸納法的假設比較強，因為它一次假設從 $x$ 到 $k$ 全都成立，而不是只假設 $P (k)$

但講義最後會證明：強歸納法與弱歸納法其實是等價的

也就是說，兩者在邏輯上沒有差別，只是使用時的形式不同

八、範例三：兩堆同數量火柴的遊戲

8.1 遊戲規則

兩位玩家輪流操作
每回合可從兩堆中的其中一堆拿走任意正數量火柴
拿走最後一根火柴者獲勝

命題

若遊戲一開始兩堆火柴數量相同，則第二位玩家必勝

8.2 為什麼這題自然適合強歸納？

因為第一位玩家第一步可能拿走 $1$ 根、 $2$ 根、一直到全部拿光。第二位玩家回應後，剩下來的局面可能是任意較小規模的「兩堆相同數量」局面。因此歸納時需要同時知道很多較小情況都可贏，這正是強歸納法的典型使用場景

8.3 證明（強歸納法）

令

P (n) : 若一開始兩堆各有 n 根火柴，則第二位玩家必勝。

Basis step

當 $n = 1$ 時，第一位玩家只能從其中一堆拿走那一根，留下另一堆一根火柴。第二位玩家拿走最後一根，獲勝

故 $P (1)$ 成立

Inductive step

假設對某個 $k \geq 1$

P (1), P (2), \dots, P (k)

都成立。要證明 $P (k + 1)$

考慮一開始兩堆各有 $k + 1$ 根火柴。第一位玩家第一步從某一堆拿走 $r$ 根，其中

1 \leq r \leq k + 1

分兩種情況：

情況 1： $r = k + 1$

第一位玩家把其中一整堆拿光。此時另一堆仍有 $k + 1$ 根。第二位玩家把另一堆全部拿光，立刻獲勝

情況 2： $1 \leq r \leq k$

第一位玩家操作後，兩堆變成：

k + 1 - r, k + 1

第二位玩家從另一堆也拿走 $r$ 根，局面就變成兩堆各有

k + 1 - r

根火柴

由於 $1 \leq r \leq k$ ，所以

1 \leq k + 1 - r \leq k

根據歸納假設，從這個局面開始，後手必勝。也就是說，第二位玩家在完成鏡射操作後，可以保證最終獲勝

因此 $P (k + 1)$ 成立

故由強歸納法，對所有 $n \in N$ ， $P (n)$ 成立

證畢

8.4 這題的核心策略

這題的本質其實是鏡射策略（mirror strategy）

只要在自己的回合把局面重新變回「兩堆相等」，第二位玩家就能一直把對手的操作鏡射回去，最後獲勝

九、同一郵票題的強歸納版本

9.1 直覺想法

若已知某個較小的金額 $k - 3$ 可以湊出來，那麼只要再加一張 4 分郵票，就能得到

(k - 3) + 4 = k + 1

這正是強歸納法比弱歸納法方便的地方：我們可以直接使用較早的某個狀態，而不是只能用 $k$ 推 $k + 1$

9.2 錯誤示範

講義舉了個錯誤示範，假如你想直接用強歸納法證明：

P (n) : 每一個 n \geq 12 的郵資，都可以只用 4-cent 與 5-cent 郵票湊出來

它的想法是這樣：

基底只先證明 $P (12)$
歸納的某一步想證明：若 $P (12) \land P (13) \land \dots \land P (k)$ 成立，則可推出 $P (k + 1)$
推出的方法是：若已知 $P (k - 3)$ ，那麼在構造 $k - 3$ 分郵資的方法上再多貼一張 4-cent 郵票，就得到 $k + 1$ 分郵資

這個想法本身沒有錯，因為

(k - 3) + 4 = k + 1

所以只要 $P (k - 3)$ 已經成立，確實可以推出 $P (k + 1)$

問題出在：你不一定真的已經知道 $P (k - 3)$ 成立

強歸納法的歸納假設是：

P (12), P (13), \dots, P (k)

全部都成立

也就是說，你只能使用編號介於 $12$ 到 $k$ 之間的那些命題

因此，若你想在證明 $P (k + 1)$ 時使用 $P (k - 3)$ ，就必須先確認：

k - 3 \geq 12

否則 $P (k - 3)$ 根本不在歸納假設涵蓋的範圍裡，你就沒有資格用它

現在來看前幾個最小的情況：

若 $k = 12$ ，那麼要證 $P (13)$ 時，需要用到
$P (k - 3) = P (9)$
但 $P (9)$ 不在
$P (12), P (13), \dots, P (k)$
的範圍裡
若 $k = 13$ ，那麼要證 $P (14)$ 時，需要用到
$P (k - 3) = P (10)$
同樣不在歸納假設範圍內
若 $k = 14$ ，那麼要證 $P (15)$ 時，需要用到
$P (k - 3) = P (11)$
也仍然不在歸納假設範圍內

所以，雖然講義寫的是「從 $P (k - 3)$ 推到 $P (k + 1)$ 」，但這個做法只有在

k - 3 \geq 12

也就是

k \geq 15

時才合法

這就是不完整的地方，歸納的某一步其實不是對所有 $k \geq 12$ 都能直接用，而是只能對 $k \geq 15$ 才能用。因此如果基底只證 $P (12)$ ，那麼：

$P (13)$ 還沒被證明
$P (14)$ 還沒被證明
$P (15)$ 也還沒被證明

整個歸納鏈就接不起來

9.3 正確證明（強歸納法）

令

P (n) : 郵資 n 可以由 4 分與 5 分郵票組成

Basis steps

12 = 4 + 4 + 4

13 = 4 + 4 + 5

14 = 4 + 5 + 5

15 = 5 + 5 + 5

因此

P (12), P (13), P (14), P (15)

全部成立

Inductive step

假設對某個 $k \geq 15$

P (12), P (13), \dots, P (k)

都成立。要證明 $P (k + 1)$

由於 $k \geq 15$ ，所以

k - 3 \geq 12

因此 $P (k - 3)$ 在歸納假設範圍內成立。也就是說， $k - 3$ 可以由 4 分與 5 分郵票組成

再多加一張 4 分郵票，就得到 $k + 1$

故 $P (k + 1)$ 成立

因此對所有 $n \geq 12$ ， $P (n)$ 都成立

證畢

9.4 這題反映的原則

若歸納的某一步用到的是

P (k - c)

而不是 $P (k)$ ，就要特別檢查前幾個小值會不會掉出已知範圍。若會，就要補足足夠多的 basis cases

這是強歸納最常見的失誤之一

十、遞迴定義：Fibonacci 數列

10.1 定義

Fibonacci 數列為：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, \dots

若以 $f (n)$ 表示第 $n$ 個 Fibonacci 數（ $n \geq 0$ ），則

f (n) = {\begin{cases} 0, & n = 0, \\ 1, & n = 1, \\ f (n - 1) + f (n - 2), & n \geq 2 \end{cases}

這是一個標準的遞迴定義：

先給初始值
再用較小的值定義較大的值

十一、範例四：Fibonacci 的指數下界

11.1 命題

令

α = \frac{1 + \sqrt{5}}{2}

則對所有 $n \geq 3$

f (n) > α^{n - 2}

11.2 證明（強歸納法）

令命題為

P (n) : f (n) > α^{n - 2}

Basis step

當 $n = 3$ 時

f (3) = 2 > α

因為

α = \frac{1 + \sqrt{5}}{2} \approx 1.618

故 $P (3)$ 成立

另外講義也提醒：若歸納的某一步會用到 $f (k - 1)$ ，那在最小情況 $k = 3$ 時要另外檢查 $P (4)$ ：

f (4) = 3 > α^{2}

故 $P (4)$ 也成立

Inductive step

假設對某個 $k \geq 4$

P (3), P (4), \dots, P (k)

都成立。要證明 $P (k + 1)$

由 Fibonacci 定義

f (k + 1) = f (k) + f (k - 1)

利用歸納假設

\begin{aligned} f (k + 1) & = f (k) + f (k - 1) \\ > α^{k - 2} + α^{k - 3} \\ = α^{k - 3} (α + 1) \end{aligned}

而黃金比例滿足

α^{2} = α + 1

因此

\begin{aligned} f (k + 1) & > α^{k - 3} (α + 1) \\ = α^{k - 3} α^{2} \\ = α^{k - 1} \end{aligned}

故 $P (k + 1)$ 成立

所以對所有 $n \geq 3$

f (n) > α^{n - 2}

證畢

11.3 為什麼這題適合強歸納？

因為 Fibonacci 的遞迴式本身就依賴前兩項：

f (n) = f (n - 1) + f (n - 2)

若要證明第 $k + 1$ 項的性質，自然要同時使用 $k$ 與 $k - 1$ 兩項的性質，因此強歸納或「兩步歸納」都非常自然

十二、Lamé 定理：Euclidean algorithm 的精確步數上界

12.1 定理敘述

設 $a, b \in N$ ，Euclidean algorithm 計算

gcd (a, b)

共做了 $n$ 次除法。則 $n$ 至多是

5 \times (min {a, b} 的十進位位數)

的量級。更精確地，若 $b = min {a, b}$ ，則可得

n \leq 5 ⌊ \log_{10} b ⌋ + 6

12.2 證明思路總覽

Lamé 定理的關鍵是利用 Fibonacci 數列給出更緊的下界：若演算法做了 $n$ 步，則餘數序列必須至少像 Fibonacci 那樣大，因此初始輸入 $b$ 不能太小

換句話說：

步數很多代表餘數下降得很慢
而下降最慢的極端情況，正是 Fibonacci 型態

12.3 第一個觀察

仍用

r_{0} = a, r_{1} = b, \dots, r_{n}

表示 Euclidean algorithm 中的餘數序列

因為每個商 $k_{i} \geq 1$ ，所以

r_{i - 1} = k_{i} r_{i} + r_{i + 1} \geq r_{i} + r_{i + 1}

也就是說：

r_{i - 1} \geq r_{i} + r_{i + 1}

這正是 Fibonacci 型遞推不等式

12.4 關鍵引理

Claim

對所有 $i \in {0, 1, \dots, n}$

r_{n - i} \geq f (i + 2)

證明（反向歸納）

以 $i$ 為歸納參數

Basis cases

當 $i = 0$ 時

r_{n} \geq 1 = f (2)

因為最後一個非零餘數必為正整數

當 $i = 1$ 時

由最後一步

r_{n - 1} = k_{n} r_{n}

且 $k_{n} \geq 1$ ，實際上因為最後一步餘數為 $0$ ，且數列是嚴格遞增的，因此有 $r_{n - 1} \geq 2$ ，所以

r_{n - 1} \geq 2 = f (3)

Inductive step

假設對某個 $i \geq 1$

r_{n - i} \geq f (i + 2), r_{n - (i - 1)} \geq f (i + 1)

則由不等式

r_{n - (i + 1)} \geq r_{n - i} + r_{n - (i - 1)}

可得

\begin{aligned} r_{n - (i + 1)} & \geq f (i + 2) + f (i + 1) \\ = f (i + 3) \end{aligned}

故命題成立

因此對所有 $i$

r_{n - i} \geq f (i + 2)

證畢

12.5 由 Fibonacci 下界推出步數上界

把上面結論代入 $i = n - 1$ ，可得

r_{1} = b \geq f (n + 1)

而 Fibonacci 指數成長，講義使用估計

f (n + 1) > α^{n - 1}, α = \frac{1 + \sqrt{5}}{2} > \frac{1 + 2.2}{2} = 1.6

因此

b > {1.6}^{n - 1}

取常用對數可得

\log b > (n - 1) \log 1.6

而

\log 1.6 > \frac{1}{5}

所以

\log b > \frac{n - 1}{5}

整理得

n < 5 \log b + 1

再利用整數取整，即得

n \leq 5 ⌊ \log b ⌋ + 6

證畢

12.6 定理的意義

Lamé 定理說明：Euclidean algorithm 非常快。即使輸入是很大的整數，它的步數也只會隨數字位數線性成長，也就是對數等級的效率

這也是為什麼 gcd 計算在數論與密碼學裡能被大量使用

十三、握手問題

13.1 題意

有 $n$ 對夫妻參加聚會（總共有 $2 n + 2$ 人）。主人詢問所有客人與自己的妻子（問了 $2 n + 1$ 人），得到總共 $2 n + 1$ 個互不相同的握手數。已知沒有人和自己的配偶握手，問女主人握了幾次手

13.2 正確答案

女主人握了

n

次手

13.3 為什麼？

題目說：

主人去問了「所有客人」以及「自己的妻子」
因此被問到的人共有 $2 n + 1$ 個
這 $2 n + 1$ 個人的回答彼此都不相同
沒有人會和自己握手
也沒有人會和自己的配偶握手

因為每個人最多只能和其餘 $2 n$ 人握手（不能和自己或配偶握），因此每個人的握手次數一定落在

0, 1, 2, \dots, 2 n

而既然主人聽到的是 $2 n + 1$ 個彼此不同的答案，那這些答案必然就是

0, 1, 2, \dots, 2 n

接著注意：

握 $0$ 次的人，其配偶必然握 $2 n$ 次
握 $1$ 次的人，其配偶必然握 $2 n - 1$ 次
一般地，握 $k$ 次的人，其配偶握 $2 n - k$ 次

先看那個回答 $0$ 的人，這表示他沒有和任何人握手，所以如果在場的其他人有和他握手，那就會矛盾，因此：

他的配偶不可能和他握手（因為是夫妻）
但他的配偶可以和其他所有人握手

而除了自己與配偶之外，一個人最多本來就只能和 $2 n$ 個人握手

如果他的配偶少跟任何一個人握手，那麼那個人就不可能達到題目要求的整體互異結構。更直接地說：既然答案中已經有 $0$ ，而所有答案又必須剛好是 $0, 1, \dots, 2 n$ ，那唯一能拿到最大值 $2 n$ 的人就只能是這個回答 $0$ 的人的配偶，見以下

$A$ 握了 $0$ 次，所以沒跟任何人握手
$C$ 握了 $2 n$ 次，所以 $C$ 跟所有非配偶的人都握過手
但 $C$ 不可能跟 $A$ 握過手
所以 $A$ 只能是 $C$ 的配偶

把握 $0$ 次的人和握 $2 n$ 次的人這對夫妻移掉之後，剩下的人會形成一個較小但結構完全相同的問題，原因是：

原本總共有 $n + 1$ 對夫妻（包含主人夫妻）
拿掉一對夫妻後，剩下 $n$ 對夫妻
剩下的每個人仍然不會和自己的配偶握手
在剩下的人之中，原本和那位「握 $2 n$ 次的人」握過手的人，現在大家的握手數都同時減 1
於是原本（拿掉 $0$ 和 $2 n$ 後）的答案集合 $1, 2, 3, \dots, 2 n - 1$ 會整齊地變成 $0, 1, 2, \dots, 2 n - 2$

所以剩下的人又形成同樣的型態，於是可以再重複同樣的論證：

在剩下的人裡，握 $0$ 次的人和握 $2 n - 2$ 次的人是一對夫妻
對應回原本的編號，就是握 $1$ 次與握 $2 n - 1$ 次的是夫妻

再繼續做下去，就會得到：

\begin{aligned} 0 & \leftrightarrow 2 n \\ 1 & \leftrightarrow 2 n - 1 \\ 2 & \leftrightarrow 2 n - 2 \end{aligned}

一直到中間為止。因此握手數為 $k$ 的人，其配偶的握手數必為

2 n - k

從上面的配對可知，所有被問到的人都會成對出現：

(0, 2 n), (1, 2 n - 1), (2, 2 n - 2), \dots

這些配對每一對的和都是

2 n

而一共有 $2 n + 1$ 個互不相同的數：

0, 1, 2, \dots, 2 n

因為總共有奇數個數，所以把兩端這樣一對一對配掉後，最後一定會剩下唯一的中間值：

n

例如：

若是 $0$ 到 $6$ ，配對為 $(0, 6), (1, 5), (2, 4)$ ，剩下 $3$
若是 $0$ 到 $8$ ，配對為 $(0, 8), (1, 7), (2, 6), (3, 5)$ ，剩下 $4$

所以在一般情況下，剩下的一定是

n

下一個問題是：為什麼剩下的那個人一定是女主人？這是因為主人沒有被問，所以在那 $2 n + 1$ 個互不相同的答案裡，不包含主人自己的握手數

但題目有一個很重要的事實：

主人和女主人是夫妻
依照剛剛的配對規律，夫妻的握手數一定互補為 $k \leftrightarrow 2 n - k$

但是：

所有不是中間值的數，都必須和另一個數配成夫妻
若女主人拿的不是中間值，那她就必須和某個也在回答列表中的人配對，這不可能，因為她的配偶是主人，而主人不在回答列表中

因此女主人不能拿任何成對的數，只能拿那個唯一不需要配對對象的中間值。由此可知女主人的握手數只能是

n

可以，下面是我幫你重寫後、邏輯更乾淨也比較適合拿去當筆記的版本

1 \in S

且對所有 $k \in N$ ，都有

k \in S \Rightarrow k + 1 \in S

那麼可推出

S = N

強歸納法

若滿足：

1 \in S

且對所有 $k \in N$ ，都有

(1 \in S \land 2 \in S \land \dots \land k \in S) \Rightarrow k + 1 \in S

那麼可推出

S = N

14.2 由強歸納法推出弱歸納法

現在假設強歸納法公理成立，我們要證明弱歸納法公理也成立，證法的形式是：

先假設某個集合 $S$ 滿足弱歸納法的前提
再證明這個 $S$ 其實也滿足強歸納法的前提
因為我們現在假設「強歸納法公理成立」，所以可推出 $S = N$

這樣就完成了「弱歸納法成立」

設 $S \subseteq N$ 滿足

1 \in S

且

\forall k \in N, k \in S \Rightarrow k + 1 \in S

我們要證明 $S = N$

已知

1 \in S, 2 \in S, \dots, k \in S

因此可知

k \in S

再由題設的弱歸納法條件可得

k \in S \Rightarrow k + 1 \in S

所以便可推出

(1 \in S \land 2 \in S \land \dots \land k \in S) \Rightarrow k + 1 \in S

這正好就是強歸納法所要求的遞推形式。再加上 $1 \in S$ ，由強歸納法可得

S = N

因此，若強歸納法成立，則弱歸納法也成立

14.3 由弱歸納法推出強歸納法

接著假設弱歸納法成立，我們要證明強歸納法也成立

設 $S \subseteq N$ 滿足

1 \in S

且對所有 $k \in N$ ，都有

(1 \in S \land 2 \in S \land \dots \land k \in S) \Rightarrow k + 1 \in S

我們要證明

S = N

這個方向的技巧是：另外定義一個新集合

S^{'} = {i : 1 \in S \land 2 \in S \land \dots \land i \in S}

這裡的意思是：

元素是 $i$
而且 $i$ 必須是自然數
並且要滿足「從 $1$ 到 $i$ 全都在 $S$ 裡」

所以：

若 $i = 1$ ，那要求的是 $1 \in S$
若 $i = 2$ ，那要求的是 $1, 2 \in S$
若 $i = 3$ ，那要求的是 $1, 2, 3 \in S$
若 $i = 10$ ，那要求的是 $1, 2, \dots, 10 \in S$

現在改對 $S^{'}$ 使用弱歸納法

Basis step

由於已知 $1 \in S$ ，而且 $1$ 的前面那串數只有自己，所以可得

1 \in S^{'}

Inductive step

假設

k \in S^{'}

根據 $S^{'}$ 的定義，這表示

1, 2, \dots, k \in S

而題設對 $S$ 的強歸納型條件告訴我們：只要

1, 2, \dots, k \in S

就能推出

k + 1 \in S

所以可知

1, 2, \dots, k, k + 1 \in S

也就是說

k + 1 \in S^{'}

因此我們證明了

k \in S^{'} \Rightarrow k + 1 \in S^{'}

由於又有 $1 \in S^{'}$ ，根據弱歸納法可得

S^{'} = N

最後，由 $S^{'}$ 的定義可知：只要 $k \in S^{'}$ ，就一定有 $k \in S$ 。因此

N = S^{'} \subseteq S \subseteq N

所以只能是

S = N

因此，若弱歸納法成立，則強歸納法也成立

十五、考前最該背住的內容

Euclidean algorithm 的核心等式：
$gcd (a, b) = gcd (b, r)$
弱歸納法格式：
$P (x), P (k) \Rightarrow P (k + 1)$
強歸納法格式：
$P (x) \land P (x + 1) \land \dots \land P (k) \Rightarrow P (k + 1)$
Fibonacci 遞迴：
$f (n) = f (n - 1) + f (n - 2)$
黃金比例恆等式：
$α^{2} = α + 1, α = \frac{1 + \sqrt{5}}{2}$
Lamé 定理的精神：
Euclidean algorithm 的最壞情況與 Fibonacci 數列有關，因此步數只有對數級
強弱歸納等價：
它們是同一件事的兩種寫法