Recurrence Relations

Brutal force method

• 暴力解開，所有式子相加後左右消掉整理得之。

線性齊次（Linear Homogeneous）

Example:

$F(n)=n, \;n=0,1$ $F(n)=F(n-1)+6F(n-2), \;n >=2$

Solution:

Step 1: 令 $a_n=F(n)$，得遞迴關係式 $a_n-a_{n-1}-6a_{n-2}=0$，特徵方程式為 $r^2-r-6=0$，得根為 $r=3,-2$，通解為 $a_n=c_1 \times3^n+c_2 \times(-2)^n$

Step 2: $a_0=0,a_1=1$代入通解方程式 $a_n=c_1 \times3^n+c_2 \times(-2)^n$ 可得 $c_1=\frac{1}{5}, c_2= -\frac{1}{5}$。

Step 3: 故 $F(n)= \frac{1}{5}(3^n-(-2)^n)$

齊次重根

假設 $T(n)$ 特徵方程如下：$(r-3)^4(r-4)^2$，則可以推得：

$T(n)=(c_1n^3+c_2n^2+c_3n^1+c_4n^0)\times3^n+(c_5n^1+c_6n^0)\times4^n$

線性非齊次（Linear Nonhomogeneous）

$a_n=d_1a_{n-1}+d_2a_{n-2}+...+d_ka_{n-k}+F(n), \;n>=k$

1. 求齊次解(含未定係數)(先不看 $F(n)$ 求之)
2. 求特解
3. 特解代入原式，求出特解的未定係數。
4. 全解 = 齊次解 + 特解
5. 代入初始條件，求出齊次解的未定係數。

如何假設非齊次特徵方程？

1. 先看 $F(n)$ 最高到幾次方，之後你的 $a_{np}$ 就要令到那：
   • ex: 到 $n^2$，則你的 $a_{np} = d_0 + d_1n + d_2n^2$
2. 在來就要看你的特徵根，如果有 $1$ 的根就得再多令下去：
   • 特徵方程式是 $b^2-2b+1=0$，解得 $b=1, 1$
   • 所以要在多令兩個，變成 $a_{np} = d_0 + d_1n +d_2n^2+d_3n^3+d_4n^4$

References

• 黃子嘉現代離散研究室
• 常係數線性遞迴關係式 (下)
• 線性遞迴關係之求解(下)，張福春
• 遞迴關係，黎靖