點算的奧秘:遞歸關係的母函數解題法


在前面幾節,筆者介紹了求解「遞歸關係」的「標準」方法,這種方法跟求解「微分方程」的「標準」方法非常相似。不過,正如「微分方程」有其他解題方法(例如「拉普拉斯變換」Laplace Transform),「遞歸關係」也有一種類似「積分變換」(Integral Transform)的解題方法,那就是「母函數」方法。

筆者在以前曾指出,「母函數」是一種記載某些數值信息的方法。現設我們有一個「遞歸關係」,各項的值為a0、a1、a2 ... an ...,那麼我們可以把這些值寫成以下這個「母函數」:

a0 + a1x + a2x2 + ... anxn + ... = Σ0 ≤ n < ∞ anxn = f(x)     (1)

如果給定某一「遞歸關係」,我們能求得相應的f(x),這便等於求得該「遞歸關係」的解。以下讓我們看如何利用某些代數方法求這個f(x)。這些代數方法需要用到以下的公式:

Σ0 ≤ n < ∞ xn = 1 / (1 − x)     (2)

Σ1 ≤ n < ∞ nxn−1 = 1 / (1 − x)2     (3)

上面的公式(2)其實就是《點算的奧秘:普通母函數》中的公式(5)。學過「微積分」的讀者應容易看到公式(3)是公式(2)的「導數」(Derivative)。如果我們繼續對公式(3)求導,還可得到更多公式,但由於牽涉的計算將越來越繁複,所以這裡只提供這兩條公式。

由於「母函數」解題法的程序頗為繁複,筆者用以下例題說明這種解題法。

例題1:求解以下「遞歸關係」:

an = 2an−1 + n − 1,若n > 0
a0 = 0

答1:本題就是《點算的奧秘:非齊次遞歸關係的解》中的例題1和2 (註1)。這是一個「非齊次遞歸關係」,根據前數節的介紹,求解「齊次遞歸關係」與「非齊次遞歸關係」須使用不同的方法。但若用「母函數」方法求解,則無須區分這兩種「遞歸關係」。為了把上式轉化為「母函數」形式,我們首先對上式各項乘以xn,然後對x求和(下限為1,因為給定的「遞歸關係」有一個限制條件n > 0),於是得到

Σ1 ≤ n < ∞ anxn = Σ1 ≤ n < ∞ 2an−1xn + Σ1 ≤ n < ∞ nxn − Σ1 ≤ n < ∞ xn

為了方便以下的計算,我們首先對上式作一些調整:

Σ1 ≤ n < ∞ anxn = 2x Σ1 ≤ n < ∞ an−1xn−1 + x Σ1 ≤ n < ∞ nxn−1 − Σ1 ≤ n < ∞ xn

接著我們利用關係式m = n − 1對上式中等號右端第一項的「求和變項」進行變換,得到下式:

Σ1 ≤ n < ∞ anxn = 2x Σ0 ≤ m < ∞ amxm + x Σ1 ≤ n < ∞ nxn−1 − Σ1 ≤ n < ∞ xn

接著我們把上式中某些項的下限改為0 (但這樣做實際等於在原來的項上加上某些新的項,我們須減去這些多出的項。舉例說,如果我們把Σ1 ≤ n < ∞ anxn改為Σ0 ≤ n < ∞ anxn,這實際等於在原來的Σ1 ≤ n < ∞ anxn上加上a0,因此我們須在更改下限後減去這個a0),得到

Σ0 ≤ n < ∞ anxn − a0 = 2x Σ0 ≤ m < ∞ amxm + x Σ1 ≤ n < ∞ nxn−1 − (Σ0 ≤ n < ∞ xn − 1)

至此,我們可以利用上面的公式(1)、(2)、(3)和本題給定的「初值」(註2)把上式改寫為

f(x) = 2xf(x) + x / (1 − x)2 − 1 / (1 − x) + 1

對上式求解f(x),容易求得

f(x)= x / [(1 − x)2(1 − 2x)] − 1 / [(1 − x)(1 − 2x)] + 1 / (1 − 2x)
 = [x − (1 − x) + (1 − x)2] / [(1 − x)2(1 − 2x)]
 = x2 / [(1 − x)2(1 − 2x)]     (4)

上式不是我們要求的最終答案,因為它涉及一個複雜的分式(其分母可被因式分解為幾個項)。因此我們要設法把上式等號右端的分式分解為「部分分式」(Partial Fraction),即由若干個其分母為「不可約項」Irreducible (即不能被因式分解的項)的分式之和。根據有關「部分分式」的理論,由於上式等號右端的分母包含兩個「因式」(Factor)-(1 − x)2和1 − 2x,其中(1 − x)2為二次項,所以我們假設

x2 / [(1 − x)2(1 − 2x)] = A / (1 − x) + B / (1 − x)2 + C / (1 − 2x) (註3)

其中A、B、C為待求的常數。對上式等號兩端同時乘以(1 − x)2(1 − 2x),便得到

x2 = A(1 − x)(1 − 2x) + B(1 − 2x) + C(1 − x)2

接著我們固然可以展開上式等號右端,得到三條「聯立方程」,並從而解出A、B和C,但較簡便的方法是把一些常數代入上式中的x,從而化簡上式。例如把x = 1代入上式,便可得到

1 = −B

其次把x = 1 / 2代入上式,便可得到

1 / 4 = C / 4

最後把x = 0代入上式,便可得到

0 = A + B + C

這樣我們同樣可得到三條「聯立方程」,但那是非常簡單的「聯立方程」。容易看到,這三條「聯立方程」的解為A = 0,B = −1,C = 1。至此我們成功求得

x2 / [(1 − x)2(1 − 2x)] = −1 / (1 − x)2 + 1 / (1 − 2x)

把以上結果代入上面(4),便得到

f(x) = 1 / (1 − 2x) − 1 / (1 − x)2

最後我們再次運用公式(1)、(2)、(3)把上式改寫為

Σ0 ≤ n < ∞ anxn= Σ0 ≤ n < ∞ (2x)n − Σ1 ≤ n < ∞ nxn−1
 = Σ0 ≤ n < ∞ 2nxn − Σ0 ≤ n < ∞ (n + 1)xn
 = Σ0 ≤ n < ∞ [2n − n − 1]xn

請注意在上面第二行我們利用關係式m = n − 1對等號右端的第二項的「求和變項」進行了變換,然後再把m改寫成n。

最後,比較上面等號兩端,我們看到本題答案為

an = 2n − n − 1

以上的答案與《點算的奧秘:非齊次遞歸關係的解》中例題2的答案完全相同。□

從上題的解答可見,用「母函數」來求解「遞歸關係」,無需區分「齊次遞歸關係」與「非齊次遞歸關係」,也無需區分求「通解」與「特解」的步驟,這是「母函數」解題法的優點。不過其缺點是,須對「母函數」進行各種變換(例如變換其「求和變項」、分解為部分分式、適當地利用像(2)和(3)那樣的公式等),有時可能涉及頗繁複的計算。

接著讓我們看另一個例題。

例題2:求解以下「遞歸關係」:

an = 2an−1 + 3n−1 − 2n−1,若n > 0
a0 = 0 

答2:本題就是《點算的奧秘:非齊次遞歸關係的解》中的例題3。我們首先對上式各項乘以xn,然後對x求和(下限為1),於是得到

Σ1 ≤ n < ∞ anxn = Σ1 ≤ n < ∞ 2an−1xn + Σ1 ≤ n < ∞ 3n−1xn − Σ1 ≤ n < ∞ 2n−1xn

接著對上式進行各種變換:

Σ1 ≤ n < ∞ anxn= 2x Σ1 ≤ n < ∞ an−1xn−1 + x Σ1 ≤ n < ∞ 3n−1xn−1 − x Σ1 ≤ n < ∞ 2n−1xn−1
 = 2x Σ0 ≤ n < ∞ anxn + x Σ0 ≤ n < ∞ 3nxn − x Σ0 ≤ n < ∞ 2nxn
Σ0 ≤ n < ∞ anxn − a0= 2x Σ0 ≤ n < ∞ anxn + x Σ0 ≤ n < ∞ (3x)n − x Σ0 ≤ n < ∞ (2x)n
f(x)= 2xf(x) + x / (1 − 3x) − x / (1 − 2x)
f(x)= x / [(1 − 3x)(1 − 2x)] − x / (1 − 2x)2
 = x2 / [(1 − 3x)(1 − 2x)2]     (4)

接著我們要把上式等號右端的分式分解為「部分分式」。我們假設

x2 / [(1 − 3x)(1 − 2x)2] = A / (1 − 3x) + B / (1 − 2x) + C / (1 − 2x)2

對上式等號兩端同時乘以(1 − 3x)(1 − 2x)2,得到

x2 = A(1 − 2x)2 + B(1 − 3x)(1 − 2x) + C(1 − 3x)

現在,把x = 1 / 2代入上式,便可得到

1 / 4 = −C / 2

其次,把x = 1 / 3代入上式,得到

1 / 9 = A / 9

最後,把x = 0代入上式,得到

0 = A + B + C

利用上面三條「聯立方程」,容易求得

A = 1,B = −1 / 2,C = −1 / 2

把以上結果代入(4),然後再進行一些變換:

f(x)= 1 / (1 − 3x) − 1 / 2(1 − 2x) − 1 / 2(1 − 2x)2
Σ0 ≤ n < ∞ anxn= Σ0 ≤ n < ∞ (3x)n − Σ0 ≤ n < ∞ 1 /2 × (2x)n − Σ1 ≤ n < ∞ 1 /2 × n(2x)n−1
 = Σ0 ≤ n < ∞ (3x)n − Σ0 ≤ n < ∞ 1 /2 × (2x)n − Σ0 ≤ n < ∞ 1 /2 × (n + 1)(2x)n
 = Σ0 ≤ n < ∞ 3nxn − Σ0 ≤ n < ∞ 2n−1xn − Σ0 ≤ n < ∞ (n + 1)2n−1xn
 = Σ0 ≤ n < ∞ [3n − 2n−1 − (n + 1)2n−1] xn
 = Σ0 ≤ n < ∞ [3n − 2n − n2n−1] xn

比較上面等號兩端,我們看到

an = 3n − 2n − n2n−1

上式跟《點算的奧秘:非齊次遞歸關係的解》中例題3的答案相符。□

以下讓我們看如何用「母函數」方法求解含複數解的「遞歸關係」。由於這類「遞歸關係」可能涉及繁複的計算,以下只舉一個簡單的例子。

例題3:求解以下「遞歸關係」,把答案表達為「三角函數」的形式,並驗證答案:

an = −an−2,若n > 1
a0 = 2,a1 = −2

答3:首先對上式各項乘以xn,然後對x求和(下限為2,因為給定的「遞歸關係」的限制條件為n > 1):

Σ2 ≤ n < ∞ anxn = −Σ2 ≤ n < ∞ an−2xn

接著對上式進行各種變換:

Σ2 ≤ n < ∞ anxn= −x2 Σ2 ≤ n < ∞ an−2xn−2
 = −x2 Σ0 ≤ n < ∞ anxn
Σ0 ≤ n < ∞ anxn − a0 − a1x= −x2 Σ0 ≤ n < ∞ anxn
f(x) − 2 + 2x= −x2f(x)
f(x)= (2 − 2x) / (1 + x2)     (5)

請注意在「實數域」下,1 + x2是「不可約項」,但在「複數域」下,1 + x2卻可以因式分解為(1 + ix)(1 − ix) (註4)。因此我們可以嘗試把上式等號右端的分式分解為「部分分式」,即假設

(2 − 2x) / (1 + x2) = A / (1 + ix) + B / (1 − ix)

經過一番計算,容易求得解得A = 1 − i,B = 1 + i。把此一結果代入(5),然後再進行一些變換:

f(x)= (1 − i) / (1 + ix) + (1 + i) / (1 − ix)
Σ0 ≤ n < ∞ anxn= (1 − i) Σ0 ≤ n < ∞ (−ix)n + (1 + i) Σ0 ≤ n < ∞ (ix)n
 = Σ0 ≤ n < ∞ [(1 − i) × (−i)n + (1 + i) × in] xn

比較上面等號兩端,我們看到

an = (1 − i) × (−i)n + (1 + i) × in     (6)

可是上面不是「三角函數」的形式。不過,我們可以把上面4個「複數」改寫為「極坐標」形式:

1 ± i = √2 (cos45° ± i sin45°)
±i = cos90° ± i sin90°

另外,根據《點算的奧秘:含複數解的遞歸關係》中的定理1,

(±i)n = (cos90° ± i sin90°)n = cos90n° ± i sin90n°

把以上結果代入(6)然後展開乘積:

an= √2 (cos45° − i sin45°)(cos90n° − i sin90n°) + √2 (cos45° + i sin45°)(cos90n° + i sin90n°)
 = √2 [2 cos45° cos90n° − 2 sin45° sin90n°]
 = 2 (cos90n° − sin90n°)

上式就是本題要求的答案。當我們把n = 0、1、2、3依次代入上式時,便會得到

a0 = 2,a1 = −2,a2 = −2,a3 = 2

由於「三角函數」是「周期函數」(Periodic Function),當n = 4時,cos90n° = cos360° = cos0°,sin90n° = sin360° = sin0°,所以a4 = a0。由此可知,an的值不斷以2、−2、−2、2的次序循環,由此我們可以總結出

a4k = 2,a4k+1 = −2,a4k+2 = −2,a4k+3 = 2,其中k為非負整數

容易看到,以上序列符合給定的「遞歸關係」,所以上面求得的答案是正確的。□

從上題的解答我們看到一個有趣的現象,雖然上題最初求得的答案(6)表面上含有「虛數單位」i,但在把(6)中的複數改寫為「極坐標」形式後,含有i的部分最終互相抵消了,因此上題的最終答案不含任何i。這是完全合理的,因為既然給定的「遞歸關係」和「初值」全為「實數」,那麼本題的解答也應只含有實數。

註1:請注意《點算的奧秘:非齊次遞歸關係的解》中的例題2本來是把本「遞歸關係」的第一項定為a1,本題則把它改為a0,這是為了方便在以下的計算中應用公式(1)。請注意根據上述例題2的「初值」a1 = 0和給定的「遞歸關係」,我們可以「倒推」出a0 = 0。

註2:假如題目沒有給定「初值」,那麼上式中的a0將保持為一個變數,並且在最後計算結果中將仍存在這個變數,這個變數其實就是以前介紹的「遞歸關係」的「通解」中的「任意常數」。

註3:一般地,若某分式的分母含有某個「因式」(1 − kx)n,在分解為「部分分式」時,我們須假設「部分分式」包含以下這些項:A1 / (1 − kx) + A2 / (1 − kx)2 + ... An / (1 − kx)n

註4:一般地,若「二次方程」Ax2 + Bx + C = 0有「共軛複數」解a + bi和a − bi,則Ax2 + Bx + C可以因式分解為(x − a − bi)(x − a + bi)。因此1 + x2 = (x − i)(x + i) = (−i + x)(i + x) = −i(1 + ix) × i(1 − ix) = (1 + ix)(1 − ix)。

返回數學專題