4. 常係數線性遞迴關係(linear recurrence relation with constant coefficients)

本節將針對 $k$ 階常係數線性遞迴關係 (定義 2.5) $$ C_0a_n + C_1a_{n-1} + \cdots + C_ka_{n-k} = f(n), \quad n \ge k $$ 分別對齊次及常見非齊次個別介紹其求解方法。

4.1. 齊次常係數線性遞迴關係 (homogeneous linear recurrence relation with constant coefficients)

首先考慮齊次的求解, 即 $f(n)=0$, 將具有型式 $a_n=A\alpha^n$ 代入得 $$ C_0 A\alpha^n + C_1 A\alpha^{n-1} + \cdots + C_k A\alpha^{n-k} = 0 $$ 因此得到 $$ A\alpha^{n-k} (C_0\alpha^k + C_1\alpha^{k-1} + \cdots + C_k) = 0 $$ 我們稱 $C_0\alpha^k+C_1\alpha^{k-1}+\cdots+C_k=0$ 為該遞迴關係式的特徵方程式 (characteristic equation), 且稱 $\alpha$ 為特徵根 (characteristic root)。 由代數基本定理知, 最多具有 $k$ 個相異特徵根, 討論其特徵根 $\alpha$, 有參種不同的情形, 以下分別討論之:

I: 相異根 $\alpha$ 具有 $k$ 個相異根 $\alpha_1, \alpha_2, \ldots, \alpha_k$, 則 $a_n=c_1\alpha_1^n+c_2\alpha_2^n+\cdots+c_k\alpha_k^n$ 為此遞迴關係式的解, 其中 $c_i$ 為常數, $1\leq i\leq k$, 證明如下面定理。

定理 4.1: (齊次相異根) 在定義 2.5 的齊次遞迴關係式中, 假設 $\alpha_i$ 為其特徵根, $i=1, 2, \ldots, k$, 則 $$ a_n = c_1 \alpha_1^n + c_2 \alpha_2^n + \cdots + c_k \alpha_k^n $$ 為此遞迴關係式的解, 其中 $c_1, c_2, \ldots, c_k$ 為常數。

證明: 因為 $\alpha_i$ 為其特徵根, $i=1, 2, \ldots, k$, 代入原方程式得 $C_0\alpha_i^k+C_1\alpha_i^{k-1}+\cdots+C_k=0$, $i=1, 2, \ldots, k$。 將等式兩邊同乘上 $c_i\alpha_i^{n-k}$, 則 $c_i\alpha_i^{n-k}(C_0\alpha_i^k+C_1\alpha_i^{k-1}+\cdots+C_k)=0$, $i=1, 2, \ldots, k$, 再將 $c_i\alpha_i^{n-k}$ 乘進去, 即 $C_0(c_i\alpha_i^n)+C_1(c_i\alpha_i^{n-1})+\cdots +C_k(c_i\alpha_i^{n-k})=0$, $i=1, 2, \ldots, k$。 將 $i=1, 2, \ldots, k$ 代入並加總起來 且同係數的項合併整理, 可得 $C_0(c_1\alpha_1^n+\cdots+c_k\alpha_k^n)+C_1(c_1\alpha_1^{n-1}+\cdots+c_k\alpha_k^{n-1}) +\cdots+C_k(c_1\alpha_1^{n-k}+\cdots+c_k\alpha_k^{n-k})=0$, 即 $C_0(c_1\alpha_1^n)+C_1(c_1\alpha_1^{n-1}) +\cdots+C_k(c_1\alpha_1^{n-k})+C_0(c_2\alpha_2^n)+C_1(c_2\alpha_2^{n-1})+\cdots+ C_k(c_2\alpha_2^{n-k}) +\cdots +C_0(c_k\alpha_k^n)+C_1(c_k\alpha_k^{n-1})+\cdots+C_k(c_k\alpha_k^{n-k})=0$, 所以 $c_1\alpha_1^n+c_2\alpha_2^n+\cdots+c_k\alpha_k^n$ 為齊次遞迴關係式的解。$\Box$

例 4.1: 設 $a_n+a_{n-1}-6a_{n-2}=0$, $n\geq 2$, $a_0=1$, $a_1=2$, 求 $a_n$ 的一般解。

解: 特徵方程式為 $\alpha^2+\alpha-6=0$, 其解為兩相異根 $\alpha=2, -3$, 因此可假設 $a_n=c_12^n+c_2(-3)^n$。代入邊界條件得 $$ \left \{ \begin{array}{ll} a_0 = c_1 + c_2=1 \\ a_1 = 2c_1 - 3c_2 = 2 \end{array} \right. $$ 其解為 $c_1=1$, $c_2=0$, 所以 $a_n=2^n$, $n\geq 0$。$\Box$

例 4.2: (賭徒問題) $A$ 和 $B$ 玩一個遊戲, 在每一階段 $A$ 贏 $B$ 的機率為 $p$, $B$ 贏 $A$ 的機率為 $q$, 其中 $p$, $q$ 為正實數, 且滿足 $p+q=1$。 假設不會有平手的情況發生, 且遊戲一開始 $A$ 有 $a$ 塊錢, $B$ 有 $b$ 塊錢, 且 $a+b=N$, 此遊戲在其中一人得到 $M$ 塊錢即停止, 這裡 $M$ 滿足 $\min(M, N-M)\le\min(a, b)$, $\max(M, N-M)\ge \max(a,b)$。

1. 求此遞迴關係式及其邊界條件。
2. 當 $p\neq q$ 時, 求 $A$ 贏的機率。

解:

1. 設 $u_k$ 為當 $A$ 在 $k$ 塊錢贏得此比賽的機率, 而 $A$ 會贏得此場比賽的情況有下列兩種: 在下一步 $A$ 贏一塊錢且 $A$ 即贏得比賽, 或是下一步 $A$ 輸一塊錢且 $A$ 贏得比賽。 第一種情況的機率為 $pu_{k+1}$, 第二種情況的機率為 $qu_{k-1}$, 所以 $u_k=pu_{k+1}+qu_{k-1}$。

   決定邊界條件, 因為當 $A$ 有 $M$ 塊錢時, 他贏的機率為 1, 即 $u_M=1$, 如果 $A$ 輸了此場比賽, 即 $B$ 得到 $M$ 塊錢, 此時 $A$ 有 $N-M$ 塊錢, 即 $A$ 贏的機率為零, $u_{N-M}=0$。

2. 其特徵多項式為 $pr^2-r+q=0$, 所以 $r=\frac{1\pm\sqrt{1-4pq}}{2p}=\frac{1\pm\sqrt{1-4p+4p^2}}{2p} =\frac{1\pm(1-2p)}{2p}=1, q/p$, 所以 $u_k=c_1+c_2(q/p)^k$, 因為 $u_M=1$, 即 $1=c_1+c_2(q/p)^M$, 又知 $u_{N-M}=0$, 故 $0=c_1+c_2(q/p)^{N-M}$。 兩聯立方程式可求得 $c_1=\frac{-(q/p)^{N-M}}{(q/p)^M-(q/p)^{N-M}}$, $c_2=\frac{1}{(q/p)^M-(q/p)^{N-M}}$, 所以 $u_k=\frac{(q/p)^k-(q/p)^{N-M}}{(q/p)^M-(q/p)^{N-M}}$。 因為 $A$ 一開始有 $a$ 塊錢, 所以 $A$ 贏的機率為 $u_a=\frac{(q/p)^a-(q/p)^{N-M}}{(q/p)^M-(q/p)^{N-M}}$。$\Box$

II: 重根 $\alpha$ 具有 $t$ 個相異根 $\alpha_1, \alpha_2, \ldots, \alpha_t$, 其中 $\alpha_i$ 具有重根數 $m_i$, $i=1, 2, \ldots, t$, 則相對於 $\alpha_i$ 部分的解為 $u_i(n)=(c_{i_0}+c_{i_1}n+\cdots+c_{i_{m_i-1}}n^{m_i-1}) \alpha_i^n$, $i=1, 2, \ldots, t$, 且 $$ a_n = u_1(n) + u_2(n) + \cdots + u_t(n) $$ 其中 $c_{i_0}, c_{i_1}, \ldots, c_{i_{m_i-1}}$ 為常數, $i=1, 2, \ldots, t$, 證明如下面定理。

定理 4.2: (齊次重根) 在定義 2.5 的齊次遞迴關係式中, 假設 $\alpha_i$ 為其相異特徵根, $i=1, 2, \ldots, t$, 其中 $\alpha_i$ 具有重根數 $m_i$, $1\leq i\leq t$, 且 $u_i(n)=(c_{i_0}+c_{i_1}n+\cdots+c_{i_{m_i-1}} n^{m_i-1})\alpha_i^n$, $i=1, 2, \ldots, t$, 則 $a_n=u_1(n)+u_2(n)+\cdots+u_t(n)$ 為此遞迴關係式的解。

證明: 對於所有的 $i=1, 2, \ldots, t$, 首先證明 $u_i(n)$ 為此齊次遞迴關係式的解, 類似定理 4.1 的證明可得 $c_{i_0}\alpha_i^n$ 為此齊次遞迴關係式的解。 若 $\alpha_i$ 的重根數 $m_i=1$, 則 $u_i(n)=c_{i_0}\alpha_i^n$ 為此齊次遞迴關係式的解。

若 $\alpha_i$ 的重根數 $m_i\gt 1$, 欲證明 $c_{i_1}n\alpha_i^n$ 亦為此齊次遞迴關係式的解。 因為 $\alpha_i$ 為其特徵根, 所以 $\alpha_i$ 滿足特徵方程式 $C_0\alpha^k+C_1\alpha^{k-1}+\cdots+C_k=0$, 等式兩邊同乘 $\alpha^{n-k}$, 因此 $\alpha_i$ 滿足方程式 \begin{equation} \label{eqnB:22140} %(4.1) C_0 \alpha^n + C_1\alpha^{n-1} + \cdots + C_k\alpha^{n-k} = 0 \end{equation} 因為 $\alpha_i$ 為方程式 (\ref{eqnB:22140}) 的 $m_i$ 重根, 所以 $\alpha_i$ 滿足 (\ref{eqnB:22140}) 式的微分, 即滿足方程式 $$ C_0n\alpha^{n-1} + C_1(n-1)\alpha^{n-2} + \cdots + C_k(n-k)\alpha^{n-k-1} = 0 $$ 將 $\alpha_i$ 代入得 $C_0n\alpha_i^{n-1}+C_1(n-1)\alpha_i^{n-2}+\cdots+C_k(n-k)\alpha_i^{n-k-1}=0$, 等式左右同乘上 $c_{i_1}\alpha_i$ 整理可得 $C_0[c_{i_1}n\alpha_i^n]+C_1[c_{i_1}(n-1)\alpha_i^{n-1}] +\cdots+C_k[c_{i_1}(n-k)\alpha_i^{n-k}]=0$, 將 $i=1, 2, \ldots, t$ 代入加總起來, 可得 $C_0[c_{1_1}n\alpha_1^n]+C_1[c_{1_1}(n-1)\alpha_1^{n-1}]+\cdots+C_k[c_{1_1}(n-k)\alpha_1^{n-k}] +C_0[c_{2_1}n\alpha_2^n] \\ +C_1[c_{2_1}(n-1)\alpha_2^{n-1}]+\cdots+C_k[c_{2_1}(n-k)\alpha_2^{n-k}]+\cdots \\ +C_0[c_{t_1}n\alpha_t^n]+C_1[c_{t_1}(n-1)\alpha_t^{n-1}]+\cdots+C_k[c_{t_1}(n-k)\alpha_t^{n-k}]=0$, 所以 $c_{i_1}n\alpha_i^n$ 為此齊次遞迴關係式的解。 同理, 因為 $\alpha_i$ 滿足 (\ref{eqnB:22140}) 式的 2次微分, 3次微分, $\cdots$, $(m_i-1)$次微分, 可證得 $$ c_{i_2}n^2\alpha_i^n, c_{i_3}n^3\alpha_i^n, \ldots, c_{i_{m_i-1}}n^{m_i-1}\alpha_i^n $$ 皆為此齊次遞迴關係式的解。 類似定理 4.1 可證明 $u_i(n)=c_{i_0}\alpha_i^n+c_{i_1}n\alpha_i^n+\cdots+c_{i_{m_i-1}}$ $\times n^{m_i-1}\alpha_i^n$ 為此齊次遞迴關係式的解, 即 $C_0u_i(n)+C_1u_i(n-1)+\cdots+C_ku_i(n-k)=0$, $i=1, 2, \ldots, t$。 將所有 $i$ 加總可得 $C_0(\sum^t_{i=1}u_i(n))+C_1(\sum^t_{i=1}u_i(n-1))+\cdots+C_k(\sum^t_{i=1}u_i(n-k)) \\ =\sum^t_{i=1}(C_0u_i(n)+C_1u_i(n-1)+\cdots+C_ku_i(n-k))=0$, 所以 $\sum^t_{i=1}u_i(n)=u_1(n)+u_2(n)+\cdots+u_t(n)$ 為此齊次遞迴關係的解。$\Box$

例 4.3: 設 $a_n-7a_{n-1}+16a_{n-2}-12a_{n-3}=0$, $n\geq 3$, $a_0=0$, $a_1=3$, $a_2=13$, 求 $a_n$ 的解。

解: 特徵方程式為 $\alpha^3-7\alpha^2+16\alpha-12=0$, 因式分解後 $(\alpha-2)^2(\alpha-3)=0$, 所以 $\alpha=2, 2, 3$, 將 $a_n=(c_1+c_2n)2^n+c_33^n$ 代入邊界條件 $(n=0, 1, 2)$, 可得 $$ \left \{ \begin{array}{ll} a_0 = c_1 + c_3 = 0 \\ a_1 = 2(c_1+c_2) + 3c_3 = 3 \\ a_2 = 4(c_1+2c_2) + 9c_3 = 13 \end{array} \right. $$ 由聯立方程式解出 $c_1=-1$, $c_2=1$, $c_3=1$, 所以 $a_n=(-1+n)2^n+3^n$, $n\geq 0$。$\Box$

例 4.4: 同例題 4.2 當 $p=q=1/2$ 時, 求 $A$ 贏的機率。

解: 當 $p=q=\frac{1}{2}$ 時, $pr^2-r+q=0$ 即為 $\frac{1}{2}r^2-r+\frac{1}{2}=0$, 所以 $r^2-2r+1=0$, $r=1, 1$ 為重根, 則 $u_k=c_3+c_4k$。 代入邊界條件 $u_M=1$, $u_{N-M}=0$, 得 $c_3+c_4M=1$, $c_3+c_4(N-M)=0$, 解出 $c_3=\frac{M-N}{2M-N}$, $c_4=\frac{1}{2M-N}$, 所以 $u_k=\frac{M-N+k}{2M-N}$。 因為 $A$ 一開始有$a$塊錢, 所以 $A$ 贏的機率為 $u_a=\frac{M-N+a}{2M-N}$。$\Box$

III: 齊次共軛複根 當出現有一組共軛複根 $\alpha_1=\delta+i\omega$, $\alpha_2=\delta-i\omega$, $\delta$, $\omega\in R$, 其中 $\omega\neq0$, 事實上它只是相異根的一個特例, 令 $\rho=\sqrt{\delta^2+\omega^2}$, $\theta=\tan^{-1}\frac{\omega}{\delta}$, 如圖 4 所示。

定理 4.3: (齊次共軛複根) 在定義 2.5 的齊次遞迴關係式中, 假設出現有一組共軛根 $\alpha_1=\delta+i\omega$, $\alpha_2=\delta-i\omega$, 其中 $\omega\neq0$, 事實上它只是相異根的一個特例, 令 $\rho=\sqrt{\delta^2+\omega^2}$, $\theta=\tan^{-1}\frac{\omega}{\delta}$, 則 $a_n=B_1\rho^n\cos n\theta+B_2\rho^n\sin n\theta$ 為此遞迴關係式的解, 其中 $B_1=c_1+c_2$, $B_2=i(c_1-c_2)$ 為常數。

證明: 相對於該組根的解為 \begin{eqnarray*} c_1(\alpha_1)^n+c_2(\alpha_2)^n &=& c_1(\delta+i\omega)^n + c_2(\delta-i\omega)^n \\ &=& c_1 (\rho e^{i\theta})^n + c_2 (\rho e^{-i\theta})^n \\ &=& c_1 (\rho^ne^{in\theta}) + c_2 (\rho^ne^{-in\theta}) \\ &=& c_1 \rho^n (\cos n\theta+i\sin n\theta) + c_2 \rho^n (\cos n\theta-i\sin n\theta) \\ &=& (c_1+c_2) \rho^n \cos n\theta + i(c_1-c_2)\rho^n\sin n\theta \\ &=& B_1 \rho^n \cos n\theta + B_2\rho^n\sin n\theta \end{eqnarray*} 其中 $B_1=c_1+c_2$, $B_2=i(c_1-c_2)$ 為常數。$\Box$

例 4.5: 設 $a_n=a_{n-1}-a_{n-2}$, $n\ge 3$, $a_1=1$, $a_2=0$, 求 $a_n$ 的解。

解: 特徵方程式為 $\alpha^2-\alpha+1=0$, 所以 $\alpha=\frac{1\pm\sqrt{3}i}{2}$, 則 $\rho=\sqrt{(\frac{1}{2})^2+(\frac{\sqrt{3}}{2})^2}=1$, $\theta=\tan^{-1}((\sqrt{3}/2)/(1/2))=\tan^{-1}\sqrt{3}=\frac{\pi}{3}$, 因此 $a_n=B_1\cos\frac{\pi}{3}+B_2\sin\frac{\pi}{3}=\frac{1}{2}B_1+\frac{\sqrt{3}}{2}B_2$。 代入邊界條件得 $$ \left \{ \begin{array}{ll} a_1 = B_1 \cos\frac{\pi}{3} + B_2 \sin \frac{\pi}{3} = \frac{1}{2}B_1 + \frac{\sqrt{3}}{2}B_2 = 1 \\ a_2 = B_1 \cos\frac{2\pi}{3} + B_2 \sin\frac{2\pi}{3} = - \frac{1}{2}B_1 + \frac{\sqrt{3}}{2}B_2 = 0 \end{array} \right. $$ 由聯立方程式解出可得 $B_1=1$, $B_2=\frac{1}{\sqrt{3}}$, 所以 $a_n=\cos\frac{n}{3}\pi+\frac{1}{\sqrt{3}}\sin\frac{n}{3}\pi$, $n\geq 1$。$\Box$

例 4.6: 設 $b\gt 0$, $n\times n$ 行列式 $$ D_n = \begin{vmatrix} ~b~ & ~b & ~0 & ~0 & ~\cdots & ~0 & ~0 & ~0 \\ b & ~b & ~b & ~0 & ~\cdots & ~0 & ~0 & ~0 \\ 0 & ~b & ~b & ~b & ~\cdots & ~0 & ~0 & ~0 \\ \vdots & ~\vdots & ~\vdots & ~\vdots & ~\ddots & ~\vdots & ~\vdots & ~\vdots \\ 0 & ~0 & ~0 & ~0 & ~\cdots & ~b & ~b & ~0 \\ 0 & ~0 & ~0 & ~0 & ~\cdots & ~b & ~b & ~b \\ 0 & ~0 & ~0 & ~0 & ~\cdots & ~0 & ~b & ~b \end{vmatrix} $$ 求 $D_n$之值。

解: 對第一列展開得 \begin{eqnarray*} D_n &=& b \underbrace{\begin{vmatrix} ~b~ & ~b~ & ~0~ & ~\cdots~ & ~0~ & ~0~ & ~0~ \\ b & b & b & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & b & b & 0 \\ 0 & 0 & 0 & \cdots & b & b & b \\ 0 & 0 & 0 & \cdots & 0 & b & b \end{vmatrix}}_{D_{n-1}} - b \begin{vmatrix} ~b~ & ~b~ & ~0~ & ~\cdots~ & ~0~ & ~0~ & ~0~ \\ 0 & b & b & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & b & b & 0 \\ 0 & 0 & 0 & \cdots & b & b & b \\ 0 & 0 & 0 & \cdots & 0 & b & b \end{vmatrix}_{(n-1)\times(n-1)} \\ &=& bD_{n-1} - b^2 \underbrace{\begin{vmatrix} ~b~ & ~b~ & ~\cdots~ & ~0~ & ~0~ & ~0~ \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & b & b & 0 \\ 0 & 0 & \cdots & b & b & b \\ 0 & 0 & \cdots & 0 & b & b \end{vmatrix}}_{D_{n-2}} \quad \mbox{(對第一行展開的結果)} \\ &=& bD_{n-1} - b^2D_{n-2} \end{eqnarray*} 另外, $D_1=|b|=b$, $D_2= \begin{vmatrix} ~b~& ~b~ \\ b & ~b~ \end{vmatrix}=0$, 得遞迴關係式 $D_n=bD_{n-1}-b^2D_{n-2}$, $D_1=b$, $D_2=0$。

特徵方程式 $\alpha^2-b\alpha+b^2=0$, 其兩共軛複數根為 $\alpha=\frac{b\pm\sqrt{-3b^2}}{2} =b[\frac{1}{2}\pm\frac{\sqrt{3}}{2}i]$, 所以 $\delta=\frac{b}{2}$, $\omega=\frac{\sqrt{3}}{2}b$, $\rho=\sqrt{\delta^2+\omega^2}=b$, $\theta=\tan^{-1}\frac{\omega}{\delta}=\tan^{-1}\sqrt{3}=\frac{\pi}{3}$。 因此 $D_n=b^n[B_1\cos(\frac{n\pi}{3})+B_2\sin(\frac{n\pi}{3})]$, 代入邊界條件得 $$ \left \{ \begin{array}{ll} D_1 = b(\frac{1}{2}B_1 + \frac{\sqrt{3}}{2}B_2) = b \\ D_2 = b^2(- \frac{1}{2}B_1 + \frac{\sqrt{3}}{2}B_2) = 0 \end{array} \right. $$ 解聯立方程式得 $B_1=1$, $B_2=\frac{1}{\sqrt{3}}$, 所以 $D_n=b^n[\cos(\frac{n\pi}{3}) +\frac{1}{\sqrt{3}}\sin(\frac{n\pi}{3})]$, $n\geq 1$。$\Box$

若解出來的特徵根包含不止 I, II, III 的其中一型時, 則 $a_n$ 為各型的和, 例如若解出的特徵根為 2, 2, 4, 5, $\frac{1\pm\sqrt{3}i}{2}$, 則 $a_n=(c_1+c_2n)2^n+d_14^n+d_25^n+B_1\cos\frac{n}{3}\pi+B_2\sin\frac{n}{3}\pi$。

例 4.7: 設 $a_n-8a_{n-1}+20a_{n-2}-16a_{n-3}=0$, 求 $a_n$ 的解。

解: 特徵方程式為 $\alpha^3-8\alpha^2+20\alpha-16=0$, 因式分解可得 $(\alpha-2)^2(\alpha-4)=0$, 所以 $\alpha=2, 2, 4$, 故可設 $a_n=(c_0+c_1n)2^n+c_24^n$。$\Box$

以上的所有情形都可以用矩陣的形式來表示, 下面分別對三種情形舉例, 介紹其對應的矩陣表示法:

例 4.8: (相異根) 設 $a_{n+2}-6a_{n+1}+8a_n=0$, $n\ge 0$, $a_0=1$, $a_1=2$, 求 $a_n$ 的解。

解: 可將上述的遞迴關係式寫成 \begin{eqnarray*} \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix} = A \begin{bmatrix} a_{n-1} \\ a_n \end{bmatrix} = A^2 \begin{bmatrix} a_{n-2} \\ a_{n-1} \end{bmatrix} = \cdots = A^n \begin{bmatrix} a_0 \\ a_1 \end{bmatrix} \end{eqnarray*} 其中 $A= \begin{bmatrix} 0 & 1 \\ ~-8~ & ~6~ \end{bmatrix}$。 只要計算出 $A^n$, 即可求得此遞迴關係式, 因為 $A^n$ 的計算較複雜, 先將 $A$ 分解成標準形式 (對角化或 Jordan 形式)。 經過計算, 在此例子中 $A$ 可對角化, 所以 $A^n$ 可利用矩陣的對角化性質簡單的求得。 因為 $A=P\Lambda P^{-1}$, 其中 $\Lambda$ 是 $A$ 對應的特徵根, 而 $P$ 的第一行為特徵根 $2$ 所對應的特徵向量, 第二行為特徵根 $4$ 所對應的特徵向量, 可得 $\Lambda= \begin{bmatrix} ~2~ & ~0~ \\ 0 & 4 \end{bmatrix}$, $P= \begin{bmatrix} ~1~ & ~1~ \\ 2 & 4 \end{bmatrix}$, 所以 $A^n=P\Lambda^nP^{-1}$ 即可很容易求得。將起始條件代入, 可得 \begin{eqnarray*} \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix} \!=\! \begin{bmatrix} ~1~ & ~1~ \\ 2 & 4 \end{bmatrix}\! \begin{bmatrix} ~2~ & ~0~ \\ 0 & 4 \end{bmatrix}^n\! \begin{bmatrix} ~1~ & ~1~ \\ 2 & 4 \end{bmatrix}^{-1}\! \begin{bmatrix} 1 \\ 2 \end{bmatrix} \!=\! \left[\!\begin{array}{ll} 2^{n+1}\!-\!4^n & 2^{2n-1}\!-\!2^{n-1} \\ 2^{n+2}\!-\!4^{n+1} & 2^{2n+1}\!-\!2^n \end{array}\!\right]\! \begin{bmatrix} 1 \\ 2 \end{bmatrix} \!=\! \begin{bmatrix} 2^n \\ 2^{n+1} \end{bmatrix} \end{eqnarray*} 因此 $a_n=2^n$, $n\ge 0$。$\Box$

例 4.9: (重根) 設 $a_{n+2}-4a_{n+1}+4a_n=0$, $n\ge 0$, $a_0=1$, $a_1=2$, 求 $a_n$ 的解。

解: 可將上述的遞迴關係式寫成 \begin{eqnarray*} \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix} = A \begin{bmatrix} a_{n-1} \\ a_n \end{bmatrix} = \cdots = A^n \begin{bmatrix} a_{0} \\ a_1 \end{bmatrix} \end{eqnarray*} 其中 $A= \begin{bmatrix} 0 & 1 \\ ~-4~ & ~4~ \end{bmatrix}$。 $A$ 的特徵根有 $2$ 的二重根, 而特徵向量只有一個 $\begin{bmatrix} 1 \\ 2 \end{bmatrix}$, 因此 $A$ 無法對角化。但可利用矩陣 Jordan 形式算出 $J=P^{-1}AP= \begin{bmatrix} ~2~ & ~1~ \\ 0 & 2 \end{bmatrix}$, 其中 $P= \begin{bmatrix} ~1~ & ~-\frac{1}{2}~ \\ 2 & ~0 \end{bmatrix}$。 故 $A^n=PJ^nP^{-1}$ 即可很容易求得。將起始條件代入, 可得 \begin{eqnarray*} \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix} \!=\! \begin{bmatrix} ~1~& ~-\frac{1}{2}~ \\ 2 & 0 \end{bmatrix}\!\begin{bmatrix} ~2~ & ~1~ \\ 0 & 2 \end{bmatrix}^n \begin{bmatrix} ~1~ & ~-\frac{1}{2}~~ \\ 2 & 0 \end{bmatrix}^{-1}\! \begin{bmatrix} 1 \\ 2 \end{bmatrix} \!=\! \begin{bmatrix} 2^n\!-\!n2^n & ~n2^{n-1} \\ -n2^{n+1} & ~2^n\!+\!n2^n \end{bmatrix}\! \begin{bmatrix} 1 \\ 2 \end{bmatrix} \!=\! \begin{bmatrix} 2^n \\ 2^{n+1} \end{bmatrix} \end{eqnarray*} 因此 $a_n=2^n$, $n\ge 0$。$\Box$

例 4.10: (共軛複根) 設 $a_{n+2}-a_{n+1}+a_n=0$, $n\ge 0$, $a_0=1$, $a_1=2$, 求 $a_n$ 的解。

解: 可將上述的遞迴關係式寫成 \begin{eqnarray*} \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix} = A \begin{bmatrix} a_{n-1} \\ a_n \end{bmatrix} = \cdots = A^n \begin{bmatrix} a_{0} \\ a_1 \end{bmatrix} \end{eqnarray*}

其中 $A= \begin{bmatrix} 0 & ~1 \\ -1 & ~1 \end{bmatrix}$。 只要計算出 $A^n$, 即可求得此遞迴關係式。
先將 $A$ 分解成標準形式 (對角化或 Jordan 形式), 經過計算, 在此例子中 $A$ 可對角化, 所以 $A^n$ 可利用矩陣的對角化性質簡單的求得。因為 $A=P\Lambda P^{-1}$, 其中 $\Lambda$ 是 $A$ 對應的特徵根, 而 $P$ 的第一行為特徵根 $\frac{1+\sqrt{3}i}{2}$ 所對應的特徵向量, 第二行為特徵根 $\frac{1-\sqrt{3}i}{2}$ 所對應的特徵向量, 可得 $\Lambda= \begin{bmatrix} \frac{1+\sqrt{3}i}{2} & ~0 \\ 0 & ~\frac{1-\sqrt{3}i}{2} \end{bmatrix}$, $P= \begin{bmatrix} \frac{1+\sqrt{3}i}{2} & ~\frac{1-\sqrt{3}i}{2} \\ 1 & ~1 \end{bmatrix}$, 所以 $A^n=P\Lambda^nP^{-1}$ 即可很容易求得。將起始條件代入, 可得 \begin{eqnarray*} \begin{bmatrix} a_n \\ a_{n+1} \end{bmatrix} &=& \begin{bmatrix} \frac{1+\sqrt{3}i}{2} & ~\frac{1-\sqrt{3}i}{2} \\ 1 & ~1 \end{bmatrix} \begin{bmatrix} \frac{1+\sqrt{3}i}{2} & ~0 \\ 0 & ~\frac{1-\sqrt{3}i}{2} \end{bmatrix}^n \begin{bmatrix} \frac{1+\sqrt{3}i}{2} & ~\frac{1-\sqrt{3}i}{2} \\ 1 & ~1 \end{bmatrix}^{-1} \begin{bmatrix} 1 \\ 2 \end{bmatrix} \\ &=& \begin{bmatrix} \frac{2^{-n-1}((1\!-\!\sqrt{3}i)^n(3\!-\!\sqrt{3}i)+(1\!+\!\sqrt{3}i)^n(3\!+\!\sqrt{3}i))}{3} & ~\frac{i2^{-n}((1-\sqrt{3}i)^n-(1+\sqrt{3}i)^n)}{\sqrt{3}} \\ \frac{i2^{-n}(-(1-\sqrt{3}i)^n+(1+\sqrt{3}i)^n)}{\sqrt{3}} & ~\frac{2^{-n-1}((3\!-\!\sqrt{3}i)(1\!+\!\sqrt{3}i)^n+(1\!-\!\sqrt{3}i)^n(3\!+\!\sqrt{3}i))}{3} \end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} \\ &=& \begin{bmatrix} 2^{-n-1}((1-\sqrt{3}i)^n(1+\sqrt{3}i)+(1-\sqrt{3}i)(1+\sqrt{3}i)^n) \\ 2^{-n}((1-\sqrt{3}i)^n+(1+\sqrt{3}i)^n) \end{bmatrix} \end{eqnarray*} 因此 $a_n=2^{-n-1}((1-\sqrt{3}i)^n(1+\sqrt{3}i)+(1-\sqrt{3}i)(1+\sqrt{3}i)^n)$, $n\ge 0$。$\Box$

綜合以上的例子, 對於一般的常係數 $k$ 階遞迴關係式: $$ C_0a_n + C_1a_{n-1} + \cdots + C_ka_{n-k} = 0, \quad n \ge k $$ 有下列矩陣的表達式: $$ \begin{bmatrix} a_n \\ a_{n+1} \\ \vdots \\ a_{n-k+1} \end{bmatrix} = A \begin{bmatrix} a_{n-1} \\ a_{n} \\ \vdots \\ a_{n-k} \end{bmatrix}, \quad A = \begin{bmatrix} 0 & ~1 & ~0 & ~\cdots & ~0 \\ 0 & ~0 & ~1 & ~\cdots & ~0 \\ 0 & ~0 & ~0 & ~\cdots & ~0 \\ \vdots & ~\vdots & ~\vdots & ~\ddots & ~\vdots \\ 0 & ~0 & ~0 & ~\cdots & ~1 \\ -\frac{C_{k}}{C_0} & ~-\frac{C_{k-1}}{C_0} & ~-\frac{C_{k-2}}{C_0} & ~\cdots & ~-\frac{C_1}{C_0} \end{bmatrix} $$ 由矩陣的理論可知 $A$ 的特徵方程式與遞迴關係式成比例, 且 $A$ 的特徵方程式如果有相異根或共軛複根時, 則 $A$ 可以對角化, 故可利用對角化簡單的算出 $A^n$, 矩陣 $A$ 可對角化故其解會設成定理 4.1 及定理 4.3 的形式; 而當 $A$ 的特徵根為重根時, 矩陣 $A$ 僅具有 Jordan 形式不可對角化需藉由 Jordan 形式的轉換, 即可以求出 $A^n$, 所以可以設成定理 4.2 的形式。

根據上面三個情形的分析可得到下面表 (2) 的結果。

表2. 齊次解型式

特徵根型式	一般解型式
相異根	$a_n=c_1\alpha_1^n+c_2\alpha_2^n+\cdots+c_k\alpha_k^n$
重根	$a_n=u_1(n)+u_2(n)+\cdots+u_t(n),$ $u_i(n)=(c_{i_0}+c_{i_1}n+\cdots+c_{i_{m_i-1}}n^{m_i-1})\alpha_i^n$
共軛複根	$a_n=B_1\rho^n\cos n\theta+B_2\rho^n\sin n\theta$ 其中 $B_1$, $B_2$ 為常數

4.2. 非齊次常係數線性遞迴關係 (nonhomogeneous linear recurrence relation with constant coefficients)

接下來考慮非齊次求解, 即 $f(n)\neq 0$, 假設 $a_n^{(h)}$ 及 $a_n^{(p)}$ 分別為此遞迴關係式的齊次解 (general solution)及特解(particular solution), 滿足 \begin{eqnarray*} C_0a_n^{(h)} + C_1a_{n-1}^{(h)} + \cdots + C_ka_{n-k}^{(h)} &=& 0 \quad \mbox{且} \\ C_0a_n^{(p)} + C_1a_{n-1}^{(p)} + \cdots + C_ka_{n-k}^{(p)} &=& f(n) \end{eqnarray*} 則 $C_0(a_n^{(h)}+a_n^{(p)})+C_1(a_{n-1}^{(h)}+a_{n-1}^{(p)})+\cdots+C_k(a_{n-k}^{(h)}+a_{n-k}^{(p)})=f(n)$, 所以 $a_n=a_n^{(h)}+a_{n}^{(p)}$ 為此遞迴關係式的解。因此, 解非齊次常係數線性遞迴關係式只比齊次多一道求特解的手續, 至於 $a_n^{(p)}$ 如何決定, 以下分成三種常見可解的情形來討論:

定理 4.4: (非齊次項為一多項式) 若 $f(n)=\sum^k_{i=0}c_in^i$, 其中 $c_1, c_2, \ldots, c_k$ 為常數且 $c_k\neq 0$, 則 $$ a_n^{(p)} = n^r(d_0+d_1n+\cdots+d_kn^k) $$ 其中 $r=\left \{ \begin{array}{ll} 0, & \quad \mbox{若 1不為特徵方程式的根} \\ 1\mbox{的重根數}, & \quad \mbox{若 1為特徵方程式的根} \end{array} \right.$

證明: 不妨假設 $C_0=1$, 在此舉二階常係數線性非齊次遞迴方程式 \begin{equation} \label{eqnB:33559} %(4.2) a_n+C_1a_{n-1}+C_2a_{n-2}=f(n) \end{equation} 且$f(n)=k_2n^2+k_1n+k_0$來說明, 其他階可以 用相同的辦法證明。它所對應的特徵方程式為 \begin{equation} %(4.3) \alpha^2 + C_1 \alpha + C_2 = 0 \label{eqnB:37602} \end{equation}

1. 若 $\alpha=1$ 不是特徵方程式 (\ref{eqnB:37602}) 的根, 則我們設 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = d_0 + d_1n + d_2n^2 \quad (d_0, d_1, d_2 \mbox{ 為特定常數}) $$ 代入 (\ref{eqnB:33559}) 化簡得 \begin{eqnarray*} && (d_2+C_1d_2+C_2d_2)n^2 + [d_1+C_1(d_1-2d_2)+ C_2(d_1-4d_2)]n \\ && + [d_0+C_1(d_2-d_1+d_0)+C_2(4d_2-d_1+d_0)] \\ &=& k_2n^2 + k_1n + k_0 \end{eqnarray*} 比較係數得 \begin{equation} \label{eqnB:92149} %(4.4) \left \{ \begin{array}{ll} d_2(1+C_1+C_2) = k_2 \\ d_1(1+C_1+C_2) - 2d_2(C_1+2C_2) = k_1 \\ d_0(1+C_1+C_2) - d_1(C_1+C_2) + d_2(C_1+4C_2) = k_0 \end{array} \right. \end{equation} 由於 $\alpha=1$ 不是 $\alpha^2+C_1\alpha+C_2=0$ 的根, 即 $1+C_1+C_2\neq 0$, 故 $d_2$, $d_1$, $d_0$可以確定。 則 $a_n^{(p)}=d_2n^2+d_1n+d_0$ 是 (\ref{eqnB:33559}) 的特解。
2. 若 $\alpha=1$ 是特徵方程式 $\alpha^2+C_1\alpha+C_2=0$ 的單根, 即 $1+C_1+C_2=0$。 因為判別式 $\Delta=C_1^2-4C_2\gt 0$, 所以特徵方程式的另一個根為 $\alpha_2=-(1+C_1)=C_2\neq1$, 這樣方程組 (\ref{eqnB:92149}) 就不能定出 $d_2$。此時令 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = n(d_0+d_1n+d_2n^2) $$ 代入 (\ref{eqnB:33559}), 比較係數, 且利用 $1+C_1+C_2=0$ 可得 \begin{equation} \label{eqnB:34708} %(4.5) \left \{ \begin{array}{ll} d_2(-3C_1-6C_2) = k_2 \\ d_2(3C_1+12C_2) + d_1(-2C_1-4C_2) = k_1 \\ d_2(-C_1-8C_2) + d_1(C_1+4C_2) + d_0(-C_1-2C_2) = k_0 \end{array} \right. \end{equation} 由 $C_2\neq 1$, $1+C_1+C_2=0$, $C_1+2C_2\neq 0$, 可確定 $d_2$, $d_1$, $d_0$。
3. 如果 $\alpha=1$ 是特徵方程式 $\alpha^2+C_1\alpha+C_2=0$ 的重根, 這時判別式 $\Delta=0$, $\alpha_1=\alpha_2=-\frac{C_1}{2}=1$, 所以 $C_1=-2$, $C_2=1$, 因此 $C_1+2C_2=0$。 這樣從方程組 (\ref{eqnB:34708}) 中確定不了 $d_2$。此時我們設 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = n^2(d_0+d_1n+d_2n^2) $$ 代入 (\ref{eqnB:33559}), 用比較係數及重根的條件得 $$ \left \{ \begin{array}{ll} 6d_2(C_1+4C_2) = k_2 \\ 3d_1(C_1+4C_2) - 4d_2(C_1+8C_2) = k_1 \\ d_0(C_1+4C_2) - d_1(C_1+8C_2) + d_2(C_1+16C_2) = k_0 \end{array} \right. $$ 這樣可以確定 $d_2$, $d_1$, $d_0$。

因此, 當 $f(n)$ 是二次多項式時, (\ref{eqnB:33559}) 的特解可以這樣來確定:

1. 若 $\alpha=1$ 不是特徵方程式的根, 則 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = d_0 + d_1n + d_2n^2 $$
2. 若 $\alpha=1$ 是特徵方程式的單根, 則 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = n(d_0+d_1n+d_2n^2) $$
3. 若 $\alpha=1$ 是特徵方程式的重根, 則 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = n^2(d_0+d_1n+d_2n^2){\Box} $$

例 4.11: (1不為特徵根) 設 $a_n-7a_{n-1}+10a_{n-2}=4n-5$, $n\ge 2$, $a_0=2$, $a_1=4$, 求 $a_n$ 的解。

解: 特徵方程式為 $\alpha^2-7\alpha+10=(\alpha-5)(\alpha-2)=0$, 得 $\alpha=2, 5$, 所以 $a_n^{(h)}=c_12^n+c_25^n$。 因為特徵根不含 1, 令 $a_n^{(p)}=d_0+d_1n$ 代入原遞迴關係式得 $(d_0+d_1n)-7(d_0+d_1(n-1))+10(d_0+d_1(n-2))=4n-5$。 整理後可得 $4d_1n+(4d_0-13d_1)=4n-5$, 所以 $$ \left \{ \begin{array}{ll} 4d_1 = 4 \\ 4d_0 - 13d_1 = -5 \end{array} \right. $$ 可得 $d_0=2$, $d_1=1$。所以 $a_n^{(p)}=n+2$, 則 $a_n=a_n^{(h)}+a_n^{(p)}=c_12^n+c_25^n+n+2$ 代入邊界條件可得 $$ \left \{ \begin{array}{ll} a_0 = c_1 + c_2 + 2 = 2 \\ a_1 = 2c_1 + 5c_2 + 3 = 4 \end{array} \right. $$ 求聯立方程式可得 $c_1=-\frac{1}{3}$, $c_2=\frac{1}{3}$, 所以 $a_n=-\frac{1}{3}\cdot2^n+\frac{1}{3}\cdot5^n+n+2$, $n\geq 0$。$\Box$

例 4.12: (1為特徵根的二重根) 設 $a_n=2a_{n-1}-a_{n-2}+4$, $n\ge 2$, $a_0=0$, $a_1=2$, 求 $a_n$ 的解。

解: 特徵方程式為 $\alpha^2-2\alpha+1=(\alpha-1)^2=0$, 得 $\alpha=1, 1$, 所以 $a_n^{(h)}=(c_0+c_1n)\cdot1^n=c_0+c_1n$。 因為 1為特徵根, 令 $a_n^{(p)}=n^2d_0$ 代入原遞迴關係式得 $n^2d_0-2(n-1)^2d_0+(n-2)^2d_0=4$。 將 $n=0$ 代入$-2d_0+4d_0=4$, 整理可得 $2d_0=4$, 即 $d_0=2$, 所以 $a_n^{(p)}=2n^2$。則 $$ a_n = a_n^{(h)} + a_n^{(p)} = c_0 + c_1n + 2n^2 $$ 代入邊界條件 $$ \left \{ \begin{array}{ll} a_0 = c_0 = 0 \\ a_1 = c_0 + c_1 + 2 = 2 \end{array} \right. $$ 解聯立方程式可得 $c_0=c_1=0$。所以 $a_n=2n^2$, $n\geq 0$。$\Box$

定理4.5: (非齊次項為一指數函數) 若 $f(n)=c\lambda^n$, 其中 $c, \lambda\neq1$ 為常數, 則 $$ a_n^{(p)} = (d_0+d_1n+\cdots+d_rn^r)\lambda^n $$ 其中 $r=\left \{ \begin{array}{ll} 0, & \quad \mbox{若 $\lambda$ 不為特徵方程式的根} \\ \lambda \mbox{ 之重根數}, & \quad \mbox{若 $\lambda$ 為特徵方程式的根} \end{array} \right. $

證明: 相同地, 在此舉二階常係數線性非齊次遞迴方程式來說明:

1. 若 $\lambda$ 不是特徵方程式 (\ref{eqnB:37602}) 的根, 設 (\ref{eqnB:33559}) 的特解為 $a_n^{(p)}=d_0\lambda^n$, 代入 (\ref{eqnB:33559}) 得 $$ d_0 \lambda^n + C_1(d_0\lambda^{n-1}) + C_2(d_0\lambda^{n-2}) = c\lambda^n $$ 整理後得 $d_0(\lambda^2\!+\!C_1\lambda\!+\!C_2)\!=\!c\lambda^2$, 因為 $\lambda^2\!+\!C_1\lambda\!+\!C_2\!\neq\! 0$, 所以 $d_0\!=\!\frac{c\lambda^2}{\lambda^2\!+\!C_1\lambda\!+\!C_2}$。
2. 若 $\lambda$ 是特徵方程式的單根, 即 $\lambda^2+C_1\lambda+C_2=0$, 設另一根為 $q$, $q\neq\lambda$。因為 $(\alpha-\lambda)(\alpha-q)=0$, 所以 $$ \left \{ \begin{array}{ll} C_1 = -(\lambda+q), \quad C_1 \neq -2\lambda \\ C_2 = \lambda q, \quad C_2 \neq \lambda^2 \end{array} \right. $$ 設 (\ref{eqnB:33559}) 的特解為 $a_n^{(p)}=(d_0+d_1n)\lambda^n$, 代入 (\ref{eqnB:33559}) 得 $$ (d_0+d_1n)\lambda^n + C_1(d_0+d_1(n-1))\lambda^{n-1} + C_2(d_0+d_1(n-2))\lambda^{n-2} = c\lambda^n $$ 整理後得 $d_0(\lambda^2+C_1\lambda+C_2)+nd_1(\lambda^2+C_1\lambda+C_2)-d_1(\lambda C_1+2C_2)=c\lambda^2$, 由於 $\lambda^2+C_1\lambda+C_2=0$, 所以 $C_1\lambda+C_2=-\lambda^2$, 因此 $C_1\lambda+2C_2=-\lambda^2+C_2\neq 0$, 故 $d_1=\frac{-c\lambda^2}{C_1\lambda+2C_2}$。
3. 若 $\lambda$ 是特徵方程式的重根, 即 $\lambda^2+C_1\lambda+C_2=0$, $\alpha_1=\alpha_2=\lambda$, 於是 $\lambda=-\frac{C_1}{2}$, $C_1=-2\lambda$, $C_2=\lambda^2$。 此時令 (\ref{eqnB:33559}) 的特解為 $a_n^{(p)}=(d_0+d_1n+d_2n^2)\lambda^n$, 代入 (\ref{eqnB:33559}) 得 \begin{eqnarray*} && \hskip -25pt (d_0+d_1n+d_2n^2)\lambda^n + C_1(d_0+d_1(n-1) + d_2(n-1)^2)\lambda^{n-1} \\ && + C_2(d_0+d_1(n-2)+d_2(n-2)^2)\lambda^{n-2} = c\lambda^n \end{eqnarray*} 整理後得 $d_2(C_1\lambda+4C_2)=c\lambda^2$, 因為 $C_1\lambda+4C_2\neq 0$, 所以 $d_2=\frac{c\lambda^2}{C_1\lambda+4C_2}$。

因此, 當 $f(n)=c\lambda^n$時, (\ref{eqnB:33559}) 的特解可以這樣來確定:

1. 若 $\lambda$ 不是特徵方程式的根, 則 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = d_0\lambda^n, \quad d_0 = \frac{c\lambda^2}{\lambda^2+C_1\lambda+C_2} $$
2. 若 $\lambda$ 是特徵方程式的單根, 則 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = (d_0+d_1n)\lambda^n, \quad d_1 = \frac{-c\lambda^2}{C_1\lambda+2C_2} $$
3. 若 $\lambda$ 是特徵方程式的重根, 則 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = (d_0+d_1n+d_2n^2)\lambda^n, \quad d_2=\frac{c\lambda^2}{C_1\lambda+4C_2}{\Box} $$

由以上的方法可發現當 $\lambda$ 是特徵方程式的單根或重根時, $d_0$, $d_1$會被消去, 所以可以不用設, 故也可用以下方法求解

1. 若 $\lambda$ 不是特徵方程式 (\ref{eqnB:37602}) 的根, 設 (\ref{eqnB:33559}) 的特解為 $a_n^{(p)}=d\lambda^{n+2}$ ($d$ 為特定常數), 代入 (\ref{eqnB:33559}) 得 $$ d(\lambda^2+C_1\lambda+C_2) = c $$ 因為 $\lambda^2+C_1\lambda+C_2\neq0$, 所以 $d=\frac{c}{\lambda^2+C_1\lambda+C_2}$。
2. 若 $\lambda$ 是特徵方程式的單根, 即 $\lambda^2+C_1\lambda+C_2=0$, 設另一根為 $q$, $q\neq\lambda$。因為 $(\alpha-\lambda)(\alpha-q)=0$, 所以 $$ \left \{ \begin{array}{ll} C_1 = -(\lambda+q), \quad C_1 \neq -2\lambda \\ C_2 = \lambda q, \quad C_2 \neq \lambda^2 \end{array} \right. $$ 設 (\ref{eqnB:33559}) 的特解為 $a_n^{(p)}=-dn\lambda^{n+2}$, 代入(\ref{eqnB:33559}) 得 $$ -d(C_1\lambda+2C_2) = c $$ 由於 $\lambda^2+C_1\lambda+C_2=0$, 所以 $C_1\lambda+C_2=-\lambda^2$, 因此 $C_1\lambda+2C_2=-\lambda^2+C_2\neq 0$, 故 $d=\frac{-c}{C_1\lambda+2C_2}$。
3. 若 $\lambda$ 是特徵方程式的重根, 即 $\lambda^2+C_1\lambda+C_2=0$, $\alpha_1=\alpha_2=\lambda$, 於是 $\lambda=-\frac{C_1}{2}$, $C_1=-2\lambda$, $C_2=\lambda^2$。 此時令 (\ref{eqnB:33559}) 的特解為 $a_n^{(p)}=dn^2\lambda^{n+2}$, 代入 (\ref{eqnB:33559}), 得 $$ d(C_1\lambda+4C_2) = c $$ 因為 $C_1\lambda+4C_2\neq 0$, 所以 $d=\frac{c}{C_1\lambda+4C_2}$。

因此, 當 $f(n)=c\lambda^n$ 時, (\ref{eqnB:33559}) 的特解可以這樣來確定:

1. 若 $\lambda$ 不是特徵方程式的根, 則 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = d\lambda^{n+2}, \quad d = \frac{c}{\lambda^2+C_1\lambda+C_2} $$
2. 若 $\lambda$ 是特徵方程式的單根, 則 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = -dn\lambda^{n+2}, \quad d = \frac{-c}{C_1\lambda+2C_2} $$
3. 若 $\lambda$ 是特徵方程式的重根, 則 (\ref{eqnB:33559}) 的特解為 $$ a_n^{(p)} = dn^2\lambda^{n+2}, \quad d = \frac{c}{C_1\lambda+4C_2} $$

例 4.13: ($\lambda$ 不是特徵方程式根) 設 $a_n-a_{n-1}=3\cdot2^n$, $n\ge 2$, $a_1=5$, 求 $a_n$ 的解。

解: 特徵方程式為 $\alpha-1=0$, $\alpha=1$, 則 $a_n^{(h)}=c$ 。 因為 $2$ 不為特徵根, 令 $a_n^{(p)}=d\cdot 2^n$ 代入原遞迴關係式得 $d\cdot 2^n-d\cdot 2^{n-1}=3\cdot 2^n$, 故 $d=6$, 所以 $a_n^{(p)}=6\cdot 2^n$, 則 \begin{eqnarray*} a_n &=& a_n^{(h)} + a_n^{(p)} \\ &=& c + 6\cdot 2^n \end{eqnarray*} 代入邊界條件 $5=a_1=c+12$, $c=-7$, 所以 $a_n=6\cdot 2^n-7$, $n\geq 1$。$\Box$

例 4.14: ($\lambda$ 是特徵方程式的單根) 設 $a_n-4a_{n-1}+3a_{n-2}=2\cdot3^n$, $n\ge 2$, $a_0=2$, $a_1=13$, 求 $a_n$ 的解。

解: 特徵方程式為 $\alpha^2-4\alpha+3=(\alpha-1)(\alpha-3)=0$, 則 $a_n^{(h)}=c_1\cdot1^n+c_2\cdot 3^n=c_1+c_23^n$。 因為 3 為特徵根, 令 $a_n^{(p)}=(d_1+d_2n)3^n$ 代入原遞迴關係式得 $(d_1+d_2n)3^n-4(d_1+d_2(n-1))3^{n-1} +3(d_1+d_2(n-2))3^{n-2}=2\cdot3^n$。將 $n=2$ 代入得 $9(d_1+2d_2)-12(d_1+d_2)+3d_1=18$, 所以 $6d_2=18$, 即 $d_2=3$。此時還無法求出 $d_1$, 所以 $a_n^{(p)}=(d_1+3n)3^n$, 則 \begin{eqnarray*} a_n &=& a_n^{(h)} + a_n^{(p)} \\ &=& c_1 + c_23^n + (d_1+3n)3^n \\ &=& c_1 + (c_2+d_1+3n)3^n \\ &=& c_1 + (c_3+3n)3^n, \quad \mbox{其中 } c_3 = c_2 + d_1 \end{eqnarray*} 代入邊界條件 $$ \left \{ \begin{array}{ll} a_0 = c_1 + c_3 = 2 \\ a_1 = c_1 + 3(c_3+3) = 13 \end{array} \right. $$ 由聯立方程式可得 $c_1=1$, $c_3=1$, 所以 $a_n=1+(1+3n)3^n$, $n\geq 0$。$\Box$

例 4.15: 求 0, 1, 2, 3 所組成的 $n$-序列含偶數個 0 的序列數。

解: 令 $a_n=d_1d_2\cdots d_n$, $d_i=0, 1, 2, 3$ 為所求的序列個數, 分成兩種情況來討論:

1. 若 $d_n\neq 0$, 欲使整個序列含偶數個 0, 則前面 $(n-1)$-序列需含偶數個 0, 共有 $a_{n-1}$ 種。
2. 若 $d_n=0$, 欲使整個序列含偶數個 0, 則前面 $(n-1)$-序列需含奇數個 0。 由於 4元 $(n-1)$-序列中有 $4^{n-1}$ 個序列, 其中含偶數個 0者有 $a_{n-1}$ 個, 所以含奇數個 0者有 $4^{n-1}-a_{n-1}$ 種。

由以上討論知 $a_n=3a_{n-1}+(4^{n-1}-a_{n-1})=2a_{n-1}+4^{n-1}$, 當只有 1個數字時有 1, 2, 3 共 3種序列, 即 $a_1=3$, 得遞迴關係式 $a_n=2a_{n-1}+4^{n-1}$, $n\geq 2$, $a_1=3$。

其特徵方程式為 $\alpha-2=0$, 得 $\alpha=2$, 所以 $a_n^{(h)}=c_12^n$。 令 $a_n^{(p)}=c_24^n$ 代入原遞迴關係式得 $c_24^n-2c_24^{n-1}=\frac{1}{4}\cdot4^n$, 整理後得 $(c_2-\frac{1}{2}c_2)4^n=\frac{1}{4}\cdot4^n$, 所以 $\frac{1}{2}c_2=\frac{1}{4}$, $c_2=\frac{1}{2}$, 所以 $a_n^{(p)}=\frac{1}{2}\cdot4^n$。則 $a_n=a_n^{(h)}+a_n^{(p)}=c_12^n+\frac{1}{2}\cdot4^n$ 代入邊界條件得 $3=a_1=2c_1+2$, 故 $c_1=\frac{1}{2}$, 最後可得 $a_n=\frac{1}{2}(2^n+4^n)$, $n\geq1$。$\Box$

定理 4.6: (非齊次項為 $\rho^{n}\cos n\theta$ 或 $\rho^n\sin n\theta$) 若 $f(n)=\rho^{n}\cos n\theta$ 或 $\rho^n\sin n\theta$, 其中 $\theta$ 為已知, 則 $a_n^{(p)}=\rho^n(B_1\cos n\theta+B_2\sin n\theta)$。

證明: $f(n)$ 是正弦或餘弦函數時, 即 $f(n)=c\cdot\cos n\theta$ 或 $f(n)=c\cdot\sin n\theta$, 方程式 (\ref{eqnB:33559}) 可以寫成 \begin{eqnarray} a_{1, n} + C_1a_{1, n-1} + C_2a_{1, n-2} &=& c\cos n\theta \label{eqnB:16756} \\ %(4.6) a_{2, n} + C_1a_{2, n-1} + C_2a_{2, n-2} &=& c\sin n\theta \label{eqnB:12400} %(4.7) \end{eqnarray} 其中 $C_1, C_2\in\mathbb R$。

將 (\ref{eqnB:12400}) 乘以 $i$ 後與 (\ref{eqnB:16756}) 相加, 得 \begin{equation} \label{eqnB:20022} %(4.8) L(a_n) = a_n + C_1a_{n-1} + C_2a_{n-2} = c(e^{i\theta})^n \end{equation} 其中 $a_n=a_{1, n}+ia_{2, n}$。$\Box$

這問題可以歸為 $f(n)=c\cdot k^n$ 的情形, 由於是複數解, 所以先證明下面定理。

定理 4.7: 若 $a_n^*=u_n+iv_n$ 是 (\ref{eqnB:20022}) 的一個解, 則 $$ L_1(u_n) = u_n + C_1u_{n-1} + C_2u_{n-2} = c\cos n\theta $$ $$ L_2(v_n) = v_n + C_1v_{n-1} + C_2v_{n-2} = c\sin n\theta $$

證明: 因為 $a_n^*$ 是 (\ref{eqnB:20022}) 的解 ($C_1, C_2\in\mathbb R$), 所以 \begin{eqnarray*} L(a_n^*) &=& L(u_n+iv_n) \\ &=& L(u_n) + i L(v_n) \\ &=& c(e^{i\theta})^n \\ &=& c\cos n\theta + ic\sin n\theta \end{eqnarray*} 根據複數相等定義, 得 $$ L_1(u_n) = c\cos n\theta, \quad L_2(v_n) = c\sin n\theta $$ 因此, 只要我們討論 (\ref{eqnB:20022}) 的特解的求法就可以了, 如果求得它的特解為 $a_n^{\ast}=u_n+iv_n$, 那麼 (\ref{eqnB:16756}) 的特解為 $a_n^*$ 的實部, (\ref{eqnB:12400}) 的特解為 $a_n^*$ 的虛部。

關於 (\ref{eqnB:20022}) 的特解求法完全類同於前面 II 的情況。

1. 當 $\alpha=e^{i\theta}$ 不是特徵方程式 $\alpha^2+C_1\alpha+C_2=0$ 的根時, (\ref{eqnB:20022}) 的特解設為 $$ a_n^* = d(e^{i\theta})^{n+2} $$ 代入 (\ref{eqnB:20022}) 得 $$ d = \frac{c}{(e^{i\theta})^2 + C_1(e^{i\theta})+C_2} = c_1 + ic_2 $$ 其中 \begin{eqnarray*} c_1 &=& R \Big (\frac{c}{(e^{i\theta})^2 + C_1(e^{i\theta})+C_2}\Big ) \\ c_2 &=& I \Big (\frac{c}{(e^{i\theta})^2 + C_1(e^{i\theta})+C_2}\Big ) \end{eqnarray*} 所以 \begin{eqnarray*} a_n^* &=& [c_1\cos(n+2)\theta-c_2\sin(n+2)\theta] + i[c_1\sin(n+2)\theta+c_2\cos(n+2)\theta] \\ &=& u_n + iv_n \end{eqnarray*} 其中 \begin{eqnarray*} u_n &=& c_1\cos(n+2)\theta - c_2\sin (n+2)\theta \\ v_n &=& c_1\sin(n+2)\theta + c_2\cos (n+2)\theta \end{eqnarray*} $u_n$, $v_n$ 分別是 (\ref{eqnB:16756}) 、(\ref{eqnB:12400}) 的特解。
2. 當 $\alpha=e^{i\theta}$ 是特徵方程式 $\alpha^2+C_1\alpha+C_2=0$ 的單根時, (\ref{eqnB:20022}) 的特解設為 $$ a_n^* = dn(e^{i\theta})^{n+2} $$ 代入 (\ref{eqnB:20022}) 得 $$ d = \frac{-c}{C_1(e^{i\theta})+2C_2} = c_1+ic_2 $$ 其中 $$ c_1 = R \Big (\frac{-c}{C_1e^{i\theta}+2C_2}\Big ), \quad c_2 = I \Big (\frac{-c}{C_1e^{i\theta}+2C_2}\Big ) $$ 所以 \begin{eqnarray*} a_n^* &=& n(c_1+ic_2)(e^{i\theta})^{n+2} \\ &=& n[c_1\cos(n+2)\theta-c_2\sin(n+2)\theta] + in[c_1\sin(n+2)\theta+c_2\cos(n+2)\theta] \\ &=& u_n+iv_n \end{eqnarray*} 其中 \begin{eqnarray*} u_n &=& n[c_1\cos(n+2)\theta-c_2\sin(n+2)\theta] \\ v_n &=& n[c_1\sin(n+2)\theta+c_2\cos(n+2)\theta] \end{eqnarray*} $u_n$, $v_n$ 分別是 (\ref{eqnB:16756}) 、(\ref{eqnB:12400}) 的特解。$\Box$

由於 $C_1, C_2\in\mathbb R$, 所以 $\alpha=e^{i\theta}$ 不可能是特徵方程式的重根。

因此, 對於 $f(n)=c\cos n\theta$ 或 $f(n)=c\sin n\theta$ 時, (\ref{eqnB:20022}) 的特解為:

1. 若 $\alpha=e^{i\theta}$ 不是特徵方程式的根, 則 \begin{eqnarray*} a_n^* &=& c_1\cos(n+2)\theta - c_2\sin(n+2)\theta \quad \mbox{或} \\ a_n^* &=& c_1\sin(n+2)\theta + c_2\cos(n+2)\theta \end{eqnarray*}
2. 若 $\alpha=e^{i\theta}$是特徵方程式的根, 則 \begin{eqnarray*} a_n^* &=& n[c_1\cos(n+2)\theta-c_2\sin(n+2)\theta] \quad \mbox{或} \\ ~\hskip 2.5cm a_n^* &=& n[c_1\sin(n+2)\theta+c_2\cos(n+2)\theta] \hskip 4cm~\Box \end{eqnarray*}

例 4.16: 設 $a_{n+2}-a_n=\sin(\frac{n\pi}{2})$, $n\geq 0$, $a_0=1$, $a_1=1$, 求 $a_n$ 的解。

解: 特徵方程式為 $\alpha^2-1=(\alpha-1)(\alpha+1)=0$, 得 $\alpha=1, -1$, 所以 $a_n^{(h)}=c_0\cdot1^n+c_1(-1)^n=c_0+c_1(-1)^n$。

令 $a_n^{(p)}=d_0\sin(\frac{n\pi}{2})+d_1\cos(\frac{n\pi}{2})$, 代入原式得 $d_0\sin(\frac{(n+2)\pi}{2})+d_1\cos(\frac{(n+2)\pi}{2}) -d_0\sin(\frac{n\pi}{2})-d_1\cos(\frac{n\pi}{2})=\sin(\frac{n\pi}{2})$。 整理後得 $-d_0\sin(\frac{n\pi}{2})-d_1\cos(\frac{n\pi}{2}) -d_0\sin(\frac{n\pi}{2})-d_1\cos(\frac{n\pi}{2})=\sin(\frac{n\pi}{2})$, 即 $-2d_0\sin(\frac{n\pi}{2})-2d_1\cos(\frac{n\pi}{2})=\sin(\frac{n\pi}{2})$, 所以 $d_0=-\frac{1}{2}$, $d_1=0$, 因此 $a_n^{(p)}=-\frac{1}{2}\sin(\frac{n\pi}{2})$, 所以 $a_n=a_n^{(h)}+a_n^{(p)}=c_0+c_1(-1)^n-\frac{1}{2}\sin(\frac{n\pi}{2})$。代入邊界條件得 $$ \left \{ \begin{array}{ll} a_0 = c_0 + c_1 = 1 \\ a_1 = c_0 - c_1 - \frac{1}{2} = 1 \end{array} \right. $$ 由聯立方程式可得 $c_0=\frac{5}{4}$, $c_1=-\frac{1}{4}$。 所以 $a_n=\frac{5}{4}-\frac{1}{4}(-1)^n-\frac{1}{2}\sin(\frac{n\pi}{2})$, $n\geq 0$。$\Box$

根據上面三個情形的分析可得到下面表 (3) 的結果。

表3. 非齊次特解型式

$f(n)$ 型式	特解型式
$\sum^k_{i=0}c_in^i$	$a_n^{(p)}=n^r(d_0+d_1n+\cdots+d_kn^k)$
$c\lambda^n$	$a_n^{(p)}=\left(d_0+d_1n+\cdots+d_rn^r\right)\lambda^n$
$\rho^{n}\cos n\theta $或$ \rho^n\sin n\theta$	$a_n^{(p)}=\rho^n(B_1\cos n\theta+B_2\sin n\theta)$

上述的解法可以推廣到當 $f(n)$ 為此三種型式的線性組合。 綜合以上求解非齊次遞迴關係式可分為下列的五個步驟:

• 步驟一決定 $a_n^{(h)}$ 的型式
• 步驟二決定 $a_n^{(p)}$ 的型式
• 步驟三以 $a_n^{(p)}$ 代入原遞迴關係式求 $a_n^{(p)}$ 的未定係數 (未必可以全部求出)
• 步驟四以 $a_n=a_n^{(h)}+a_n^{(p)}$ 代入邊界條件求出所有未定係數
• 步驟五寫出 $a_n$ 所求的答案

註: 若 $a_n^{(p)}$ 為非齊次常係數線性遞迴關係式 $C_0a_n+C_1a_{n-1}+\cdots+C_ka_{n-k}=f(n)$ 的一個特解, 則 $C_0(a_n-a_n^{(p)})+C_1(a_{n-1}-a_{n-1}^{(p)})+\cdots+C_k(a_{n-k}-a_{n-k}^{(p)})=0$, 設 $b_n=a_n-a_n^{(p)}$, 則上式可改寫成一常係數線性遞迴關係式 $$ C_0b_n + C_1b_{n-1} + \cdots + C_kb_{n-k}=0 $$

習題 4

下列是一些不錯的題目, 也許讀者有興趣試試, 為了方便讀者, 我們也將答案列入。

1. 設 $a_n-10a_{n-1}+21a_{n-2}=0$, $n\ge 3$, $a_1=3$, $a_2=93$, 求 $a_n$ 的解。 (答案: $-6\cdot 3^n+3\cdot 7^n$)
2. 設 $a_n-6a_{n-1}+9a_{n-2}=0$, $n\ge 3$, $a_1=3$, $a_2=0$, 求 $a_n$ 的解。 (答案: $(2-n)3^n$)
3. 設 $a_n-2a_{n-1}+2a_{n-2}=0$, $n\ge 3$, $a_1=0$, $a_2=1$, 求 $a_n$ 的解。 (答案: $(\sqrt{2})^n[-\frac{1}{2}\cos\frac{n\pi}{4}+\frac{1}{2}\sin\frac{n\pi}{4}]$)
4. 求以下遞迴關係式的解 $a_n-6a_{n-1}+12a_{n-2}-8a_{n-3}=0$, $n\ge 4$, 其邊界條件為 $a_0=1,a_1=0,a_3=-160$。 (答案: $(1+2n-3n^2)2^n$, $n\geq 0$)
5. 求下列 $n$ 階行列式之值 $$ D_{n} = \begin{vmatrix} ~5~ & ~3~ & ~0~ & ~\cdots~ & ~0~ & ~0~ & ~0~ \\ 2 & 5 & 3 & \ddots & 0 & 0 & 0 \\ 0 & 2 & 5 & \ddots & 0 & 0 & 0 \\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & \ddots & 5 & 3 & 0 \\ 0 & 0 & 0 & \ddots & 2 & 5 & 3 \\ 0 & 0 & 0 & \cdots & 0 & 2 & 5 \end{vmatrix} $$ (答案: $-2^{n+1}+3^{n+1}$, $n\geq 1$)
6. 求下列行列式之值 $$ \begin{vmatrix} ~6~ & ~3~ & ~0~ & ~\cdots~ & ~0~ & ~0~ & ~0~ \\ 3 & 6 & 3 & \ddots & 0 & 0 & 0 \\ 0 & 3 & 6 & \ddots & 0 & 0 & 0 \\ \vdots & \ddots & \ddots & \ddots & \ddots & \ddots & ~\vdots~ \\ 0 & 0 & 0 & \ddots & 6 & 3 & 0 \\ 0 & 0 & 0 & \ddots & 3 & 6 & 3 \\ 0 & 0 & 0 & \cdots & 0 & 3 & 6 \end{vmatrix}_{n\times n} \quad\hbox{(答案: $(1+n)3^{n}$, $n\geq 1$)} $$
7. 求解遞迴關係式 $a_n=2a_{n-1}+3$, $n\ge 2$, $a_1=3$。 (答案: $3\cdot2^n-3$, $n\geq 1$)
8. 求解遞迴關係式 $a_n=5a_{n-1}-6a_{n-2}+4n$, $n\geq 2$, $a_0=9$, $a_1=14$。 (答案: $2^n+3^n+2n+7$, $n\geq 0$)
9. 求遞迴關係式 $a_{n+2}-8a_{n+1}+15a_n=6\cdot3^n+10\cdot5^n$, $n\geq 0$, $a_0=2$, $a_1=10$ 的解。 (答案: $(1-n)3^n+(1+n)5^n,n\geq 0$)
10. 求遞迴關係式 $a_{n+2}+4a_{n+1}-12a_n=\beta_1\cdot 2^n$, $n\ge 1$, $a_1=2$, $a_2=4$ 的解。 (答案: $(1-\frac{5}{64}\beta_1)2^n+(\frac{-\beta_1}{192})(-6)^n+\frac{\beta_1}{16}n2^n$)
11. 求遞迴關係式 $a_{n+2}+4a_{n+1}-12a_n=3n-1$, $n\ge 1$, $a_1=2$, $a_2=4$ 的解。 (答案: $(\frac{21}{16})2^n-(\frac{11}{2352})(-6)^n-\frac{11}{49}-\frac{3}{7}n$)
12. 已知數列 $\{a_n\}$ 的第一項 $a_1=\frac{3}{5}$, 第二項 $a_2=\frac{31}{100}$, 並且數列 $(a_2-\frac{1}{10}a_1), (a_3-\frac{1}{10}a_2), \ldots, (a_{n+1}-\frac{1}{10}a_n), \ldots$ 是公比為 $\frac{1}{2}$ 的等比數列,
    1. 求數列 $\{a_n\}$ 的一般解公式。
    2. 證明數列 $\log_{10}(a_2-\frac{1}{2}a_1), \log_{10}(a_3-\frac{1}{2}a_2), \ldots, \log_{10}(a_{n+1}-\frac{1}{2}a_n), \ldots$ 是公差為 $-1$ 的等差數列。
    (答案: (a)$-\frac{1}{4}(\frac{1}{10})^n+\frac{5}{4}(\frac{1}{2})^n$)
13. 有一個樓梯共有 10階。某人上樓一步一階或一步二階, 則上樓方法共有幾種? (答案: $89$)
14. 在一個大小尺寸為 $2\times 31$ 的棋盤上, 用 31個 $2\times 1$ 尺寸的矩形覆蓋, 問有多少種覆蓋法? (答案: $2178309$)
15. (方程式根的問題) 設 $\alpha$, $\beta$ 為實係數二次方程式 $ax^2+bx+c=0$ 之二根, 若 $a\neq 0$, 則 $\alpha+\beta=-b/a$ (兩根之和), $\alpha\beta=c/a$ (兩根之積), 根據這些性質及乘法公式, 我們可以推得 \begin{eqnarray*} \alpha^2 + \beta^2 &=& (\alpha+\beta)^2 - 2\alpha\beta = (-b/a)^2 - 2(c/a) = (b^2-2ac)/a^2 \\ \alpha^3 + \beta^3 &=& (\alpha+\beta)^3 - 3\alpha\beta(\alpha+\beta) = (-b/a)^3 - 3(c/a)(-b/a) = (-b^3+3abc)/a^3 \\ \alpha^4 + \beta^4 &=& (\alpha^2+\beta^2) - 2(\alpha\beta)^2 = (b^4-4b^2ac+2a^2c^2)/a^4 \end{eqnarray*} 但是欲求 $\alpha^n+\beta^n$ 之值, 其乘法公式之困難度亦增加很多, 故今想利用遞迴方法來得尋求解題之道。 (答案: $T_{n+2}=\left(-\frac{b}{a}\right)T_{n+1}+\left(-\frac{c}{a}\right)T_{n}$)
16. (錯排問題) 當聖誕節來臨時, 有一天大華正在寫一堆卡片, 突然想到一個有趣的數學問題。 假設卡片與信封已分別寫上了名字, 試問在裝入時, 全部裝錯 (即卡片與信封上名字不符) 的裝法共有幾種呢? (答案: $a_n=(n-1)(a_{n-1}+a_{n-2}),n\gt 2$)
17. 甲固定在 9 PM 到 9 AM 灌溉一片草地。假設他每次在這期間可以灌 $q$ 的水量, 但是 9 AM 到9 PM 這些水量的一半會被蒸發或吸收。若此片草地在 9 PM 原本的水量有 $I$, 若 $a_n$ 表示經過 $n$ 個 12小時的週期後所剩的水量, 求 $a_n$ 的遞迴關係式。 (答案: $\frac{I-q}{2}(\sqrt{2})^{-n}\{\sqrt{2}[1-(-1)^n]+[1+(-1)^n]\}+\frac{q}{2}[3-(-1)^n], n\ge0$)
18. 設 $P_1, P_2, \ldots, P_m$ 共 $m$ 個人玩傳接球遊戲 (不可自己傳給自己), 由 $P_1$ 開始請問傳 $n$ 次回到 $P_1$ 的方法數有幾種? (答案: $\frac{m-1}{m}\left[(-1)^n+(m-1)^{n-1}\right]$)
19. 將一硬幣連續投擲 $n$ 次, 在投擲中連續出現兩次正面的機率為多少? (答案: $1-\frac{(1+\sqrt{5})^{n+2}-(1-\sqrt{5})^{n+2}}{2^{2n+2}\sqrt{5}}$)

A. 附錄: Mathematica: ${\tt RSolve}$

Mathematica 5.0 (Wolfram 2003)是一個強大的數值、符號運算、繪圖整合系統, 具有高階程式語言能力的數學軟體。 它新增一個強大的內建命令 ${\tt RSolve}$, 可以解遞迴方程。 在 5.0以前的版本中, ${\tt RSolve}$ 是置放於附加標準程式庫資料夾 ${\tt DiscreteMath}$ 中, 使用前必須將它先行載入, 載入格式: ${\tt \lt \lt DiscreteMath`RSolve`}$。${\tt RSolve}$ 的語法如下:

• $\blacksquare {\tt RSolve[eqns, a[n], n]}$ 解遞迴方程式${\tt eqns}$的解${\tt a[n]}$

或

• $\blacksquare {\tt RSolve[eqns, \mathtt{a_n}, n]]}$ 解遞迴方程式${\tt eqns}$的解$\mathtt{a_n}$

其中 ${\tt eqns}$ 為遞迴方程式及邊界條件, 可以使用函數 ${\tt a[n]}$, 或直接用 $\mathtt{a_n}$ 來表示數列 $a_n$。 如果遞迴方程式及邊界條件總個數超過一個, 則將其全部置於一個陣列 (${\tt List}$) 中。 例如解 $a_n-2a_{n-1}=3^\wedge n$, $a_1=2$, 則 ${\tt eqns}$ 的語法為 ${\tt \{a[n]-2a[n-1] == 3^\wedge n,\ a[1] == 2\}}$。 因為在 Mathematica 中 ${\tt =}$ 是用來設定變數的值, 因此方程式中的等號必須使用兩個。

${\tt RSolve}$ 可以解任意階常係數線性遞迴方程。以下用兩個例子來說明它的使用方式。

例 A.1: (二階線性齊次遞迴關係) 設 $a_{n}+4a_{n-1}-21a_{n-2}=0$, $n\ge 2$, 利用 Mathematica 的 ${\tt RSolve} $求解 $a_{n}$ 的一般解。

解: ${In[1]:=}{RSolve[a[n] + 4a[n - 1] - 21a[n - 2] == 0, a[n],\ n]} \\ {Out[2]=}{a[n]\rightarrow \left( -7 \right)^n C[1] + 3^n C[2]}$ 因為沒有邊界條件, 所以在 ${\tt Out[1]}$ 中含有未定係數 ${\tt C[1]}$ 和 ${\tt C[2]}$, 因此 $a_n=c_1 (-7)^n+c_2 3^n$。$\Box$

${\tt RSolve} $亦可以解帶參數及邊界條件的遞迴方程式, 如下面例子。

例 A.1: (一階線性非齊次遞迴關係) 設 $a[0]=1$, $a_{n+1}=\alpha a[n]+\beta$, $n\ge 0$, 利用 Mathematica 的 ${\tt RSolve}$ 求解 $a_{n}$。

解: ${In[1]:=}{RSolve[\{a[n + 1] == \alpha\ a[n] + \beta ,\ a[0] == 0\},\ a[n],\ n]} \\ {Out[2]=}{a[n]\rightarrow {\frac{\left( -1 + {\alpha }^n \right) \beta }{-1 + \alpha }}}$ 因此 $a_n=\frac{(\alpha^n-1)\beta}{\alpha-1}$。$\Box$

參考文獻

---本文作者張福春任教國立中山大學應用數學系, 莊淨惠為國立中山大學應用數學系碩士班畢業生---