遞迴關係求解

遞迴關係 (recurrence relation) 用前幾項定義下一項,如 Fibonacci $a_n = a_{n-1} + a_{n-2}$。線性齊次常係數遞迴 $a_n = pa_{n-1} + qa_{n-2}$ 的解法:猜 $a_n = r^n$,得特徵方程 $r^2 - pr - q = 0$。相異根 $r_1, r_2$ 時通解 $a_n = c_1r_1^n + c_2r_2^n$;重根時 $a_n = (c_1 + c_2n)r^n$。常數由初始值決定。

算例:$a_n = 5a_{n-1} - 6a_{n-2}$,$a_0 = 1$、$a_1 = 4$。特徵方程 $(r-2)(r-3) = 0$,$a_n = c_1 2^n + c_2 3^n$;$c_1 + c_2 = 1$、$2c_1 + 3c_2 = 4$ 得 $a_n = 2\cdot3^n - 2^n$。Fibonacci 的根是黃金比例 $\frac{1\pm\sqrt5}{2}$,這就是 Binet 公式的由來。

一階 $a_n = ra_{n-1} + d$ 用固定點化成等比。遞迴與微分方程的解法完全平行(特徵根 ↔ 特徵方程),對角化是它的矩陣版本;演算法複雜度(主定理)、分期付款、人口模型都是遞迴。