常係數線性遞迴關係式 (下)

Posted on 10/08/2015 by ccjou

本文的閱讀等級：初級

考慮下列 k 階線性非齊次遞迴關係式 (linear nonhomogeneous recurrence relation)

a_n=d_1a_{n-1}+d_2a_{n-2}+\cdots+d_ka_{n-k}+F(n),~~n\ge k，

其中 d_1,\ldots,d_k 是常數，d_k\neq 0，F(n) 稱為控制項。如果移除 F(n)，

a_n=d_1a_{n-1}+d_2a_{n-2}+\cdots+d_ka_{n-k}

稱為關聯齊次遞迴關係式 (associated homogeneous recurrence relation)。令數列 \{a^{(p)}_n\} 為滿足非齊次遞迴關係式的一個特解 (particular solution)，數列 \{a^{(h)}_n\} 為滿足關聯齊次遞迴關係式的齊次解 (homogeneous solution)。非齊次遞迴關係式的任一解 (即通項) 可表示為 \{a^{(p)}_n+a^{(h)}_n\}，證明於下：因為 \{a^{(p)}_n\} 是一個特解，

\displaystyle a^{(p)}_n=d_1a^{(p)}_{n-1}+d_2a^{(p)}_{n-2}+\cdots+d_ka^{(p)}_{n-k}+F(n)。

假設 \{b_n\} 是任何一個非齊次遞迴關係式的解，即有

\displaystyle b_n=d_1b_{n-1}+d_2b_{n-2}+\cdots+d_kb_{n-k}+F(n)。

令上面兩式相減，

\displaystyle b_n-a^{(p)}_n=d_1(b_{n-1}-a^{(p)}_{n-1})+d_2(b_{n-2}-a^{(p)}_{n-2})+\cdots+d_k(b_{n-k}-a^{(p)}_{n-k})。

因此，\{b_n-a_n^{(p)}\} 滿足關聯齊次遞迴關係式，可得 b_n=a_n^{(p)}+a_n^{(h)}。本文討論非齊次遞迴關係式的控制項為 F(n)=q(n)s^n 的解法，其中 q(n) 是一個多項式，s 是一常數。

 
首先介紹如何以待定係數法 (method of undetermined coefficients) 求非齊次遞迴關係式的一個特解，下面用兩個例子說明求解過程。

 
例一：考慮

a_n=2a_{n-1}+3n，

初始值為 a_0=1。因為 F(n)=3n，我們猜測特解的形式為

a_n^{(p)}=\alpha_1 n+\alpha_0，

其中 \alpha_0 和 \alpha_1 是待決定的係數。將上式代入遞迴關係式，

\begin{aligned} \alpha_1 n+\alpha_0&=2(\alpha_1(n-1)+\alpha_0)+3n\\ &=(2\alpha_1+3)n+2(\alpha_0-\alpha_1), \end{aligned}

比較等號兩邊的多項式係數，\alpha_1=2\alpha_1+3 和 \alpha_0=2\alpha_0-2\alpha_1，解得 \alpha_1=-3 和 \alpha_0=-6，所以 a_n^{(p)}=-3n-6。寫出關聯齊次遞迴關係式 a_n=2a_{n-1}，特徵方程為 t=2，故齊次解為 a_n^{(h)}=c_12^n。合併以上結果，通項可表示為 a_n=a_n^{(p)}+a_n^{(h)}=-3n-6+c_1 2^n。代入初始條件，a_0=-6+c_1=1，可得 c_1=7。所以，

\displaystyle a_n=-3n-6+7\cdot 2^n,~~n\ge 0。

 
例二：考慮

a_n=a_{n-1}+6a_{n-2}+5^n。

因為 F(n)=5^n，我們猜測特解的形式為

a_n^{(p)}=\alpha_1 5^n。

代入遞迴關係式，可得

\alpha_1 5^n=\alpha_15^{n-1}+6\alpha_15^{n-2}+5^n，

或 25\alpha_1=5\alpha_1+6\alpha_1+25，解得 \alpha_1=\frac{25}{14}，所以 a_n^{(p)}=\frac{25}{14}\cdot 5^n。寫出關聯齊次遞迴關係式 a_n=a_{n-1}+6a_{n-2}，由特徵方程 t^2=t+6 解出二根，3 和 -2，因此齊次解為 a_n^{(h)}=c_13^n+c_2(-2)^n。合併以上結果，通項可表示為

\displaystyle a_n=\frac{25}{14}\cdot 5^n+c_1 3^n+c_2(-2)^n，

其中 c_1 和 c_2 由初始條件 a_0 和 a_1 決定。

 
考慮一般情況，F(n)=q(n)s^n，其中 q(n) 是一個 r 次多項式。我們利用有限差分 (finite difference) 推導特解的形式。令 f(i)=q(n-i)。明顯地，f(i) 是 i 的 r 次多項式。使用下面的等式 (見“一個關於階乘的恆等式”)：對於所有的 n\ge 0，

\displaystyle \sum_{i=0}^{r+1}(-1)^i\binom{r+1}{i}f(i)=\sum_{i=0}^{r+1}(-1)^i\binom{r+1}{i}q(n-i)=0。

直白地說，r 次多項式 q(n) 的 r+1 階反向差分 (backward difference) 等於零[1]。上式等號兩邊乘以 s^n，推得 \{F(n)\} 滿足下列線性齊次遞迴關係式：

\displaystyle \sum_{i=0}^{r+1}\binom{r+1}{i}(-s)^iq(n-i)s^{n-i}=\sum_{i=0}^{r+1}\binom{r+1}{i}(-s)^iF(n-i)=0。

使用二項式定理 (見“二項式係數與組合問題”)，遞迴關係式的特徵方程為

\displaystyle \sum_{i=0}^{r+1}\binom{r+1}{i}(-s)^it^{r+1-i}=(t-s)^{r+1}=0。

更進一步，我們可以證明所求數列 \{a_n\} 滿足下列特徵方程所對應的齊次遞迴關係式：

\displaystyle (t^k-d_1t^{k-1}-d_2t^{k-2}-\cdots-d_k)(t-s)^{r+1}=0，

其中 t^k-d_1t^{k-1}-\cdots-d_k 是關聯齊次遞迴關係式的特徵多項式。為便利說明，考慮下例：

a_n=5a_{n-1}+F(n)，

其中 F(n)=q(n)s^n，q(n)=2n+1，r=1。寫出

\begin{aligned} a_n-5a_{n-1}&=F(n)\\ -2s(a_{n-1}-5a_{n-2})&=-2sF(n-1)\\ s^2(a_{n-2}-5a_{n-3})&=s^2F(n-2), \end{aligned}

加總上式，等號右邊為

\displaystyle F(n)-2sF(n-1)+s^2F(n-2)=0。

數列 \{a_n\} 滿足齊次遞迴關係式

\displaystyle a_n-5a_{n-1}-2s(a_{n-1}-5a_{n-2})+s^2(a_{n-2}-5a_{n-3})=0，

不難確認上式的特徵方程為 t^2(t-5)-2st(t-5)+s^2(t-5)=(t-5)(t-s)^2=0。根據特徵方程，我們可導出 a_n 的表達式。若 s\neq 5，通項為 (見“常係數線性遞迴關係式 (中)”)

a_n=\alpha_05^n+(\alpha_1+\alpha_2n)s^n；

若 s=5，

a_n=(\alpha_0+\alpha_1n+\alpha_2n^2)s^n。

上兩式中，齊次解是 a_n^{(h)}=\alpha_05^n，特解可記為 a_n^{(p)}=n^m(\alpha_1+\alpha_2n)s^n，其中 m 是 s 於特徵方程 t=5 的重數。如果 s 不是特徵多項式 t-5 的一根，即 s\neq 5，則 m=0。

 
一旦得知特解的形式即可運用待定係數法解出組合係數。上例中，假設 s=3，將 a_n^{(p)}=(\alpha_1+\alpha_2n)3^n 代入遞迴關係式，

\displaystyle (\alpha_1+\alpha_2n)3^n=5(\alpha_1+\alpha_2(n-1))3^{n-1}+(2n+1)3^n。

上式通除 3^{n-1}，化簡並比較等號兩邊的係數，

\displaystyle\begin{aligned} 3\alpha_1&=5\alpha_1-5\alpha_2+3\\ 3\alpha_2&=5\alpha_2+6, \end{aligned}

解得 \alpha_1=-9 和 \alpha_2=-3。因此，通項為

\displaystyle a_n=-(9+3n)3^n+\alpha_05^n，

其中 \alpha_0 由初始條件 a_0 決定。

 
最後將上文結果整理於下。給定一 k 階非齊次遞迴關係式

a_n=d_1a_{n-1}+d_2a_{n-2}+\cdots+d_ka_{n-k}+F(n),~~n\ge k，

其中 d_1,\ldots,d_k 是常數，d_k\neq 0，F(n)=q(n)s^n，q(n) 是一 r 次多項式。通項可表示為 a_n=a_n^{(p)}+a_n^{(h)}，存在一特解形式如下：

\displaystyle a_n^{(p)}=n^mp(n)s^n，

其中 p(n) 是一個次數不大於 r 的多項式，m 是 s 於關聯齊次遞迴關係式的特徵方程

t^k=d_1t^{k-1}+d_2t^{k-2}+\cdots+d_k

的重數。使用待定係數法，將 a_n^{(p)} 代入非齊次遞迴關係式可解出 p(n) 的係數。從關聯齊次遞迴關係式可得齊次解 a_n^{(h)} 的表達式，組合係數由初始條件 a_0,a_1,\ldots,a_{k-1} 決定。

 
註解
[1] Wolfram MathWorld：Backward Difference

Advertisement
This entry was posted in 特別主題 and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out /  Change )

Cancel

Connecting to %s