🌟 進階純數學 1 (9231) 學習筆記 🌟

第 1.7 章：數學歸納法

歡迎來到純數學中最強大且令人滿足的課題之一：數學歸納法 (Proof by Induction)！

別擔心，這初看之下可能有點難，但它其實是一個巧妙的方法，用於證明一個命題對無限多種情況（通常是所有正整數 \(n\)）都成立。你可以把它想像成排列得完美的骨牌陣！

什麼是數學歸納法？（骨牌比喻）

想像你有無限多塊骨牌，編號分別為 \(n=1, n=2, n=3,\dots\) 等。要證明「所有」骨牌都會倒下，你只需要證明兩件事：

  1. 起始推力（基進步驟 / Base Case）： 你推倒了第一塊骨牌（即 \(n=1\) 的情況）。
  2. 連鎖反應（歸納步驟 / Inductive Step）： 你證明了若「任意」一塊骨牌（假設是第 \(k\) 塊）倒下，它必然會推倒下一塊骨牌（即第 \((k+1)\) 塊）。

如果你證實了這兩點，那麼每一塊骨牌，一直到無窮遠處，都一定會倒下！這就是數學歸納法的精髓。

重點總結

數學歸納法讓我們能夠證明一個公式或命題對於所有大於或等於起始值（通常為 1）的整數均成立。

歸納證明的四個必要步驟

每一個成功的歸納證明都必須遵循這四個強制步驟。漏掉任何一個步驟都會導致證明不完整！

步驟 1：基進步驟 (\(n=n_{min}\))

你必須證明命題 \(P(n)\) 對於最小可能的整數 \(n_{min}\) 是成立的。

  • 通常 \(n_{min} = 1\)，但請仔細檢查題目（有時會從 \(n=0\) 或 \(n=2\) 開始）。
  • 將 \(n_{min}\) 代入等式的兩邊（左式 LHS 和右式 RHS），並證明它們相等，或者證明該性質成立。

步驟 2：歸納假設 (Assumption)

假設命題 \(P(n)\) 對於某個任意正整數 \(k\) 是成立的。

  • 清楚寫下你的假設：假設 \(P(k)\) 為真。
  • 例如： 如果要證明 \(\sum_{r=1}^n r = \frac{1}{2}n(n+1)\)，你要寫：
    假設 \(n=k\) 時成立： \(\sum_{r=1}^k r = \frac{1}{2}k(k+1)\)。

步驟 3：歸納步驟（證明 \(n=k+1\) 的情況）

這是證明的核心。你必須證明若 \(P(k)\) 為真（你在步驟 2 的假設），那麼命題 \(P(k+1)\) 也必須為真。

  • 從 \(P(k+1)\) 的表達式開始。
  • 關鍵技巧： 處理 \(P(k+1)\) 的表達式，以便代入你所假設的命題 \(P(k)\)。
  • 透過代數運算，證明所得結果與將 \(n\) 替換為 \((k+1)\) 後的公式 \(P(n)\) 相符。

🚨 常見錯誤警示！ 🚨

切勿直接寫出 \(n=k+1\) 的命題，然後試圖通過反推或假定它成立來進行證明。你「必須」從一邊（通常是 \(P(k+1)\) 的左式）開始，並推導到另一邊（右式）。

步驟 4：結論 (Formal Write-up)

最後一步是將邏輯鏈條正式化。你的回答中必須包含這一段。

  • 說明由於 \(P(n)\) 對於 \(n=n_{min}\) 成立（步驟 1），且由於 \(P(k)\) 的真值隱含了 \(P(k+1)\) 的真值（步驟 3），根據數學歸納法，命題 \(P(n)\) 對所有 \(n \ge n_{min}\) 的整數均成立。
重點總結

將步驟 2（假設）視為你的工具。步驟 3 的目標僅僅是創造一個使用該工具的機會。

將歸納法應用於不同類型的問題

課程要求使用歸納法證明與求和、遞迴關係、可除性、矩陣和導數相關的結果。結構雖然保持不變，但針對每一種類型，步驟 3 需要特定的運算技巧。

1. 涉及級數求和的證明

這是最常見的類型，通常使用標準結果，如 \(\sum r^3\)。

例子：證明 \(\sum_{r=1}^n r^3 = \frac{1}{4}n^2(n+1)^2\)。

  • 假設 (P(k))： \(\sum_{r=1}^k r^3 = \frac{1}{4}k^2(k+1)^2\)。
  • 歸納步驟 (P(k+1))：

    我們從前 \((k+1)\) 項的和開始：
    \( \sum_{r=1}^{k+1} r^3 = \left( \sum_{r=1}^k r^3 \right) + (k+1)^3 \)

    現在，代入假設 \(P(k)\)：
    \( = \frac{1}{4}k^2(k+1)^2 + (k+1)^3 \)

    提取公因式 \((k+1)^2\)：
    \( = (k+1)^2 \left[ \frac{1}{4}k^2 + (k+1) \right] \)

    化簡括號內的部分：
    \( = (k+1)^2 \left[ \frac{k^2 + 4k + 4}{4} \right] = (k+1)^2 \left[ \frac{(k+2)^2}{4} \right] \)

    整理以符合原公式 \(n=(k+1)\) 時的右式：
    \( = \frac{1}{4}(k+1)^2 (k+2)^2 \)

    由於這與 \(P(k+1)\) 相符，步驟完成。

2. 涉及可除性的證明

這類證明需要展示 \(P(k+1)\) 可以寫成 \(P(k)\) 的倍數與另一個可被該數整除的項之和。

例子：證明對於所有正整數 \(n\)，\(3^{2n} + 2 \times 5^n - 3\) 均可被 8 整除。

  • 假設 (P(k))： 假設 \(3^{2k} + 2 \times 5^k - 3 = 8M\)，其中 \(M\) 為整數。
  • 歸納步驟 (P(k+1))： 我們需要檢驗 \(3^{2(k+1)} + 2 \times 5^{k+1} - 3\)。

    利用指數律重寫表達式以提取假設項 \(3^{2k}\)：
    \( P(k+1) = 3^{2k} \times 3^2 + 2 \times 5^k \times 5 - 3 \)
    \( P(k+1) = 9 \times 3^{2k} + 10 \times 5^k - 3 \)

    根據假設，我們知 \(3^{2k} = 8M - 2 \times 5^k + 3\)。將其代入 \(P(k+1)\)：
    \( P(k+1) = 9(8M - 2 \times 5^k + 3) + 10 \times 5^k - 3 \)
    \( P(k+1) = 72M - 18 \times 5^k + 27 + 10 \times 5^k - 3 \)
    \( P(k+1) = 72M - 8 \times 5^k + 24 \)

    從結果中提取 8：
    \( P(k+1) = 8(9M - 5^k + 3) \)

    由於 \(9M - 5^k + 3\) 為整數，因此 \(P(k+1)\) 可被 8 整除。


3. 涉及遞迴關係的證明

遞迴關係根據前項定義數列（例如 \(u_{n+1} = f(u_n)\)）。你需要證明該數列也可以由通項公式 \(u_n\) 定義。

例子：數列由 \(u_1 = 1\) 及 \(u_{n+1} = 3u_n - 1\) 定義。證明 \(u_n = \frac{1}{2}(1 + 3^{n-1})\)。

  • 假設 (P(k))： 假設 \(u_k = \frac{1}{2}(1 + 3^{k-1})\)。
  • 歸納步驟 (P(k+1))：

    使用 \(u_{k+1}\) 的遞迴關係定義：
    \( u_{k+1} = 3u_k - 1 \)

    代入假設 \(u_k\)：
    \( u_{k+1} = 3 \left( \frac{1}{2}(1 + 3^{k-1}) \right) - 1 \)

    化簡：
    \( u_{k+1} = \frac{3}{2} + \frac{3 \times 3^{k-1}}{2} - 1 \)
    \( u_{k+1} = \frac{1}{2} + \frac{3^k}{2} \)
    \( u_{k+1} = \frac{1}{2}(1 + 3^k) \)

    當 \(n\) 替換為 \((k+1)\) 時，這與目標公式 \(\frac{1}{2}(1 + 3^{n-1})\) 一致。（因為 \(3^{(k+1)-1} = 3^k\)）。

4. 涉及矩陣的證明

歸納法通常用於尋找矩陣的 \(n\) 次冪 \(M^n\)。

例子：給定 \(M = \begin{pmatrix} 4 & -1 \\ 6 & 1 \end{pmatrix}\)，證明對於整數 \(n \ge 1\)，\(M^n = \frac{1}{3} \begin{pmatrix} 3 \times 2^n - 2 & 1 - 2^n \\ 3 \times 2^{n+1} - 6 & 3 - 2^{n+1} \end{pmatrix}\)。

  • 假設 (P(k))： 假設該公式對 \(M^k\) 成立。
  • 歸納步驟 (P(k+1))：

    我們使用性質 \(M^{k+1} = M^k M\)。 （注意：你必須將假設的 \(M^k\) 與原始矩陣 \(M\) 相乘）。

    \( M^{k+1} = \frac{1}{3} \begin{pmatrix} 3 \times 2^k - 2 & 1 - 2^k \\ 3 \times 2^{k+1} - 6 & 3 - 2^{k+1} \end{pmatrix} \begin{pmatrix} 4 & -1 \\ 6 & 1 \end{pmatrix} \)

    你必須進行矩陣乘法並化簡四個分量（這通常比較繁瑣，但屬於代數運算）。目標是證明結果等於：
    \( \frac{1}{3} \begin{pmatrix} 3 \times 2^{k+1} - 2 & 1 - 2^{k+1} \\ 3 \times 2^{(k+1)+1} - 6 & 3 - 2^{(k+1)+1} \end{pmatrix} \)

5. 涉及導數（\(n\) 階導數）的證明

此處，\(P(n)\) 是 \(n\) 階導數 \(\frac{d^n y}{dx^n}\) 的表達式。

例子：求並證明 \(y = xe^x\) 的 \(n\) 階導數。

  • 猜想 (歸納前)： 首先，找出模式（參見第 4 節）。
    \( \frac{dy}{dx} = 1e^x + xe^x = (x+1)e^x \) (\(n=1\))
    \( \frac{d^2y}{dx^2} = 1e^x + (x+1)e^x = (x+2)e^x \) (\(n=2\))
    \( \frac{d^3y}{dx^3} = 1e^x + (x+2)e^x = (x+3)e^x \) (\(n=3\))

    猜想為：\( \frac{d^n y}{dx^n} = (x+n)e^x \)。

  • 假設 (P(k))： 假設 \( \frac{d^k y}{dx^k} = (x+k)e^x \)。
  • 歸納步驟 (P(k+1))：

    \((k+1)\) 階導數是 \(k\) 階導數的導數：
    \( \frac{d^{k+1} y}{dx^{k+1}} = \frac{d}{dx} \left[ (x+k)e^x \right] \)

    使用乘積法則，注意 \(k\) 為常數：
    \( = \frac{d}{dx}(x+k) \cdot e^x + (x+k) \cdot \frac{d}{dx}(e^x) \)
    \( = 1 \cdot e^x + (x+k) e^x \)
    \( = e^x (1 + x + k) \)
    \( = (x + (k+1))e^x \)

    這與 \(n=k+1\) 時的公式一致。

識別猜想與試驗策略 (課程 1.7)

有時，考試題目不會預先給出公式（命題 \(P(n)\)）。你需要使用有限試驗來發現模式並形成猜想，然後使用歸納法證明它。

如何形成猜想：

  1. 計算前幾項： 計算出 \(n=1, 2, 3,\) 甚至 \(4\) 的結果。
  2. 尋找模式：
    • 求和： 如果結果是多項式，尋找立方 (\(n^3\))、平方 (\(n^2\)) 或線性 (\(n\)) 的因子。
    • 遞迴： 尋找涉及公共因子冪次的關係（如前例中的 \(3^n\)）。
    • 導數/矩陣： 觀察係數隨 \(n\) 的變化情況。通常變化是線性的 (\(+n\)) 或指數型的 (\(2^n\))。
  3. 寫下猜想： 用 \(n\) 明確寫出公式。這就成為你隨後進行數學歸納法證明時的 \(P(n)\)。

你知道嗎？
計算諸如 \(\sum_{r=1}^n r \times r!\)（簡化後為 \((n+1)! - 1\)）之類的級數和，是生成前幾項結果（猜想）並在應用歸納法證明通項之前必不可少的經典例子。

快速回顧：歸納步驟


1. 基進步驟 (n=1)： 證明左式 = 右式。
2. 假設 P(k)： 為 \(k\) 寫出等式/命題。
3. 證明 P(k+1)： 從 \(P(k+1)\) 開始，利用 \(P(k)\) 進行代換，以達到目標形式。
4. 結論： 正式的邏輯陳述。