遞推關係簡介 (Introduction to Recurrence Relations)

歡迎來到決策數學 2 (Decision Mathematics 2) 中最實用且優雅的課題之一！在日常生活中，許多事物都是隨著離散的時間間隔逐步變化的。試想像一下你的儲蓄戶口每年賺取利息、自然保護區內的動物數量在每個繁殖季節後的增長，或是演算法進行重複運算的過程。遞推關係（recurrence relation，常稱為差分方程 difference equation）其實就是一個利用數列中前面的一項或多項，來表示後續各項的方程。

雖然項與項之間的關係法則（term-to-term rule）能告訴你如何由一步推展到下一步，但如果你想求取 \(100\) 年後的數值，卻要先算出中間每一年，那確實會相當繁瑣。在這一章中，你將學會如何「解」這些遞推關係，從而找出閉合形式（closed form，即以 \(n\) 表示第 \(n\) 項 \(u_n\) 的通項公式）。剛開始接觸時千萬不要被它嚇倒；我們會把整個方法拆解成清晰易懂、逐步推進的步驟！

1. 理解遞推關係 (Understanding Recurrence Relations)

甚麼是一階線性遞推關係？

在決策數學 2 的課程範圍內，重點集中在一階線性遞推關係（first-order linear recurrence relations）：

• 一階（First-order）： 每一項 \(u_{n+1}\) 僅取決於緊接在前的一項 \(u_n\)。
• 線性（Linear）： 項 \(u_{n+1}\) 和 \(u_n\) 的次數僅為 \(1\) 次；它們不會互相相乘、平方，亦不會出現在 \(\sin\) 或 \(\sqrt{\phantom{x}}\) 等函數之內。

常系數一階線性遞推關係的一般形式為：

\(u_{n+1} - a u_n = g(n)\)    （或寫成 \(u_{n+1} = a u_n + g(n)\)）

其中 \(a\) 為常數，而 \(g(n)\) 則是給定的 \(n\) 函數（可以是常數、包含 \(n\) 的多項式或指數項）。

齊次與非齊次 (Homogeneous vs Non-Homogeneous)

我們主要將這類關係分為兩大類：

1. 齊次（Homogeneous）： 當 \(g(n) = 0\) 時。方程可簡化為：
\(u_{n+1} - a u_n = 0\)   \(\implies\)   \(u_{n+1} = a u_n\)
比喻： 可以將其視為純粹的複利增長，期間沒有任何額外的資金注入或提取。

2. 非齊次（Non-Homogeneous）： 當 \(g(n) \neq 0\) 時。方程包含額外的「輸入項」或「外力項」：
\(u_{n+1} - a u_n = g(n)\)
比喻： 可以視為一項每年賺取利息的投資，但同時你每年還會定期存入一筆固定金額。

重點提示： 一階的意思是僅往回看一步。若等號右方為零，則為齊次；若右方包含額外的 \(n\) 函數，則為非齊次。

2. 解一階線性齊次遞推關係 (Solving First-Order Linear Homogeneous Recurrence Relations)

補函數與輔助方程 (The Complementary Function and Auxiliary Equation)

我們先探討齊次方程：

\(u_{n+1} - a u_n = 0\)

若 \(u_{n+1} = a u_n\)，代表每一項都是前一項乘以 \(a\)。這本質上就是一個等比數列（geometric sequence）！其解稱為補函數（complementary function，記作 \(u_c\)）。

為了按照考評局要求的規範方法求解，我們會寫出輔助方程（auxiliary equation）。我們嘗試代入形式為 \(u_n = m^n\) 的試探解：

\(m^{n+1} - a m^n = 0\)

兩邊同時除以 \(m^n\)，便得出輔助方程：

\(m - a = 0 \implies m = a\)

因此，通解（即補函數）為：

\(u_n = A(a)^n\)

其中 \(A\) 為任意常數，需由初始條件（例如起始值 \(u_0\) 或 \(u_1\)）決定。

逐步示範：齊次關係

題目： 給定 \(u_0 = 5\)，解遞推關係 \(u_{n+1} - 3u_n = 0\)。

第一步：寫出輔助方程。
將 \(u_{n+1}\) 換成 \(m\)，將 \(u_n\) 換成 \(1\)：
\(m - 3 = 0 \implies m = 3\)

第二步：寫出通解。
\(u_n = A(3)^n\)

第三步：應用初始條件求 \(A\)。
當 \(n = 0\) 時，\(u_0 = 5\)：
\(5 = A(3)^0 \implies A = 5\)

最終答案：
\(u_n = 5(3)^n\)

重點提示： 對於任何形式為 \(u_{n+1} - a u_n = 0\) 的關係，輔助方程均為 \(m - a = 0\)，可直接得出 \(u_n = A(a)^n\)。

3. 解非齊次遞推關係 (Solving Non-Homogeneous Recurrence Relations)

完整解的結構

求解非齊次遞推關係 \(u_{n+1} - a u_n = g(n)\) 時，完整的通解（general solution）必然由兩部分相加而成：

\(u_n = \text{補函數 (CF)} + \text{特解 (PS)}\)

\(u_n = u_c + u_p\)

• 補函數（\(u_c\)）： 對應齊次方程 \(u_{n+1} - a u_n = 0\) 的解。這部分必定包含任意常數 \(A\)。
• 特解（\(u_p\)）： 滿足完整方程 \(u_{n+1} - a u_n = g(n)\) 的任何一個特定數列。它不含任何任意常數。

求特解（\(u_p\)）

為了找出特解，我們會根據 \(g(n)\) 的數學形式作出合理的「猜測」（即試探解 trial solution），將其代入遞推關係中，然後比較系數求出未知的常數。

以下是必須熟記的常見試探解對照表：

• 若 \(g(n) = k\)（常數）：
嘗試設 \(u_p = C\)（常數）。
特殊情況： 若 \(a = 1\)（此時齊次解本身已是常數 \(A(1)^n = A\)），設常數將無法求出解。此時須乘以 \(n\)，嘗試設 \(u_p = C n\)。

• 若 \(g(n) = p n + q\)（\(n\) 的一次多項式）：
嘗試設 \(u_p = C n + D\)。
特殊情況： 若 \(a = 1\)，嘗試設 \(u_p = n(C n + D) = C n^2 + D n\)。

• 若 \(g(n) = k \lambda^n\)（指數形式）：
嘗試設 \(u_p = C \lambda^n\)。
特殊情況： 若 \(\lambda = a\)（底數與輔助方程的根相同），嘗試設 \(u_p = C n \lambda^n\)。

至關重要的原則：何時計算任意常數

考試重要警告： 切勿在加上特解之前就利用初始條件去求常數 \(A\)！你必須先建立完整的通解 \(u_n = u_c + u_p\)，然後才可以代入 \(n = 0\)（或 \(n = 1\)）來計算 \(A\)。

範例一：右方為常數

題目： 求遞推關係 \(u_{n+1} - 2u_n = 6\) 的通解，並求出當 \(u_0 = 10\) 時的特解。

第一步：求補函數（\(u_c\)）。
將右方設為零：\(u_{n+1} - 2u_n = 0\)。
輔助方程：\(m - 2 = 0 \implies m = 2\)。
因此，\(u_c = A(2)^n\)。

第二步：求特解（\(u_p\)）。
右方為常數 \(6\)。我們嘗試設常數解：\(u_n = C\)。
若 \(u_n = C\)，則 \(u_{n+1} = C\)。
代入遞推關係中：
\(C - 2C = 6\)
\(-C = 6 \implies C = -6\)
因此，\(u_p = -6\)。

第三步：寫出通解。
\(u_n = u_c + u_p\)
\(u_n = A(2)^n - 6\)

第四步：利用初始條件求 \(A\)。
已知 \(u_0 = 10\)：
\(10 = A(2)^0 - 6\)
\(10 = A(1) - 6 \implies A = 16\)

最終答案：
\(u_n = 16(2)^n - 6\)

快速驗算： 當 \(n = 0\) 時，\(u_0 = 16(1) - 6 = 10\)。由原遞推關係可得 \(u_1 = 2(10) + 6 = 26\)。代入求得的公式：\(u_1 = 16(2)^1 - 6 = 32 - 6 = 26\)。結果完全吻合！

範例二：右方為一次式

題目： 給定 \(u_0 = 2\)，解遞推關係 \(u_{n+1} - 3u_n = 4n\)。

第一步：求補函數（\(u_c\)）。
輔助方程：\(m - 3 = 0 \implies m = 3\)。
\(u_c = A(3)^n\)。

第二步：求特解（\(u_p\)）。
由於 \(g(n) = 4n\) 為一次式，我們嘗試設 \(u_n = C n + D\)。
則下一項為 \(u_{n+1} = C(n+1) + D = C n + C + D\)。
將兩者代入 \(u_{n+1} - 3u_n = 4n\)：
\((C n + C + D) - 3(C n + D) = 4n\)
展開並整理同類項：
\(-2C n + (C - 2D) = 4n\)

比較 \(n\) 的系數與常數項：
• 比較 \(n\) 的系數：\(-2C = 4 \implies C = -2\)
• 比較常數項：\(C - 2D = 0 \implies -2 - 2D = 0 \implies 2D = -2 \implies D = -1\)
因此，\(u_p = -2n - 1\)。

第三步：寫出通解。
\(u_n = A(3)^n - 2n - 1\)

第四步：求常數 \(A\)。
代入 \(n = 0\) 及 \(u_0 = 2\)：
\(2 = A(3)^0 - 2(0) - 1\)
\(2 = A - 1 \implies A = 3\)

最終答案：
\(u_n = 3(3)^n - 2n - 1\)  （亦可化簡為 \(u_n = 3^{n+1} - 2n - 1\)）。

重點提示： 非齊次方程的解題步驟清晰分為兩部分：先利用輔助方程求出 \(u_c\)，再透過比較系數求出 \(u_p\)。記住必須先結合成 \(u_n = u_c + u_p\)，才可以代入條件求 \(A\)。

4. 遞推關係的應用建模 (Modelling with Recurrence Relations)

將實際情境轉化為遞推關係

決策數學 2 的核心考核能力之一，就是將文字敘述的情境轉化為遞推關係、求解方程，並在實際情境中合理解讀其意義。

閱讀題目時，請特別留意以下常見字眼：

• 百分比增長／減少： 若某數量每年增加 \(r\%\)，則每個新數值等於前一年的數值乘以 \((1 + \frac{r}{100})\)。例如，增長 \(4\%\) 代表乘以 \(1.04\)。
• 固定增加或扣除： 像「固定費用 \(50\)」、「捕撈 \(300\) 條魚」或「每年補充放養 \(120\) 隻動物」等字眼，代表 \(g(n)\) 中的常數部分。若使總量增加則相加，若減少則相減。
• 初始狀態： 起始數量代表 \(u_0\)（在時間 \(0\)）或有時代表 \(u_1\)（在第 \(1\) 年結束後）。請務必仔細閱讀題目對時間 \(n\) 的定義。

綜合建模範例：種群增長

情境： 一個野生動物信託基金負責管理森林內的鹿群。設 \(x_n\) 為第 \(n\) 年年初的鹿群數量。
在第 \(0\) 年年初，共有 \(800\) 隻鹿。
在每一年內，由於自然繁殖，鹿群數量會增加 \(10\%\)。此外，在每年年底，護林員會將固定的 \(50\) 隻鹿遷往其他公園，以防止過度繁衍。

(a) 建立以 \(x_n\) 表示 \(x_{n+1}\) 的遞推關係。
(b) 解此遞推關係，求以 \(n\) 表示 \(x_n\) 的表達式。
(c) 計算第 \(5\) 年年初的鹿群數量。
(d) 描述鹿群數量在長遠而言的變化趨勢。

解答：

(a) 部分：建立關係式
自然增長 \(10\%\) 對應的倍數為 \(1 + 0.10 = 1.1\)。
每年年底遷走鹿隻會使數量減少 \(50\)。
因此：
\(x_{n+1} = 1.1 x_n - 50\)，初始條件為 \(x_0 = 800\)。
整理成標準形式：
\(x_{n+1} - 1.1 x_n = -50\)

(b) 部分：求解遞推關係
補函數（\(x_c\)）：
輔助方程：\(m - 1.1 = 0 \implies m = 1.1\)。
\(x_c = A(1.1)^n\)

特解（\(x_p\)）：
等號右方為常數（\(-50\)），故設 \(x_n = C\)：
\(C - 1.1 C = -50\)
\(-0.1 C = -50 \implies C = \frac{-50}{-0.1} = 500\)
因此，\(x_p = 500\)。

通解：
\(x_n = A(1.1)^n + 500\)

應用初始條件（\(x_0 = 800\)）：
\(800 = A(1.1)^0 + 500\)
\(800 = A + 500 \implies A = 300\)

因此，閉合形式的解為：
\(x_n = 300(1.1)^n + 500\)

(c) 部分：計算第 \(5\) 年的數量
代入 \(n = 5\)：
\(x_5 = 300(1.1)^5 + 500\)
\(x_5 = 300(1.61051) + 500 = 483.153 + 500 = 983.153\)
由於動物數量必須為整數，取最接近的整數得：\(983\) 隻鹿。

(d) 部分：長遠趨勢
隨著 \(n\) 增加，\(1.1^n\) 會無限增長（因為 \(1.1 > 1\)）。因此，項 \(300(1.1)^n\) 會趨向無限大。
長遠而言，鹿群數量將會無止境地持續增長。

重點提示： 建模題目通常遵循三個標準步驟：(1) 將文字敘述轉化為 \(u_{n+1} - a u_n = g(n)\)，(2) 透過「補函數 + 特解」配合邊界條件求解，(3) 代入數值或分析 \(n \to \infty\) 時的極限，從而在現實背景下得出結論。

5. 常見錯誤與避忌 (Common Mistakes and How to Avoid Them)

1. 過早計算 \(A\)：
這是考生在試卷中最常犯的錯誤！不少同學寫出 \(u_c = A(a)^n\) 後，就立刻代入 \(u_0\) 來求 \(A\)，最後才把特解加進去。這樣做必然會得出錯誤答案。請切記：務必先寫出完整通解 \(u_n = u_c + u_p\)，然後才代入初始值。

2. 下標混淆（\(n\) 與 \(n+1\)）：
當把一次式的試探解 \(u_n = C n + D\) 代入方程時，謹記 \(u_{n+1} = C(n+1) + D = C n + C + D\)。如果忘了把 \(C\) 分配乘進 \(+1\) 的項中，常數項的計算便會全盤出錯。

3. 「底數重疊」陷阱：
若你要解 \(u_{n+1} - 2u_n = 3(2)^n\)，嘗試設 \(u_p = C(2)^n\) 會導致 \(C(2)^{n+1} - 2C(2)^n = 2C(2)^n - 2C(2)^n = 0\)，使 \(C\) 被完全消去！因為 \(2^n\) 本身已經是補函數的一部分，遇到這種情況，你必須嘗試設 \(u_p = C n (2)^n\)。

4. 沒有驗算答案：
考試時你可以使用計算機。你隨時可以用原有的遞推關係逐步手算推出 \(n = 1\) 和 \(n = 2\) 的值，然後再代入你找出的通項公式驗算。如果兩者相符，你就可以對自己的答案有 \(100\%\) 的信心！

溫習清單 (Summary Checklist)

• 標準形式： 將關係式整理成 \(u_{n+1} - a u_n = g(n)\)。
• 補函數： 解輔助方程 \(m - a = 0 \implies m = a\)，得出 \(u_c = A(a)^n\)。
• 特解： 根據 \(g(n)\) 選擇適當的試探形式，代入方程並比較系數以求出未知參數。
• 通解： 組合出 \(u_n = u_c + u_p\)。
• 求常數： 將給定的邊界條件（如 \(u_0\)）代入完整的通解中求出 \(A\)。
• 合理解讀： 在應用情境題目中，計算具體數值或探討隨 \(n\) 增加時的長遠變化趨勢。