Recurrence Relations

歡迎來到遞迴關係的世界！

在本章中，我們將探討遞迴關係 (Recurrence Relations)（有時稱為差分方程 (Difference Equations)）。這些方程本質上是數學上的「規則書」，告訴你如何根據之前的數值來找出數列中的下一個數。這是高等純數學 (Extra Pure) 單元中至關重要的一部分，因為它讓我們能夠對從銀行利息到人口增長，甚至是數位訊號處理等各種事物進行建模！

你知道嗎？著名的費氏數列 (Fibonacci sequence) \(1, 1, 2, 3, 5, 8, ...\) 實際上就是一個遞迴關係！每一項都是前兩項之和：\(u_{n+2} = u_{n+1} + u_n\)。

1. 遞迴關係的語言

在開始解題之前，我們需要掌握它的語言。遞迴關係將項 \(u_n\) 與之前的項（如 \(u_{n-1}\) 或 \(u_{n-2}\)）連結起來。

關鍵術語：
階數 (Order)：指你需要回溯到多遠的項。如果你只需要前一項 (\(u_n\))，這就是一階 (First Order)。如果你需要前兩項 (\(u_n\) 和 \(u_{n-1}\))，這就是二階 (Second Order)。
線性 (Linear)：這意味著各項 (\(u_n, u_{n+1}\) 等) 沒有被平方、立方，也沒有被困在平方根之內。
齊次 (Homogeneous)：如果方程等於零（例如 \(u_{n+1} - 2u_n = 0\)），它就是齊次的。如果存在一個關於 \(n\) 的「剩餘」函數（例如 \(u_{n+1} - 2u_n = 3n + 1\)），它就是非齊次 (Non-Homogeneous)。
初始條件 (Initial Conditions)：這是初始數值，例如 \(u_0 = 5\)。沒有這些條件，我們只能找到「通解 (General Solution)」。有了它們，我們就能找到「特解 (Particular Solution)」。

快速複習框：長期行為類型

當 \(n\) 變得非常大時（記作 \(n \to \infty\)），數列的表現會有所不同：
1. 收斂 (Convergent)：項數穩定在一個單一數值上（即極限 (Limit)）。
2. 發散 (Divergent)：項數永遠變得越來越大（或越來越小）。
3. 週期性 (Periodic)：項數以循環方式重複（例如 \(1, 0, -1, 1, 0, -1, ...\)）。
4. 震盪 (Oscillating)：項數來回跳動，通常振幅會變大或變小。

關鍵收穫：階數告訴你需要多少「初始資訊片段」才能完整解出該數列。

2. 解一階遞迴關係

一階線性關係的形式如下：\(u_{n+1} = a u_n + f(n)\)。

齊次情況 \(u_{n+1} = a u_n\)

這是最簡單的類型。它就像等比數列！如果你每次都乘以 \(a\)，通解就是：
\(u_n = A(a)^n\)
範例：若 \(u_{n+1} = 3u_n\)，則 \(u_n = A(3)^n\)。

非齊次情況 \(u_{n+1} = a u_n + f(n)\)

別擔心，看起來複雜而已！我們分兩部分來解，就像微分方程一樣：
總解 = 互補函數 (Complementary Function, CF) + 特解 (Particular Integral, PI)

第一步：求出 CF。 忽略 \(f(n)\)，將其視為零來求解。這會給你 \(u_n = A(a)^n\)。
第二步：求出 PI。 觀察 \(f(n)\) 並「猜測」一個類似的形式：
- 如果 \(f(n) = \text{常數}\)，猜 \(u_n = \lambda\)。
- 如果 \(f(n) = \text{線性（例如 } 2n+3\text{）}\)，猜 \(u_n = \lambda n + \mu\)。
- 如果 \(f(n) = \text{二次（例如 } n^2\text{）}\)，猜 \(u_n = \lambda n^2 + \mu n + \nu\)。
- 如果 \(f(n) = d k^n\)，猜 \(u_n = \lambda k^n\)。
第三步：結合並求解。 將兩者相加，並利用初始條件（如 \(u_0\)）來求出常數 \(A\)。

常見錯誤：如果你的 PI「猜測」已經存在於 CF 中，你必須將你的猜測乘以 \(n\)。例如，如果你的 CF 是 \(A(2)^n\) 且 \(f(n) = 2^n\)，那麼你的 PI 猜測應該是 \(\lambda n (2^n)\)。

3. 解二階遞迴關係

這些方程的形式為 \(u_{n+2} + a u_{n+1} + b u_n = f(n)\)。這些是本章的「大魔王」題目，但解法非常有邏輯。

第一步：輔助方程 (Auxiliary Equation)

為了求出互補函數 (CF)，我們透過將 \(u_{n+2}\) 替換為 \(m^2\)、\(u_{n+1}\) 替換為 \(m\)、\(u_n\) 替換為 \(1\) 來建立一個二次方程。
對於 \(u_{n+2} + a u_{n+1} + b u_n = 0\)，其輔助方程為：\(m^2 + am + b = 0\)。

第二步：三種根的形式

解出 \(m\) 的二次方程。根的性質決定了 CF：
1. 相異實根 (\(m_1\) 和 \(m_2\))：
\(u_n = A(m_1)^n + B(m_2)^n\)
2. 重根 (\(m_1 = m_2 = m\))：
\(u_n = (A + Bn)m^n\)
3. 複數根 (\(m = p \pm iq\))：
首先，求出模 \(r = \sqrt{p^2 + q^2}\) 和幅角 \(\theta = \arctan(q/p)\)。
CF 為：\(u_n = r^n (A \cos(n\theta) + B \sin(n\theta))\)。

第三步：特解 (PI)

如果方程是非齊次的（不等於零），請使用與一階部分相同的表格來猜測 PI。將你的猜測代入原始方程，以求出希臘字母（\(\lambda, \mu\) 等）的值。

關鍵收穫：務必先求出 CF！在將 CF 和 PI 相加之前，你無法求出常數 \(A\) 和 \(B\)。

4. 驗證與探討

有時考試不會要求你從零開始解題。相反地，它可能會要求你驗證 (verify)一個解或探討 (investigate)一個極限。

驗證（步驟）：
1. 拿給定的 \(u_n\) 解。
2. 利用該公式寫出 \(u_{n+1}\) 和 \(u_{n+2}\) 的樣子。
3. 將這些代入遞迴關係中。
4. 化簡！如果左邊等於右邊，則解已驗證。

探討長期行為：
如果數列有一個極限 (Limit) \(L\)，那麼當 \(n\) 變得非常大時，\(u_n \approx L\) 且 \(u_{n+1} \approx L\)。
要找出極限，將所有 \(u\) 項替換為 \(L\) 並解出 \(L\)。
範例：對於 \(u_{n+1} = 0.5u_n + 3\)，極限為 \(L = 0.5L + 3\)，得出 \(0.5L = 3\)，所以 \(L = 6\)。

總結檢查清單

- 你能辨識階數以及它是否為齊次嗎？
- 你能解二階關係的輔助方程嗎？
- 你記得複數根的模-幅角形式嗎？
- 當 PI 與 CF 重疊時，你知道要將猜測乘以 \(n\) 嗎？
- 你能使用初始條件來求出 \(A\) 和 \(B\) 的特定值嗎？

如果複數根剛開始讓你感到奇怪，別擔心！只要記住它們總是會產生 \(\sin\) 和 \(\cos\) 的規律，這是有道理的，因為阿爾岡圖 (Argand diagram) 上的複數代表了旋轉與震盪。