發刊日期 |
2010年3月
|
||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
標題 | 線性遞迴關係之求解(下) |
||||||||||||||||
作者 | |||||||||||||||||
關鍵字 | |||||||||||||||||
檔案下載 | |||||||||||||||||
全文 |
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)$。
解:
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$, 即可求得此遞迴關係式。 綜合以上的例子, 對於一般的常係數 $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. 齊次解型式
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}
因此, 當 $f(n)$ 是二次多項式時, (\ref{eqnB:33559}) 的特解可以這樣來確定:
例 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. $ 證明: 相同地, 在此舉二階常係數線性非齊次遞迴方程式來說明:
因此, 當 $f(n)=c\lambda^n$時, (\ref{eqnB:33559}) 的特解可以這樣來確定:
由以上的方法可發現當 $\lambda$ 是特徵方程式的單根或重根時, $d_0$, $d_1$會被消去, 所以可以不用設, 故也可用以下方法求解
因此, 當 $f(n)=c\lambda^n$ 時, (\ref{eqnB:33559}) 的特解可以這樣來確定:
例 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$ 為所求的序列個數, 分成兩種情況來討論:
由以上討論知 $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 的情況。
由於 $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}) 的特解為:
例 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)$ 為此三種型式的線性組合。 綜合以上求解非齊次遞迴關係式可分為下列的五個步驟:
註: 若 $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下列是一些不錯的題目, 也許讀者有興趣試試, 為了方便讀者, 我們也將答案列入。
A. 附錄: Mathematica: ${\tt RSolve}$Mathematica 5.0 (Wolfram 2003)是一個強大的數值、符號運算、繪圖整合系統, 具有高階程式語言能力的數學軟體。 它新增一個強大的內建命令 ${\tt RSolve}$, 可以解遞迴方程。 在 5.0以前的版本中, ${\tt RSolve}$ 是置放於附加標準程式庫資料夾 ${\tt DiscreteMath}$ 中, 使用前必須將它先行載入, 載入格式: ${\tt \lt \lt DiscreteMath`RSolve`}$。${\tt RSolve}$ 的語法如下:
或
其中 ${\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$ 參考文獻---本文作者張福春任教國立中山大學應用數學系, 莊淨惠為國立中山大學應用數學系碩士班畢業生--- |