34104 線性遞迴關係之求解(下)

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。

★ 終極密碼為0到100之間 ★
您共有六次機會

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. 共軛複根

定理 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$

參考文獻

Brualdi, R. A., Introductory Combinatorics, 4th edition. Prentice Hall, New York, 2005. D'Angelo, J. P. and West, D. B., Mathematical Thinking: Problem-Solving and Proofs, 2nd edition. Prentice Hall, New York, 1999. Graham, R. L., Knuth, D. E. and Patashnik, O., Concrete Mathematics, 2nd edition. Addison Wesley, New York, 1994. Grimaldi, R. P., Recurrence relations. In Handbook of Discrete and Combinatorial Mathematics by Rosen, K. H. (Editor). Boca Raton, Florida: CRC, 1999. Kelley, W. G. and Peterson, A. C., Difference Equations: An Introduction with Applications, 2nd edition. Academic Press, New York, 2000. Loy, J., Fibonacci Numbers. 2007 Jun 20. Available from: http://www.jimloy.com/algebra/fibo.htm Sedgewick, R. and Flajolet, P., An Introduction to the Analysis of Algorithms. Addison-Wesley, New York, 1996. Sloane, N. J. A., The On-Line Encyclopedia of Integer Sequences. 2007 Jun 20. Available from:http://www.research.att.com/~njas/sequences/ Spiegel, M. R., Schaum's Outline of Calculus of Finite Differences and Difference Equations. McGraw-Hill, New York, 1971. Stanley, R. P., Enumerative Combinatorics, Vol. 2. Cambridge University Press, New York, 1999. Tucker, A., Applied Combinatorics, 4th edition. John Wiley & Sons, Inc., New York, 2002. Wolfram, S., The Mathematica Book, 5th edition. Champaign, IL: Wolfram Media, 2003. 游森棚, 談談九十五學年度高中數學新課程大綱的 "遞迴"。2008 February 25。 Available from: http://umath.nuk.edu.tw/~senpengeu/HighSchool/recurr.pdf

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

文章 推薦

電腦模擬與賭局

假設玩家A和B進行賭博。玩家A有m元,玩家B則有n元,然後擲1個公正的硬幣。如果出現正面就算玩家A贏,反面就算玩家B贏。每次賭注都是1元,如果A贏則A變m+1元、而B變n−1元,並稱此為1回合。雙方不斷地進行賭博,直到某方的錢歸零為止。在這個賭博中,有以下兩個問題:(1)玩家A和玩家B贏的機率各是多少?(2)每投1次硬幣決勝負,都稱為1回合,平均要幾回合,賭局才會結束(某方錢輸光)?....閱讀更多