歡迎來到 Decision Mathematics 2 的遞推關係（Recurrence Relations）
歡迎來到進階數學（Further Mathematics，8FM0）中最實用且極具成就感的課題之一！你有沒有想過銀行是如何按年計算複利的？生態學家是如何建立動物種群模型的？或者電腦演算法是如何一步一步解決益智難題的？所有這些過程背後都有一個共同的數學核心骨幹：遞推關係（Recurrence Relations，或稱遞迴關係）。
即使你以往覺得代數很抽象複雜，也完全不用擔心。我們會將每一種解題技巧拆解成清晰易懂、按部就班的步驟。學完這一章後，你將能夠將現實生活中的情境轉化為數學方程、求解得出精確通項公式，並運用數學歸納法（Mathematical Induction）來嚴格證明你的解。
---1. 核心定義與基礎概念
在開始解方程之前，我們先來釐清 Decision Mathematics 2 中貫穿始終的核心術語。
什麼是遞推關係（Recurrence Relation）？
遞推關係（有時稱為差分方程，Difference Equation）是一個利用序列中前一項或多項（例如 \(u_{n-1}\) 或 \(u_n\)）以及指標 \(n\) 來定義每一項（\(u_n\) 或 \(x_n\)）的公式。
閉式解 / 顯式公式（Closed-Form / Explicit Formula）：
閉式解能讓你直接根據 \(n\) 和初始常數計算出 \(u_n\) 的數值，而不需要逐一算出之前的所有各項。例如，若 \(u_n = 2^n + 3\)，你可以直接計算出 \(u_{100}\)，而不需要先算出 \(u_1, u_2, \dots, u_{99}\)。
遞推關係的階數（Order of a Recurrence Relation）：
階數（Order）是關係式中出現的序列項中，最高下標與最低下標之間的差。
• \(u_{n+1} = 3u_n + 5\) 是一階（First order），因為下標之差為 \((n+1) - n = 1\)。
• \(u_{n+2} + 4u_{n+1} - 5u_n = 0\) 是二階（Second order），因為 \((n+2) - n = 2\)。
註：在 AS Level（8FM0）中，你需要掌握的求解技巧重點在一階遞推關係！
線性與非線性（Linear vs. Non-Linear）：
如果每個序列項都只以一次方的形式出現，且沒有任何序列項相乘，則該遞推關係為線性（Linear）。例如，\(u_{n+1} = 2u_n + n\) 是線性的，而 \(u_{n+1} = (u_n)^2\) 或 \(u_{n+1} = u_n \cdot u_{n-1}\) 則是非線性的。
齊次與非齊次（Homogeneous vs. Non-Homogeneous）：
• 如果每一項都包含序列變量，則該關係為齊次（Homogeneous）：\(u_{n+1} - a u_n = 0\)。
• 如果關係中包含獨立的 \(n\) 函數或獨立常數，則為非齊次（Non-homogeneous）：\(u_{n+1} - a u_n = f(n)\)。
邊界條件 / 初始條件（Boundary / Initial Conditions）：
這些是題目給定已知的起始數值，例如 \(u_0 = 100\) 或 \(u_1 = 4\)，讓我們能夠求出通解中未知常數的精確數值。
2. 建立現實情境中的遞推關係模型
在 AS 考試中，題目經常會要求你根據文字描述來建立遞推關係。我們來看三個經典範例：
情境 A：儲蓄與利息計算
例子： 某人開立儲蓄戶口並存入 \(£1000\)。每年戶口結餘均可賺取 \(5\%\) 利息，而在每年年終，他會額外存入 \(£200\)。
• 設 \(u_n\) 為 \(n\) 年後戶口內的金額。
• 第 \(n+1\) 年的結餘來自第 \(n\) 年的結餘加上 \(5\%\) 利息，再加上 \(£200\)：
\(u_{n+1} = 1.05 u_n + 200\)，且初始條件為 \(u_0 = 1000\)。
情境 B：包含捕撈的種群模型
例子： 一個養魚場一開始有 \(5000\) 條魚。魚群數量每年自然倍增為原本的 \(1.2\) 倍，但每年年終會捕撈 \(800\) 條魚。
• 設 \(u_n\) 為 \(n\) 年後的魚群數量。
• 遞推關係：\(u_{n+1} = 1.2 u_n - 800\)，且 \(u_0 = 5000\)。
情境 C：河內塔問題（Tower of Hanoi）
你知道嗎？ 著名的河內塔難題探討按照特定規則將 \(n\) 個圓盤從一根柱子移動到另一根柱子所需的最少移動次數 \(M_n\)。
• 要移動 \(n+1\) 個圓盤，你必須先將上方 \(n\) 個圓盤移至輔助柱（需要 \(M_n\) 次移動），將最底部最大的圓盤移至目標柱（\(1\) 次移動），然後再把那 \(n\) 個圓盤移到它上面（又需要 \(M_n\) 次移動）。
• 遞推關係：\(M_{n+1} = 2M_n + 1\)，且初始條件為 \(M_1 = 1\)。
建立模型的核心要點： 仔細分析步驟 \(n\) 到步驟 \(n+1\) 之間發生了什麼變化，確認初始狀態是從 \(n=0\) 還是 \(n=1\) 開始，並清晰寫出初始值。
---3. 求解一階線性遞推關係
要找出線性非齊次關係式 \(u_{n+1} - a u_n = f(n)\) 的閉式解公式，我們採用結構化的三步法：
通解（General Solution） = 餘函數（Complementary Function） + 特解（Particular Solution）
\(u_n = u_n^{(c)} + u_n^{(p)}\)
步驟 1：求餘函數（Complementary Function, CF），\(u_n^{(c)}\)
餘函數是將右式設為零後的齊次方程的解：
\(u_{n+1} - a u_n = 0\)
建立輔助方程（Auxiliary Equation）：\(m - a = 0 \implies m = a\)。
因此，餘函數的形式恆為：
\(u_n^{(c)} = A(a)^n\)
（其中 \(A\) 為任意常數）。
步驟 2：求特解（Particular Solution, PS），\(u_n^{(p)}\)
特解是用來處理非齊次項 \(f(n)\) 的。我們會根據 \(f(n)\) 的函數形式作出合理的試探假設（Trial guess），將其代入原遞推關係中，並求解未知的待定係數。
常見試探形式對照表：
• 常數（Constant）： 若 \(f(n) = k\)，試設 \(u_n^{(p)} = \lambda\)
特殊失效情況： 若 \(a = 1\)（即 \(u_{n+1} - u_n = k\)），試設 \(u_n^{(p)} = \lambda n\)。
• 一次線性（Linear）： 若 \(f(n) = pn + q\)，試設 \(u_n^{(p)} = \lambda n + \mu\)
特殊失效情況： 若 \(a = 1\)，需乘上 \(n\)：試設 \(u_n^{(p)} = n(\lambda n + \mu) = \lambda n^2 + \mu n\)。
• 二次多項式（Quadratic）： 若 \(f(n) = pn^2 + qn + r\)，試設 \(u_n^{(p)} = \lambda n^2 + \mu n + \nu\)
特殊失效情況： 若 \(a = 1\)，將整個試探式乘上 \(n\)。
• 指數 / 幾何形式（Exponential / Geometric）： 若 \(f(n) = k(b)^n\)，試設 \(u_n^{(p)} = \lambda (b)^n\)
特殊失效情況： 若 \(b = a\)（底數與 CF 底數相同），試設 \(u_n^{(p)} = \lambda n (a)^n\)。
步驟 3：求任意常數 \(A\)
寫出完整的通解：\(u_n = A(a)^n + u_n^{(p)}\)。
將給定的初始條件（例如 \(u_0\) 或 \(u_1\)）代入這個完整公式中，求解常數 \(A\)。
範例解說：求解一階遞推關係
題目： 求遞推關係 \(u_{n+1} = 3u_n + 4n\) 的閉式解，已知 \(u_0 = 5\)。
解題步驟：
第一部分：餘函數（CF）
考慮齊次方程：\(u_{n+1} - 3u_n = 0\)。
輔助根：\(m = 3\)。
因此，\(u_n^{(c)} = A(3)^n\)。
第二部分：特解（PS）
在此題中，\(f(n) = 4n\)（一次多項式），且 \(a = 3 \neq 1\)。
試設 \(u_n^{(p)} = \lambda n + \mu\)。
則 \(u_{n+1}^{(p)} = \lambda (n + 1) + \mu = \lambda n + \lambda + \mu\)。
將各項代入 \(u_{n+1} - 3u_n = 4n\)：
\((\lambda n + \lambda + \mu) - 3(\lambda n + \mu) = 4n\)
\(-2\lambda n + (\lambda - 2\mu) = 4n + 0\)
比較 \(n\) 的係數及常數項：
• 針對 \(n\) 的係數：\(-2\lambda = 4 \implies \lambda = -2\)
• 針對常數項：\(\lambda - 2\mu = 0 \implies -2 - 2\mu = 0 \implies \mu = -1\)
因此，特解為 \(u_n^{(p)} = -2n - 1\)。
第三部分：通解與邊界條件
結合 CF 與 PS 得到通解：
\(u_n = A(3)^n - 2n - 1\)
現在代入初始條件 \(u_0 = 5\)：
\(5 = A(3)^0 - 2(0) - 1\)
\(5 = A(1) - 1 \implies A = 6\)
最終閉式解公式：
\(u_n = 6(3)^n - 2n - 1\)
4. 以數學歸納法證明閉式解
Pearson Edexcel 考試要求同學必須掌握利用數學歸納法（Mathematical Induction）來證明閉式公式滿足特定的遞推關係。嚴格遵循以下四步法，確保穩拿滿分：
步驟 1：奠基步驟（Base Case）
驗證公式在最小給定值 \(n\) 時成立（通常是 \(n = 0\) 或 \(n = 1\)）。證明公式算出的值與題目給定的初始條件完全一致（即 \(\text{LHS} = \text{RHS}\)）。
步驟 2：歸納假設（Inductive Hypothesis）
清晰寫出：「假設當 \(n = k\) 時公式成立，即 \(u_k = g(k)\)。」
步驟 3：歸納步驟（Inductive Step）
利用原遞推關係計算 \(u_{k+1}\)。代入對 \(u_k\) 的歸納假設，並運用代數運算證明其結果符合 \(g(k+1)\) 的形式。
步驟 4：正式結論（Formal Conclusion）
完整寫出標準的結論句。切勿省略，因為考官評分標準中這句話佔有獨立的溝通分數（Communication Mark）！
範例解說：數學歸納法證明
題目： 某數列定義為 \(u_{n+1} = 2u_n + 1\)，且 \(u_1 = 3\)。試用數學歸納法證明對於所有正整數 \(n \ge 1\)，都有 \(u_n = 2^{n+1} - 1\)。
證明：
1. 奠基步驟（Base Case）： 當 \(n = 1\) 時：
根據公式：\(u_1 = 2^{1+1} - 1 = 2^2 - 1 = 3\)。
這與給定的初始條件 \(u_1 = 3\) 相符。因此，當 \(n = 1\) 時命題成立。
2. 歸納假設（Inductive Hypothesis）：
假設當 \(n = k\) 時命題成立，即 \(u_k = 2^{k+1} - 1\)。
3. 歸納步驟（Inductive Step）：
利用遞推關係，當 \(n = k + 1\) 時：
\(u_{k+1} = 2u_k + 1\)
代入我們對 \(u_k\) 的歸納假設：
\(u_{k+1} = 2(2^{k+1} - 1) + 1\)
\(u_{k+1} = 2 \cdot 2^{k+1} - 2 + 1\)
\(u_{k+1} = 2^{(k+1)+1} - 1\)
這正是將 \(n = k + 1\) 代入公式後所需的目標形式。
4. 結論（Conclusion）：
「若該命題在 \(n = k\) 時成立，則在 \(n = k + 1\) 時亦成立。由於當 \(n = 1\) 時命題成立，根據數學歸納法，該命題對所有整數 \(n \ge 1\) 均成立。」
5. 常見易錯盲點與考官警告
考官在 Decision Mathematics 2 評卷報告中經常指出一些本可避免的失分陷阱，請務必留意：
• 過早代入常數： 絕對不要只在餘函數（CF）中就直接用 \(u_0\) 來求 \(A\)！你必須在寫出完整的通解 \(u_n = u_n^{(c)} + u_n^{(p)}\) 之後，才代入 \(n=0\) 求 \(A\)。
• 下標平移時漏掉括號： 當為線性試探式 \(\lambda n + \mu\) 求 \(u_{n+1}^{(p)}\) 時，切記 \(n\) 必須替換為 \((n+1)\)。即 \(\lambda(n+1) + \mu = \lambda n + \lambda + \mu\)。如果寫成 \(\lambda n + \mu + 1\)，將會直接導致運算錯誤。
• 忽略 \(a = 1\) 時的失效情況： 如果你嘗試用常數試探式 \(u_n^{(p)} = \lambda\) 去解 \(u_{n+1} - u_n = 5\)，代入後會得到 \(\lambda - \lambda = 0 \neq 5\)。你必須意識到當 \(a=1\) 時，必須將試探式乘以 \(n\)，即設 \(u_n^{(p)} = \lambda n\)。
• 歸納法結論不完整： 漏寫結論句，或者忘記同時提及奠基步驟與歸納推導（\(n=k \implies n=k+1\)），都會讓你失掉最後的溝通分數。
• 混淆起始下標： 審題時務必看清楚題目給予的初始條件是 \(u_0\) 還是 \(u_1\)。
---6. 本章摘要與快速複習
• 遞推關係（Recurrence Relation）： 以之前的各項（如 \(u_n\)）來表示 \(u_{n+1}\)。
• 階數（Order）： 最高下標減去最低下標之差。
• 餘函數（CF）： 齊次方程 \(u_{n+1} - au_n = 0\) 的解，形式為 \(u_n^{(c)} = A(a)^n\)。
• 特解（PS）： 與 \(f(n)\) 形式相對應的試探解；若與 CF 衝突則需乘上 \(n\)。
• 通解（General Solution）： \(u_n = u_n^{(c)} + u_n^{(p)} = A(a)^n + u_n^{(p)}\)。
• 邊界條件（Boundary Values）： 在最後一步代入完整通解以求出 \(A\)。
• 數學歸納法（Induction）： 證明奠基步驟 \(\rightarrow\) 假設 \(n=k\) 時成立 \(\rightarrow\) 利用遞推關係證明 \(n=k+1\) 時亦成立 \(\rightarrow\) 寫出完整正式結論。