自然常數 e 的無理性證明

▪ 預備知識：\(e\) 的無窮級數定義

首先，我們將自然常數 \(e\) 定義為以下無窮級數的總和（在此默認該級數是收斂的）：

\[e = \sum_{k=0}^{\infty} \frac{1}{k!} = \frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \dots\]

有了這個基本工具後，我們的證明將分成兩個階段來推進。

---

▪ 第一階段：範圍估計（證明 \(2 < e < 3\)）

我們先確定 \(e\) 的範圍，確保「\(e\) 不是整數」。

1.  \(e > 2\)

只需要看級數的前兩項：

\[e > \frac{1}{0!} + \frac{1}{1!} = 1 + 1 = 2\]

因為後續的項（\(\frac{1}{2!}, \frac{1}{3!}, \dots\)）通通都是正數，所以 \(e\) 必定大於 2。

2.  \(e < 3\)

使用「疊鏡級數（Telescoping Series）」放縮技巧。我們將分母的階乘進行連續兩整數相乘的放縮：

• \(\frac{1}{2!} = \frac{1}{1 \times 2} = \left( \frac{1}{1} - \frac{1}{2} \right)\)
• \(\frac{1}{3!} = \frac{1}{1 \times 2 \times 3} < \frac{1}{2 \times 3} = \left( \frac{1}{2} - \frac{1}{3} \right)\)
• \(\frac{1}{4!} = \frac{1}{1 \times 2 \times 3 \times 4} < \frac{1}{3 \times 4} = \left( \frac{1}{3} - \frac{1}{4} \right)\)

以此類推，整個級數可以放縮並拆項寫成：

\[e < 1 + 1 + \left(\frac{1}{1} - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \left(\frac{1}{3} - \frac{1}{4}\right) + \dots\]

除了前兩項 $1 + 1$ ，後面各項括號的正負項全部對消，最後只剩下：

\[e < 1 + 1 + 1 = 3\]

既然\(2 < e < 3\)，那麼自然常數 \(e\) 絕對不是整數。

---

▪ 第二階段：反證法

1. 做出反證假設

假設 \(e\) 是一個有理數。

既然是有理數，它就可以被表示為最簡分數：

\[e = \frac{p}{q}\]

其中 \(p\) 與 \(q\) 是互質的正整數。又因前文已論證 \(e\) 不是整數，所以分母 \(q\) 絕對不等於 1，也就是說：

\[q > 1\]

2. 拆分級數與同乘 \(q!\)

我們把 \(e\) 的無窮級數在分母為 \(q!\) 的項的地方切開，拆分成「前半段有限項」與「後半段無窮尾巴」兩部分：

\[\frac{p}{q} = \sum_{k=0}^{q} \frac{1}{k!} + \sum_{k=q+1}^{\infty} \frac{1}{k!}\]

接著將前半段移項到左邊，讓無窮級數的尾巴單獨留在右邊：

\[0 < \frac{p}{q} - \sum_{k=0}^{q} \frac{1}{k!} = \sum_{k=q+1}^{\infty} \frac{1}{k!}\]

關鍵步驟：將不等式各項同乘以 \(q!\)：

\[0 < p(q-1)! - \sum_{k=0}^{q} \frac{q!}{k!} = \sum_{k=q+1}^{\infty} \frac{q!}{k!}\]

3. 矛盾

左式是一個整數

\(p(q-1)!\) 顯然是一個整數。而在 \(\sum_{k=0}^{q} \frac{q!}{k!}\) 這一串展開式中，因為每一項的指標 \(k \le q\)，所以分母的 \(k!\) 一定會被分子的 \(q!\) 整除（例如 \(\frac{q!}{q!}=1, \frac{q!}{(q-1)!}=q\) 等等）。這意味著裡面的每一項通通都是整數，加起來自然也是整數。兩個整數相減，結果必然也是整數。再結合大於 0 的條件，左式是一個大於 0 的正整數。

右式是一個小於 1 的分數

將右式的無窮級數展開： \[ \begin{align*} \sum_{k=q+1}^{\infty} \frac{q!}{k!} &= \frac{q!}{(q+1)!} + \frac{q!}{(q+2)!} + \frac{q!}{(q+3)!} + \dots \\ &= \frac{1}{q+1} + \frac{1}{(q+1)(q+2)} + \frac{1}{(q+1)(q+2)(q+3)} + \dots \end{align*} \] 接著進行估計，再度進行放縮，把分母中的 \((q+2), (q+3)\) 等等通通替換成較小的 \((q+1)\)。分母變小，分數就會變大： \[\text{右式} < \frac{1}{q+1} + \frac{1}{(q+1)^2} + \frac{1}{(q+1)^3} + \dots\] 這是一個無窮等比級數，首項 \(a = \frac{1}{q+1}\), 公比 \(r = \frac{1}{q+1}\)。套用無窮等比級數求和公式 $\frac{a}{1-r}$ 得：

\[\text{右式} < \frac{\frac{1}{q+1}}{1 - \frac{1}{q+1}} = \frac{1}{(q+1) - 1} = \frac{1}{q}\]

前文已論證 \(q > 1\) ，那麼 \(\frac{1}{q}\) 必然小於 1。也就是說，右式是一個嚴格小於 1 的分數。

---

▪ 結論

綜上所述，我們得到

🚨 矛盾 \[0 < \text{某個整數} < 1\]

這意味我們最初的假設「假設 \(e\) 是有理數」是錯誤的。因此自然常數 \(e\) 必然是一個無理數。 

(證明終了)

📖 參考文獻

Alsina, C., & Nelsen, R. B. (2010). Charming Proofs: A Journey Into Elegant Mathematics. Mathematical Association of America.

去程與回程的線路安排問題

=問題=

從甲地到乙地有 $12$ 條道路，其中有 $5$ 條雙向道， $4$ 條由甲地到乙地的單行道， $3$ 條由乙地到甲地的單行道。求從甲地到乙地再回到甲地，且去程與回程走不同的路，共有多少種路線安排？

=解答=

$(1^\circ)$ 符號化與道路分類

首先，我們將這 $12$ 條道路在「去程」與「回程」時的可用性，進行精簡的符號化分類：

• $A$（雙向道）：共 $5$ 條。（去程、回程皆可通）
• $B$（甲 $\rightarrow$ 乙 單行道）：共 $4$ 條。（僅去程可通）
• $C$（乙 $\rightarrow$ 甲 單行道）：共 $3$ 條。（僅回程可通）

這時，我們可以很清晰地列出「去程」與「回程」的可選路徑範圍：

• 去程只能選擇：$A$ 或 $B$
• 回程只能選擇：$A$ 或 $C$

$(2^\circ)$ 分類討論

由於題目規定「去程與回程走不同的路」，我們依據「去程選什麼路 $\rightarrow$ 回程選什麼路」的決策順序，將所有可能的情境拆解為以下四種互斥的走法：

【第一類：$A \rightarrow A$】去程走雙向，回程也走雙向

• 去程：有 $5$ 條雙向道 $A$ 可以選擇。
• 回程：因為去程已經走過其中 $1$ 條雙向道，且去回不能重複，所以回程可選的雙向道只剩下 $5 - 1 = 4$ 條。
• 此類走法：根據乘法原理，共有

$$5 \times 4 = 20 \text{ 種}$$

【第二類：$A \rightarrow C$】去程走雙向，回程走單行

• 去程：有 $5$ 條雙向道 $A$ 可以選擇。
• 回程：回程選擇的是乙 $\rightarrow$ 甲的單行道 $C$（共 $3$ 條）。因為去程走的是 $A$，回程走的是 $C$，兩者完全沒有交集，所以不需要扣除任何路徑。
• 此類走法：根據乘法原理，共有$$5 \times 3 = 15 \text{ 種}$$

【第三類：$B \rightarrow A$】去程走單行，回程走雙向

• 去程：選擇甲 $\rightarrow$ 乙的單行道 $B$（共 $4$ 條）。
• 回程：選擇雙向道 $A$（共 $5$ 條）。因為去程完全沒有走過雙向道 $A$，所以回程的 $5$ 條雙向道皆可自由挑選，不需扣除。
• 此類走法：根據乘法原理，共有$$4 \times 5 = 20 \text{ 種}$$

【第四類：$B \rightarrow C$】去程走單行，回程也走單行

• 去程：選擇單行道 $B$（共 $4$ 條）。
• 回程：選擇單行道 $C$（共 $3$ 條）。去程與回程所選的道路集合完全互斥。
• 此類走法：根據乘法原理，共有$$4 \times 3 = 12 \text{ 種}$$

$(3^\circ)$ 匯整結果

上述四種情境彼此互斥，由加法原理，我們將四種情境的所有可能走法相加，即為最終所有的線路安排總數：

$$20 + 15 + 20 + 12 = 67 \text{ 種}$$

（解答終了）

矩陣乘法的結合律

1. 設定與目標

考慮數域$K$。假設我們有三個矩陣 $A, B, C$，其維度分別為：

• $A \in M_{m \times n}(K)$
• $B \in M_{n \times p}(K)$
• $C \in M_{p \times q}(K)$

我們的目標是證明 $(AB)C = A(BC)$。為此，我們只需證明兩邊矩陣對應的第 $(i, j)$ 個元（entry）完全相等。

2. 左式展開：$(AB)C$

首先處理左邊的運算。令 $D = AB$，根據矩陣乘法定義，其第 $(i, t)$ 個元為：

$$d_{it} = \sum_{s=1}^{n} a_{is}b_{st} \quad (1 \le i \le m, 1 \le t \le p)$$

接著令 $E = (AB)C = DC$，則 $E$ 的第 $(i, j)$ 個元 $e_{ij}$ 為：

$$e_{ij} = \sum_{t=1}^{p} d_{it}c_{tj}$$

將 $d_{it}$ 的式子代入，利用分配律將 $c_{tj}$ 移入和號內：

$$e_{ij} = \sum_{t=1}^{p} \left( \sum_{s=1}^{n} a_{is}b_{st} \right) c_{tj} = \sum_{t=1}^{p} \sum_{s=1}^{n} a_{is}b_{st}c_{tj}$$

3. 右式展開：$A(BC)$

現在處理右邊。令 $F = BC$，其第 $(s, j)$ 個元為：

$$f_{sj} = \sum_{t=1}^{p} b_{st}c_{tj} \quad (1 \le s \le n, 1 \le j \le q)$$

接著令 $G = A(BC) = AF$，其第 $(i, j)$ 個元 $g_{ij}$ 為：

$$g_{ij} = \sum_{s=1}^{n} a_{is}f_{sj} = \sum_{s=1}^{n} a_{is} \left( \sum_{t=1}^{p} b_{st}c_{tj} \right)$$

同樣利用分配律展開：

$$g_{ij} = \sum_{s=1}^{n} \sum_{t=1}^{p} a_{is}b_{st}c_{tj}$$

4. 結論

觀察 $e_{ij}$ 與 $g_{ij}$ 的最終表達式：

• $e_{ij} = \sum_{t=1}^{p} \sum_{s=1}^{n} a_{is}b_{st}c_{tj}$
• $g_{ij} = \sum_{s=1}^{n} \sum_{t=1}^{p} a_{is}b_{st}c_{tj}$

由於有限項數的加法滿足交換律與結合律，雙重和號的求和順序可以互換。因此，$e_{ij} = g_{ij}$，這代表 $G = E$，即：

$$A(BC) = (AB)C$$

（證明終了）