點算的奧秘：非齊次遞歸關係的解

除了這個相關的「通解」外，我們還需要一個「特解」pn，即滿足「非齊次遞歸關係」的不含「任意常數」的解(註1)。

要求得這個pn，我們要使用以下介紹的「未定系數 ... 點算的奧秘：非齊次遞歸關係的解 在《點算的奧秘：齊次遞歸關係的解》中，筆者介紹了求解「常系數一元線性齊次遞歸關係」的方法，在本網頁筆者將介紹求解「常系數一元線性非齊次遞歸關係」的方法。

在這裡首先重溫「非齊次遞歸關係」的定義。

當我們把一個「遞歸關係」寫成標準形式，即把含有an、an−1...等的項統統移到等號左邊，並把其餘的項移到等號右邊後，如果在等號右邊的項不等於0，則該「遞歸關係」是「非齊次」的。

我們把這個在等號右邊的非零項稱為「非齊次遞歸關係」的「非齊次部分」。

求解「非齊次遞歸關係」須應用到求解「齊次遞歸關係」的方法。

具體地說，我們須先求解一個「相關齊次遞歸關係」(AssociatedHomogeneousRecurrenceRelation)，即我們暫時把等號右邊的項當作0，然後求這個「相關齊次遞歸關係」的「通解」gn。

除了這個相關的「通解」外，我們還需要一個「特解」pn，即滿足「非齊次遞歸關係」的不含「任意常數」的解(註1)。

要求得這個pn，我們要使用以下介紹的「未定系數法」(MethodofUndeterminedCoefficients)。

「未定系數法」乃基於以下假設：「非齊次遞歸關係」的「特解」與該「遞歸關係」的「非齊次部分」具有相同的形式，兩者僅在系數方面有差異。

因此，假如給定「遞歸關係」的「非齊次部分」是「指數函數」3×2n，我們便假設pn也具有相同的形式，即pn=A×2n；假如給定「遞歸關係」的「非齊次部分」是「3階多項式」n3−1，我們便假設該「遞歸關係」的「特解」也具有相同的形式，即pn=An3+Bn2+Cn+D(註2)。

假如給定「遞歸關係」的「非齊次部分」具有較複雜的形式(例如混合了「指數函數」和「多項式」)，則pn亦要具有同類型的複雜形式，現把這些情況總結成下表： 表1 類型「遞歸關係」的「非齊次部分」pn的形式 指數函數3×2nA×2n 多項式n3−1An3+Bn2+Cn+D 混合指數函數3×2n−5nA×2n+B×5n 指數函數+多項式3×2n+6n2−3A×2n+Bn2+Cn+D 在上表中，A、B、C、D是未定的系數，當我們把上述含有未定系數的「特解」代入給定的「遞歸關係」後，便可解出這些系數的值。

筆者用以下例題說明如何運用「未定系數法」。

例題1：試求以下「遞歸關係」的「特解」： an=2an−1+n−1 答1：本題的「遞歸關係」就是《點算的奧秘：點算問題的遞歸關係》中例題3的「遞歸關係」。

首先把上式改寫成標準形式： an−2an−1=n−1 由於上式的「非齊次部分」是「1階多項式」n−1，根據表1，我們假設pn=An+B。

接著我們把這個pn代入上面的「遞歸關係」，並嘗試求出系數A和B： An+B=2[A(n−1)+B]+n−1 &nbsp=2An−2A+2B+n−1 &nbsp=(2A+1)n−2A+2B−1 比較上面等號兩端的一次項和常數項，我們得到以下的聯立方程： A=2A+1 B=−2A+2B−1 容易求得上述聯立方程的解為A=−1，B=−1。

因此本題的「特解」為 pn=−n−1□ 利用「未定系數法」求得「特解」pn後，我們便可以把pn加上前述「相關齊次遞歸關係」的「通解」gn，這樣便得到「非齊次遞歸關係」的「通解」，即 an=gn+pn 請注意上述「通解」須符合以下一般結構規定：gn與pn的各項應是「線性無關」的。

由於上述「通解」含有若干個「任意常數」，如果我們把給定的「初值」代入上述「通解」，便可求出這些「任意常數」的值，從而得到滿足給定「初值」的「特解」。

例題2：承接例題1，假設該題的「遞歸關係」的「初值」為 a1=0 試求解上述「遞歸關係」，並求a4的值。

答2：本題的「相關齊次遞歸關係」為 an−2an−1=0 上式的「輔助方程」為 x−2=0 由於上述方程只有一個「實根」2，我們求得本題的「相關齊次遞歸關係」的「通解」為 gn=C×2n 把上面的gn與在例題1求得的pn加起來，便得到本題的「通解」為 an=C×2n−n−1 把給定的「初值」代入上式，便得到 a1=C×21−1−1 即，2C−2=0 容易求得C=1。

因此滿足本題給定「初值」的「特解」為 an=2n−n−1 把n=4代入上式，我們便求得 a4=24−4−1=11 上述答案與《點算的奧秘：點算問題的遞歸關係》例題3的答案完全吻合。

□ 當「非齊次部分」的某部分與gn的某部分具有相同的形式時，假如我們仍然沿用上面表1所示pn的形式，這就會使gn與pn在某部分重合，因而不符合「線性無關」的要求，違反有關遞歸關係「通解」的結構規定。

為補救此一問題，我們可以仿照上節處理「重根」的做法，對pn中與gn重合的部分乘以n。

筆者用以下例題說明上述解題方法。

例題3：求解以下「遞歸關係」並求a4的值： an=2an−1+3n−1−2n−1，若n>1 a1=0&nbsp 答3：本題的「遞歸關係」就是《點算的奧秘：點算問題的遞歸關係》中例題4的「遞歸關係」。

首先把上述「遞歸關係」改寫成標準形式： an−2an−1=3n−1−2n−1 本題的「相關齊次遞歸關係」的「輔助方程」為 x−2=0 因此本題的「相關齊次遞歸關係」的「通解」為 gn=C×2n 接著求pn。

由於本題的「非齊次部分」為3n−1−2n−1，本來根據表1， pn=A×3n+B×2n(註3) 但這個pn的一部分(B×2n)與上述的gn具有相同的形式，pn與gn並不符合「線性無關」的要求。

因此我們要對pn中與gn重合的部分乘以n，從而得到以下經修訂的pn(讀者可自行驗證，如果不對pn作出如下修訂，我們將無法解出A和B)： pn=A×3n+Bn×2n 把上述pn代入給定的「遞歸關係」： A3n+Bn2n=2[A3n−1+B(n−1)2n−1]+3n−1−2n−1 3A(3n−1)+2Bn(2n−1)=(2A+1)3n−1+(−2B−1)2n−1+2Bn(2n−1) 3A(3n−1)=(2A+1)3n−1+(−2B−1)2n−1 比較上面等號兩端的3n−1項和2n−1項的系數，我們得到以下的聯立方程： 3A=2A+1 0=−2B−1 容易求得上述聯立方程的解為A=1，B=−1/2。

因此本題的「特解」為 pn=3n−n/2×2n &nbsp=3n−n×2n−1 把上面的gn和pn加起來，便得到本題的「通解」為 an=C×2n+3n−n×2n−1 接著把給定的「初值」代入上式，便得到 a1=C×20+30−0×20−1 即，C+1=0 容易求得C=−1。

因此滿足本題給定「初值」的「特解」為 an=−2n+3n−n×2n−1 把n=4代入上式，我們便求得 a4=−24+34−4×24−1=33 上述答案與《點算的奧秘：點算問題的遞歸關係》例題4的答案完全吻合。

□ 在某些複雜情況下，當「相關齊次遞歸關係」的「輔助方程」含有「重根」而pn的一部分又與gn具有相同形式時，對這一重合部分乘以n仍不足以使所得結果符合「線性無關」的要求。

在此情況下，我們要因應情況對重合部分乘以n的某個冪次項，使所得結果符合「線性無關」的要求。

試看以下例題。

例題4：求解下列「遞歸關係」，並且驗證本題答案與用下列「遞歸關係」求得的a3和a4的值相符： an−4an−1+5an−2−2an−3=2+2n，若n>2 a0=6，a1=20，a2=52 答4：由於給定的「遞歸關係」本身已是以標準形式出現，容易看到本題的「相關齊次遞歸關係」的「輔助方程」為 x3−4x2+5x−2=0 容易驗證可以把上式因式分解為 (x−1)2(x−2)=0 由於在上式的3個「實根」1、1、2中，1為「重根」，本題的「相關齊次遞歸關係」的「通解」為 gn=C×1n+Dn×1n+E×2n &nbsp=C+Dn+E×2n 接著求pn。

由於本題的「非齊次部分」為2+2n(即一個「0階多項式」加上一個「指數函數」)，本來根據表1， pn=A+B×2n 但這個pn中的兩個部分(A和B×2n)與上述gn中的兩個部分(C和E×2n)具有相同的形式，pn與gn並不符合「線性無關」的要求。

現在我們分別研究如何修訂pn的兩個部分，首先考慮A。

假如對此項乘以n，所得結果An仍然與gn中的Dn具有相同的形式。

假如對此項乘以n2，所得結果An2不再與gn中的任何部分重合。

其次考慮B×2n。

假如對此項乘以n，所得結果Bn×2n不與gn中的任何部分重合。

因此，經修訂的pn為 pn=An2+Bn×2n 把上述pn代入給定「遞歸關係」的等號左端： &nbspAn2+Bn2n−4[A(n−1)2+B(n−1)2n−1]+5[A(n−2)2+B(n−2)2n−2]−2[A(n−3)2+B(n−3)2n−3] =An2+Bn2n−4An2+8An−4A−4Bn2n−1+4B2n−1+5An2−20An+20A+5Bn2n−2−10B2n−2−2An2+12An−18A−2Bn2n−3+6B2n−3 =(1−4+5−2)An2+(8−20+12)An+(−4+20−18)A+(8−16+10−2)Bn2n−3+(16−20+6)B2n−3 =−2A+2B2n−3 上式應等於給定「遞歸關係」的等號右端： −2A+2B2n−3=2+8×2n−3 比較上式等號兩端，容易解得A=−1，B=4。

因此 pn=−n2+4n×2n &nbsp=−n2+n×2n+2 由此得到本題的「通解」為 an=C+Dn+E×2n−n2+n×2n+2 接著把給定的「初值」代入上式，便得到 a0=C+D×0+E×20−02+0×20+2 即，C+E=6 a1=C+D×1+E×21−12+1×21+2 即，C+D+2E+7=20 a2=C+D×2+E×22−22+2×22+2 即，C+2D+4E+28=52 容易求得上述聯立方程的解為C=2，D=3，E=4。

因此滿足本題給定「初值」的「特解」為 an=2+3n+4×2n−n2+n×2n+2 &nbsp=2+3n−n2+(1+n)×2n+2 為了驗證答案，我們首先用上式直接求a3和a4的值： a3=2+3×3−32+(1+3)×23+2=130 a4=2+3×4−42+(1+4)×24+2=318 接著我們又用上述「遞歸關係」和「初值」分別求a3和a4的值： a3=4a2−5a1+2a0+2+23=4×52−5×20+2×6+2+23=130 a4=4a3−5a2+2a1+2+24=4×130−5×52+2×20+2+24=318 上述兩種方法的計算結果相符。

□ 註1：「遞歸關係」的「特解」有兩種意義(其實「常微分方程」的「特解」也是如此)，它既可以指滿足某「遞歸關係」的給定「初值」的解，這種「特解」要透過把「初值」代入「遞歸關係」的「通解」來求得；亦可以指滿足某「非齊次遞歸關係」的不含「任意常數」的解，這種「特解」要使用下文將要介紹的「未定系數法」來求。

本網頁會同時用到這兩種意義的「特解」。

筆者不知為何數學界要用同一個名稱指稱兩個很不同的概念，這確實是一種很不理想的情況，有時會造成混亂。

但由於這兩種意義的「特解」在數學界中沿用已久，本網頁惟有依循數學界的習慣，並在此提醒讀者小心分辨這兩種意義。

註2：請注意我們在這裡是把「3階多項式」n3−1看成1n3+0n2+0n+(−1)。

註3：雖然本題「非齊次部分」的冪次是n−1，但為方便比較，應把pn的冪次寫成n。

事實上，由於3n=3×3n−1，3n與3n−1屬於同一類型的「指數函數」。

返回數學專題