遞迴關係求解器

遞迴關係求解器

遞迴關係求解器透過求解特徵方程，計算任何常係數線性齊次遞迴關係的閉式解。它能將根繪製在複平面上，並生成數列的前 N 項。您可以透過有序係數列表或自然數學運算式（如 a(n) = 3·a(n−1) − 2·a(n−2)）輸入遞迴式。本工具可自動處理相異實根、重根和共軛複數根對。

什麼是線性遞迴關係？

k 階常係數線性齊次遞迴關係具有以下形式：

其中 c₁, c₂, …, c_k 是固定的實數，k 是階數。配合 k 個初始值 a(0), a(1), …, a(k−1)，該遞迴式能唯一確定序列的每一項。經典例子包括：

• 費波那契 (Fibonacci)： a(n) = a(n−1) + a(n−2)，初始值 0, 1 → 0, 1, 1, 2, 3, 5, 8, 13, …
• 盧卡斯 (Lucas)： a(n) = a(n−1) + a(n−2)，初始值 2, 1 → 2, 1, 3, 4, 7, 11, 18, 29, …
• 佩爾數 (Pell numbers)： a(n) = 2·a(n−1) + a(n−2)，初始值 0, 1 → 0, 1, 2, 5, 12, 29, 70, …
• 泰波那契 (Tribonacci)： a(n) = a(n−1) + a(n−2) + a(n−3)，初始值 0, 0, 1 → 0, 0, 1, 1, 2, 4, 7, 13, 24, …

特徵方程法

為了找到 a(n) 的閉式公式，我們尋找形式為 a(n) = rⁿ 的解。代入遞迴式並除以 r^n−k 可得：

這就是特徵方程 — 一個 r 的 k 次多項式。根據代數基本定理，它恰好有 k 個複數根（計入重數）。遞迴的通解取決於這些根的結構：

情況 1：相異實根 r₁, …, r_k

常數 A₁, …, A_k 透過代入 n = 0, 1, …, k−1 並根據初始值求解線性方程組來確定。

情況 2：重數為 m 的根 r

每個重複根貢獻 m 個線性無關的基底序列：rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ。

情況 3：共軛複數根 r = ρ·e^iθ, r̄ = ρ·e^−iθ

當遞迴式具有實係數時，複數根總是成對出現。每一對根會組合成一個實數震盪項，其幾何包絡線為 ρⁿ，頻率為 θ。

主根決定的增長分類

令 ρ = max|r_i| 為根的最大絕對值（譜半徑）。a(n) 的長期行為受以下規則支配：

費波那契 — 解題範例

考慮費波那契遞迴 a(n) = a(n−1) + a(n−2)，初始值 a(0) = 0 且 a(1) = 1。

1. 特徵方程： r² − r − 1 = 0
2. 求根（二次公式）： r = (1 ± √5) / 2，即 φ ≈ 1.6180 與 ψ ≈ −0.6180
3. 通解形式： a(n) = A·φⁿ + B·ψⁿ
4. 套用初始條件： A + B = 0 且 A·φ + B·ψ = 1，解得 A = 1/√5, B = −1/√5
5. 比內 (Binet) 公式： a(n) = (φⁿ − ψⁿ) / √5

由於 |ψ| < 1，第二項隨著 n → ∞ 會趨近於 0，因此 a(n) 約等於 φⁿ / √5 — 這就是為什麼費波那契數大約以每步 φ 倍的速度增長。

如何使用此求解器

1. 選擇輸入模式： 「引導式」可讓您選擇階數並輸入以逗號分隔的係數；「自由格式運算式」接受完整的遞迴式，如 a(n) = a(n-1) + 6*a(n-2) - 8*a(n-3)。
2. 輸入係數或運算式。 支援小數 (0.5) 與分數 (1/2)。
3. 提供初始值。 您必須提供恰好 k 個符合階數的值：a(0), a(1), …, a(k−1)。
4. 選擇顯示項數 (最高 60)。
5. 點擊求解。結果頁面將顯示特徵方程、複平面上的根位置、閉式公式以及序列的動畫條形圖。

支援範圍與限制

• 階數： 1 到 6（階數 ≥ 3 時，特徵多項式透過 Durand–Kerner 迭代數值求解）。
• 實常數係數： 不支援複係數；係數 c_i 必須為實數。
• 僅限齊次式： 此工具僅求解齊次遞迴（無強制項，如 + n 或 + 2ⁿ）。對於非齊次遞迴，請在此處求解齊次部分，再另外加上特解。
• 數值精度： 結果以 IEEE-754 雙精度計算；對於病態遞迴（根的大小範圍跨度極大），驗證橫幅將標註閉式解與迭代值之間的任何偏差。

應用領域

• 演算法分析： 分治演算法的執行時間通常符合線性遞迴（主定理）。
• 組合數學： 計算序列 — 卡特蘭數、錯排、鋪磚問題 — 常由遞迴式給出。
• 訊號處理： 帶有回饋的離散時間 LTI 系統即為線性遞迴；其穩定性取決於根的位置（位於單位圓內 ⇔ 穩定）。
• 人口動態與金融： 複利計算、年齡結構人口模型、自迴歸 AR(p) 時間序列。
• 物理學： 一維晶格模型、緊束縛哈密頓量 (Tight-binding Hamiltonians) 以及轉移矩陣法。

常見問題解答

什麼是常係數線性遞迴關係？

常係數線性遞迴關係是形式如 a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k) 的方程，其中 c₁, c₂, …, c_k 是固定的實數，k 是階數。序列中的每一項都是前 k 項的線性組合。常見例子包括費波那契遞迴 a(n) = a(n−1) + a(n−2) 以及具有不同初始值的盧卡斯遞迴。

遞迴的特徵方程是什麼？

給定遞迴 a(n) = c₁·a(n−1) + c₂·a(n−2) + … + c_k·a(n−k)，其特徵方程為 r^k − c₁·r^k−1 − c₂·r^k−2 − … − c_k = 0。這個多項式方程恰好有 k 個複數根（計入重數），遞迴的每個解都是形式為 n^j·rⁿ 序列的線性組合，其中 r 是根，j 的範圍直到其重數減 1。

如何獲得 a(n) 的閉式公式？

求解特徵方程以找到其根 r₁, r₂, …, r_k。如果所有根皆相異，閉式解為 a(n) = A₁·r₁ⁿ + A₂·r₂ⁿ + … + A_k·r_kⁿ，其中常數 A_i 透過代入初始值並求解線性方程組來確定。如果根 r 的重數為 m，它會貢獻 m 個基底項：rⁿ, n·rⁿ, n²·rⁿ, …, n^m−1·rⁿ。此計算機自動執行整個程序。

複數根對序列意味著什麼？

當遞迴具有實係數時，複數根總是成對出現 r = ρ·e^iθ 和 r̄ = ρ·e^−iθ。這類根會產生震盪行為：閉式解包含 2·ρⁿ·[α·cos(nθ) − β·sin(nθ)] 項。如果 ρ 等於 1，序列以恆定振幅震盪；如果 ρ 小於 1，震盪會衰減；如果 ρ 大於 1，振幅呈幾何級數增長。

為什麼主根能告訴我序列如何增長？

當 n 變得很大時，具有最大 |r| 的項會支配其他所有項，因為其絕對值增長最快。因此，如果 ρ = max|r_i|，那麼 |a(n)| 漸近地與 ρⁿ 成正比（如果主根是重根，則會多一個多項式因子）。求解器根據此原理將您的序列分類：ρ < 1 時收斂至零，ρ = 1 時有界，ρ > 1 時呈幾何增長。

這個工具能求解費波那契數列嗎？

可以。輸入遞迴式 a(n) = a(n−1) + a(n−2) 與初始值 0, 1。計算機將推導出特徵方程 r² − r − 1 = 0，根為 φ = (1 + √5)/2 和 ψ = (1 − √5)/2，並返回比內公式 a(n) = (φⁿ − ψⁿ) / √5。點擊輸入表單上方的費波那契快速示例可查看完整解題過程。

此工具是否支援非齊次遞迴，例如 a(n) = a(n−1) + n？

不支援 — 本工具僅求解齊次遞迴（無強制項）。對於非齊次遞迴，請將通解分解為齊次部分（可在此求解）加上一個符合強制項的特解。常見的特解假設 (Ansatz) 包括：與多項式強制項同次數的多項式、與指數強制項對應的 C·rⁿ，或是與三角強制項對應的 A·cos(nθ) + B·sin(nθ)。

延伸閱讀

• 遞迴關係 — 維基百科
• 常係數線性遞迴 — 維基百科
• 特徵方程 — 維基百科
• 費波那契數列 — 維基百科
• Durand–Kerner 方法 — 維基百科

其他相關工具:

數列工具:

• 算術序列計算機 高精度
• 立方列表
• 前n個質數
• 幾何序列計算機
• 斐波納契數列表
• 質數列表
• 平方數列表
• 考拉茲猜想計算機
• 快樂數計算機
• 魔方陣產生器
• 卡特蘭數生成器
• 西格瑪求和計算機 新
• 乘積符號計算機 (Pi 記號) 新
• 帕斯卡三角形產生器 新
• 孿生質數查找器 新
• 分拆函數計算機 新
• 遞迴關係求解器 新