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


《點算的奧秘:齊次遞歸關係的解》中,筆者介紹了求解「常系數一元線性齊次遞歸關係」的方法,在本網頁筆者將介紹求解「常系數一元線性非齊次遞歸關係」的方法。在這裡首先重溫「非齊次遞歸關係」的定義。當我們把一個「遞歸關係」寫成標準形式,即把含有an、an−1 ...等的項統統移到等號左邊,並把其餘的項移到等號右邊後,如果在等號右邊的項不等於0,則該「遞歸關係」是「非齊次」的。我們把這個在等號右邊的非零項稱為「非齊次遞歸關係」的「非齊次部分」。

求解「非齊次遞歸關係」須應用到求解「齊次遞歸關係」的方法。具體地說,我們須先求解一個「相關齊次遞歸關係」(Associated Homogeneous Recurrence Relation),即我們暫時把等號右邊的項當作0,然後求這個「相關齊次遞歸關係」的「通解」gn。除了這個相關的「通解」外,我們還需要一個「特解」pn,即滿足「非齊次遞歸關係」的不含「任意常數」的解(註1)。要求得這個pn,我們要使用以下介紹的「未定系數法」(Method of Undetermined Coefficients)。

「未定系數法」乃基於以下假設:「非齊次遞歸關係」的「特解」與該「遞歸關係」的「非齊次部分」具有相同的形式,兩者僅在系數方面有差異。因此,假如給定「遞歸關係」的「非齊次部分」是「指數函數」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
 = 2An − 2A + 2B + n − 1
 = (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 

答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
 = 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
 = 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代入給定「遞歸關係」的等號左端:

 An2 + 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
 = −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
 = 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屬於同一類型的「指數函數」。

返回數學專題