從遞迴式轉一般式的奧秘
在計算機科學和數學中，遞迴式（Recurrence Relation）是一種用來定義序列或函數的表達方式，其中某項的值由其先前的一項或多項的值決定。例如，斐波那契數列的定義 $F(n) = F(n-1) + F(n-2)$ 就是一個典型的遞迴式。
雖然遞迴式在描述問題時非常直觀且優雅，但在實際應用中，直接計算遞迴式中的第 n 項可能效率低下，因為需要重複計算許多相同的子問題。這時，我們就需要將遞迴式轉換成一個「一般式」（Closed-form Expression）。一般式可以直接計算出序列或函數的第 n 項，而無需進行任何遞迴計算，從而大大提高效率。
本文將詳細探討 **怎麼從遞迴式轉一般式**，並提供多種常見的轉換方法，輔以具體範例，幫助讀者深入理解這個過程。
一、 理解遞迴式的類型
在開始轉換之前，我們需要對遞迴式進行分類，不同的類型有不同的處理方法：
1. 常係數線性遞迴式 (Linear Homogeneous Recurrence Relations with Constant Coefficients)
這類遞迴式的形式為：$a_n = c_1 a_{n-1} + c_2 a_{n-2} + dots + c_k a_{n-k}$，其中 $c_1, c_2, dots, c_k$ 是常數。例如：$a_n = 2a_{n-1} + 3a_{n-2}$。
2. 非常係數線性遞迴式 (Linear Non-homogeneous Recurrence Relations with Constant Coefficients)
這類遞迴式在常係數線性遞迴式的基礎上，增加了一個與 $n$ 相關的函數 $f(n)$：$a_n = c_1 a_{n-1} + c_2 a_{n-2} + dots + c_k a_{n-k} + f(n)$。例如：$a_n = 2a_{n-1} + n$。
3. 非線性遞迴式 (Non-linear Recurrence Relations)
這類遞迴式的形式不符合線性結構，例如：$a_n = a_{n-1}^2 + 1$。
本文將主要 focus 在前兩種最常見的類型，因為它們有成熟的數學方法可以推導。
二、 常係數線性遞迴式的轉換方法
這類遞迴式的轉換核心是利用「特徵方程」（Characteristic Equation）來求解。
1. 步驟一：建立特徵方程
對於遞迴式 $a_n = c_1 a_{n-1} + c_2 a_{n-2} + dots + c_k a_{n-k}$，其對應的特徵方程為：
$$r^k - c_1 r^{k-1} - c_2 r^{k-2} - dots - c_k = 0$$2. 步驟二：求解特徵方程的根
計算上述特徵方程的根 $r_1, r_2, dots, r_k$。根的性質（實數、重根、複數根）將決定一般式的形式。
3. 步驟三：根據根的性質構造一般式
- 情況一：所有根均為不相等的實數 ($r_1, r_2, dots, r_k$ 互不相同)
- 情況二：存在重根 (例如，根 $r_1$ 重複 $m$ 次)
- 情況三：存在複數根
一般式形式為：$a_n = A_1 r_1^n + A_2 r_2^n + dots + A_k r_k^n$。
其中 $A_1, A_2, dots, A_k$ 是待定係數，需要利用初始條件（如 $a_0, a_1, dots$）來求解。
如果根 $r$ 是 $m$ 重根，則一般式中對應的部分為：$(A_1 + A_2 n + A_3 n^2 + dots + A_m n^{m-1}) r^n$。
如果特徵方程有複數根，它們總是成對出現（共軛複數）。可以將複數根轉換為三角函數的形式，或者直接使用複數係數，但通常更推薦轉換為三角函數形式，以便於理解。
4. 步驟四：利用初始條件求解待定係數
將構造好的一般式代入已知的初始條件，形成一個關於待定係數的線性方程組，解出係數。例如，若有 $k$ 個初始條件 $a_0, a_1, dots, a_{k-1}$，則可得到 $k$ 個方程來求解 $A_1, dots, A_k$。
範例：斐波那契數列
斐波那契數列：$F(n) = F(n-1) + F(n-2)$，初始條件 $F(0)=0, F(1)=1$。
- 建立特徵方程： $r^2 - r - 1 = 0$
- 求解特徵方程的根： 使用求根公式 $r = frac{-b pm sqrt{b^2 - 4ac}}{2a}$，得 $r_1 = frac{1 + sqrt{5}}{2}$ (黃金分割率 $phi$)， $r_2 = frac{1 - sqrt{5}}{2}$ ( $1-phi$)。
- 構造一般式： 由於是兩個不相等的實數根，一般式為 $F(n) = A_1 (frac{1 + sqrt{5}}{2})^n + A_2 (frac{1 - sqrt{5}}{2})^n$。
- 利用初始條件求解待定係數：
- 當 $n=0$: $F(0) = A_1 + A_2 = 0 implies A_2 = -A_1$
- 當 $n=1$: $F(1) = A_1 (frac{1 + sqrt{5}}{2}) + A_2 (frac{1 - sqrt{5}}{2}) = 1$
最終，斐波那契數列的一般式為：$F(n) = frac{1}{sqrt{5}} (frac{1 + sqrt{5}}{2})^n - frac{1}{sqrt{5}} (frac{1 - sqrt{5}}{2})^n$。
三、 非常係數線性遞迴式的轉換方法
對於非常係數線性遞迴式 $a_n = c_1 a_{n-1} + dots + c_k a_{n-k} + f(n)$，其一般式由兩部分組成：
$a_n = a_n^{(h)} + a_n^{(p)}$
- $a_n^{(h)}$ 是齊次方程 $a_n = c_1 a_{n-1} + dots + c_k a_{n-k}$ 的通解，即我們上面講過的常係數線性遞迴式的解。
- $a_n^{(p)}$ 是非齊次方程的特解，其形式與 $f(n)$ 的形式有關。
1. 確定齊次解 $a_n^{(h)}$
按照常係數線性遞迴式的步驟，求解特徵方程，得到齊次解。
2. 確定特解 $a_n^{(p)}$ 的形式
根據 $f(n)$ 的形式，猜測特解的形式。以下是一些常見情況：
- 如果 $f(n)$ 是多項式：
- 若 $f(n)$ 是 $d$ 次多項式，且 $1$ 不是特徵方程的根，則特解形式為一個 $d$ 次多項式。
- 若 $f(n)$ 是 $d$ 次多項式，且 $1$ 是特徵方程的 $m$ 重根，則特解形式為 $n^m$ 乘以一個 $d$ 次多項式。
- 如果 $f(n)$ 是指數形式 $C cdot s^n$：
- 若 $s$ 不是特徵方程的根，則特解形式為 $A cdot s^n$。
- 若 $s$ 是特徵方程的 $m$ 重根，則特解形式為 $A cdot n^m cdot s^n$。
- 如果 $f(n)$ 是三角函數形式 (如 $sin(an)$ 或 $cos(an)$)：
- 如果 $f(n)$ 是上述形式的組合：
這可以看作是複指數形式 $C cdot (e^{ia})^n$ 的實部或虛部。如果 $e^{ia}$ (或 $e^{-ia}$) 不是特徵方程的根，則特解形式為 $A cos(an) + B sin(an)$。如果 $e^{ia}$ (或 $e^{-ia}$) 是特徵方程的 $m$ 重根，則特解形式為 $n^m (A cos(an) + B sin(an))$。
根據疊加原理，可以分別求出各部分對應的特解，然後相加得到總的特解。
3. 求解特解的待定係數
將猜測的特解形式代入原非齊次遞迴式，解出特解的待定係數。
4. 組合齊次解和特解，並用初始條件確定最終係數
$a_n = a_n^{(h)} + a_n^{(p)}$。利用初始條件，解出 $a_n^{(h)}$ 中的待定係數，從而得到最終的一般式。
範例：求解 $a_n = 2a_{n-1} + 1$，初始條件 $a_0=0$
- 確定齊次解： 齊次方程為 $a_n = 2a_{n-1}$。特徵方程為 $r - 2 = 0$，根為 $r=2$。所以齊次解為 $a_n^{(h)} = A cdot 2^n$。
- 確定特解的形式： $f(n) = 1$，這是一個 $0$ 次多項式。因為 $1$ 不是特徵方程的根（特徵根為 $2$），所以特解形式為常數 $B$。令 $a_n^{(p)} = B$。
- 求解特解的待定係數： 將 $a_n^{(p)} = B$ 代入原遞迴式 $a_n = 2a_{n-1} + 1$： $B = 2B + 1$ $-B = 1 implies B = -1$。 所以特解為 $a_n^{(p)} = -1$。
- 組合齊次解和特解： $a_n = a_n^{(h)} + a_n^{(p)} = A cdot 2^n - 1$。
- 用初始條件確定最終係數： 已知 $a_0 = 0$。 $a_0 = A cdot 2^0 - 1 = 0$ $A - 1 = 0 implies A = 1$。
最終，一般式為 $a_n = 1 cdot 2^n - 1 = 2^n - 1$。
四、 其他轉換方法（簡介）
1. 數學歸納法
對於某些較簡單的遞迴式，如果我們已經猜測出一般式的形式，可以使用數學歸納法來證明該一般式是正確的。
2. 替換法 (Substitution)
有時通過變換變量或進行一些巧妙的代數變換，可以將一個複雜的遞迴式轉化為一個較簡單的遞迴式，甚至可以轉化為常係數線性遞迴式。
3. 生成函數法 (Generating Functions)
生成函數法是一種強大的工具，可以用來處理各種類型的遞迴式，尤其是那些無法直接應用特徵方程法的遞迴式。該方法將遞迴式轉換為一個關於形式冪級數的方程，然後通過求解該方程來得到遞迴式的閉合形式。
生成函數法的基本思想是：假設一個序列 $a_0, a_1, a_2, dots$ 的生成函數為 $A(x) = a_0 + a_1 x + a_2 x^2 + dots$。通過將遞迴式兩邊乘以 $x^n$ 並對所有可能的 $n$ 求和，可以得到一個關於 $A(x)$ 的方程。解出 $A(x)$ 後，再通過求 $A(x)$ 的泰勒級數展開，就可以得到序列的閉合形式。
4. 矩陣法 (Matrix Method)
對於線性遞迴式，特別是那些依賴於多個前項的遞迴式，可以將其表示為矩陣形式。例如，斐波那契數列的遞迴關係可以表示為：
$$egin{pmatrix} F(n) \ F(n-1) end{pmatrix} = egin{pmatrix} 1 & 1 \ 1 & 0 end{pmatrix} egin{pmatrix} F(n-1) \ F(n-2) end{pmatrix}$$通過計算矩陣的 $n$ 次方，可以快速得到 $F(n)$ 的值。這種方法對於計算大量項時特別有用，並且可以結合快速冪演算法來進一步提高效率。
常見問題 (FAQ)
如何判斷一個遞迴式是否為常係數線性遞迴式？
判斷一個遞迴式是否為常係數線性遞迴式，主要看兩個方面：
1. **線性 (Linearity)：** 遞迴式中的每一項 $a_i$ 都必須是 $a$ 的一次方，並且沒有 $a_i cdot a_j$ 這樣的乘積項。
2. **常係數 (Constant Coefficients)：** 遞迴式中的係數 $c_i$ 必須是常數，不能是關於 $n$ 的函數。例如，$a_n = n cdot a_{n-1}$ 就不是常係數線性遞迴式。
如果同時滿足這兩個條件，並且遞迴式的形式為 $a_n = c_1 a_{n-1} + c_2 a_{n-2} + dots + c_k a_{n-k}$，那麼它就是一個常係數線性遞迴式。
為什麼要將遞迴式轉成一般式？
將遞迴式轉成一般式的最主要原因是為了**提高計算效率**。直接計算遞迴式中的第 $n$ 項，可能需要進行大量的重複計算，其時間複雜度可能是指數級的。而一般式可以直接通過一個公式計算出第 $n$ 項，其計算複雜度通常為多項式級別，甚至常數級別，這在處理大型問題時顯得尤為重要。
此外，一般式也更便於我們對序列的性質進行分析，例如趨勢、漸近行為等。
當特徵方程的根是複數時，如何處理？
當常係數線性遞迴式的特徵方程出現複數根時，它們通常是以共軛複數對的形式出現，例如 $a + bi$ 和 $a - bi$。我們可以將這些複數根轉換為極座標形式，並利用歐拉公式 $e^{i heta} = cos( heta) + isin( heta)$ 將其轉換為三角函數形式。例如，如果特徵方程的根是 $r = ho (cos heta + i sin heta)$ 和 $ar{r} = ho (cos heta - i sin heta)$，那麼對應於這兩個根的通解部分可以寫成 $ ho^n (A cos(n heta) + B sin(n heta))$。其中 $A$ 和 $B$ 是待定係數，通過初始條件求解。
生成函數法適用於哪些類型的遞迴式？
生成函數法是一種非常通用的方法，適用於幾乎所有類型的線性遞迴式，包括常係數和非常係數的，以及一些非線性的遞迴式（通過變換）。它特別擅長處理那些難以通過特徵方程法解決的問題，或者當我們需要同時考慮多個遞迴式組成的系統時。儘管生成函數法需要一些代數技巧，但它提供了一種系統性的解決方案。
如何快速判斷 $f(n)$ 的形式對應哪種特解形式？
在求解非常係數線性遞迴式時，判斷特解形式的關鍵在於 $f(n)$ 的結構以及特徵方程的根。一般而言，如果 $f(n)$ 是多項式，特解也是多項式；如果 $f(n)$ 是指數形式 $C cdot s^n$，特解也包含 $s^n$；如果是三角函數，則類似於複指數。最需要注意的情況是，當 $f(n)$ 的形式（或其部分）恰好與特徵方程的根的冪次形式相同時，需要在猜測的特解形式上乘以 $n^m$，其中 $m$ 是該根在特徵方程中的重數。掌握這些基本規則，能夠大大簡化求解過程。
