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

本文的閱讀等級:初級

考慮下列 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 0F(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_1c_2 由初始條件 a_0a_1 決定。

 
考慮一般情況,F(n)=q(n)s^n,其中 q(n) 是一個 r 次多項式。我們利用有限差分 (finite difference) 推導特解的形式。令 f(i)=q(n-i)。明顯地,f(i)ir 次多項式。使用下面的等式 (見“一個關於階乘的恆等式”):對於所有的 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^nq(n)=2n+1r=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,其中 ms 於特徵方程 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 0F(n)=q(n)s^nq(n) 是一 r 次多項式。通項可表示為 a_n=a_n^{(p)}+a_n^{(h)},存在一特解形式如下:

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

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

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

Advertisements
本篇發表於 特別主題 並標籤為 , , 。將永久鏈結加入書籤。

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s