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


《點算的奧秘:點算問題的遞歸關係》中,筆者介紹了把某些點算問題 表達為「遞歸關係」的方法。這種方法的優點是,無論點算問題多麼複雜,只要我們利用有關「遞歸關係」, 從初值a1開始一步一步計算a2、a3 ...,總能求得我們要求的某個 an。但是這種方法的缺點就是,在求an的過程中,我們先要求得各個am的 值(m < n),而不能直接求an。假如n是一個較大的數字,這將涉及大量計算,因此不是一種有效率 的解題方法。即使我們利用電腦程式或「試算表」(Spreadsheet)替我們代勞,這仍然不是一個好的解題方法, 因為電腦程式或「試算表」只提供一個個數值結果,我們無法看到這些數值結果之間的聯繫。因此我們需要求 解「遞歸關係」的另一種方法,這種方法應能讓我們把各個an的值表達為一條由某些已知函數及數 學運算符組成的算式(或稱「封閉形式」Closed Form),把n代入這個「封閉形式」,我們便可以直接求得 an的值。

求解上述「封閉形式」的最直接方法是根據給定的「遞歸關係」找出an與an−1 之間的關係,然後又找出an與an−2之間的關係,這樣逐步回溯,嘗試從中總結 出一些規律。筆者使用以下例子說明如何運用這種求解方法。

例題1:求解以下「遞歸關係」,並驗證答案:

an = an−1 + n,若n > 1
a1 = 1 

答1:根據上述「遞歸關係」,我們有

an = an−1 + n

現在,把上式中的n換成n − 1,便得到an−1 = an−2 + n − 1。把此式代入上式中的an−1,便得到an與an−2之 間的關係:

an= an−2 + n − 1 + n
 = an−2 + 2n − 1

接著我們又可以把給定「遞歸關係」中的n換成n − 2,求得某一關係式,並代入上式中的 an−2,便得到an與an−3之間的關係。我們繼續進行上述的運 算,直至看到某些規律為止。現把有關計算列於下面:

an= an−2 + 2n − 1
 = an−3 + n − 2 + 2n − 1
 = an−3 + 3n − (1 + 2)
 = an−4 + n − 3 + 3n − (1 + 2)
 = an−4 + 4n − (1 + 2 + 3)
 = an−5 + n − 4 + 4n − (1 + 2 + 3)
 = an−5 + 5n − (1 + 2 + 3 + 4)
 = ...
 = a1 + n(n − 1) − (1 + 2 + 3 + ... n − 2)

接著我們利用初值a1 = 1以及「算術級數」的公式1 + 2 + 3 + ... n = n(n + 1) / 2,把上式變 為

an= 1 + n(n − 1) − (n − 2)(n − 1) / 2
 = [2 + 2n(n − 1) − (n − 2)(n − 1)] / 2
 = (2 + 2n2 − 2n − n2 + 3n − 2) / 2
 = (n2 + n) / 2
 = n(n + 1) / 2 (註1)

為了驗證上述答案,我們可以把它代入給定的「遞歸關係」,看看等號兩邊是否相同。把上述答案代入給定「 遞歸關係」等號的左邊,得an = n(n + 1) / 2。接著把它代入給定「遞歸關係」等號的右邊,得

 an−1 + n
=(n − 1)(n) / 2 + n
=(n2 − n + 2n) / 2
=(n2 + n) / 2
=n(n + 1) / 2

由此可見等號左右兩邊相同。最後我們還要把n = 1代入上述答案,a1 = 1 × (1 + 1) / 2 = 1,與給定的初值相符。至此上述答案得以驗證。□

上題的解答顯示,前述的解題方法非常繁瑣,而且並不保證必能找到某種規律,因此我們需要一種較佳的解題 方法。以下筆者將介紹求解某些「遞歸關係」的方法,但這種方法只局限於求解某一類「遞歸關係」,具體地 說,就是「常系數一元線性遞歸關係」(Univariate Linear Recurrence Relation with Constant Coefficients),以下解釋一下這類「遞歸關係」的特點。首先,我們把「遞歸關係」寫成某種「標準」形式, 方法是把含有an、an−1 ...等的項統統放在等號左邊,並按其「下標」的大小 排好次序,並把其餘的項放在等號右邊。例如例題1中的「遞歸關係」便可以寫成以下標準形式:

an − an−1 = n

寫成標準形式後,等號左邊便有點類似一個「多項式」(Polynomial),其中每一項都有其「系數」,例如在上 式等號左邊,an和an−1項的「系數」分別是1和−1。假如等號左邊各項的 「系數」都是常數,我們便說有關「遞歸關係」是「常系數」的。

其次,我們可以把「遞歸關係」中的an看成函數a(n),a和n分別是這個函數的「因變量」 (Dependent Variable)和「自變量」(Independent Variable)。假如某「遞歸關係」中各項都只含有一個「自 變量」,我們便說這個「遞歸關係」是「一元」的。

最後,我們還要看標準形式「遞歸關係」等號左邊各項的「冪次」。假如各項的「冪次」均為1,我們便說這個 「遞歸關係」是「線性」的。請注意以下各項的「冪次」均不為1:(an)3、 anan−1、1 / an(因為這項可改寫為 (an)−1)。

除了上述概念外,我們還需要其餘兩個概念:「遞歸關係」的「階」和「齊次性」。一個「遞歸關係」的 「階」(Order)是指該「遞歸關係」在寫成標準形式後,各項下標最大值與最小值之差。舉例說,在「遞 歸關係」an + 6an−1 − 2an−3 = 0中,各項下標的最 大值為n,最小值為n − 3,所以這個「遞歸關係」的「階」為n − (n − 3) = 3。

在把「遞歸關係」寫成標準形式後,假如等號右邊等於0,我們便說該「遞歸關係」是「齊次」 (Homogeneous)的,否則便是「非齊次」(Non-homogeneous)的。例如例題1的「遞歸關係」就是「非 齊次」的。以下筆者將介紹求解「齊次遞歸關係」的方法,以下的討論將著重求解方法,不會涉及理論問題, 例如這些求解方法的背後原理,以及「解的存在性和唯一性」(Existence and Uniqueness of Solution)問題 。對這些理論問題感興趣的讀者,請參考有關書籍。至於「非齊次遞歸關係」的解題方法,將留待下節介紹。

學過「微分方程」的讀者應能發現,上述有關「遞歸關係」的分類法跟「常微分方程」(Ordinary Differential Equation)的分類法非常相似。事實上,我們可以把「遞歸關係」看成一種離散的「微分方程」 (在某些情況下,「遞歸關係」又可稱為「差分方程」Difference Equation),因此兩者的解也具有相同的結構 。具體地說,求解「齊次遞歸關係」須分兩個步驟進行。在第一個步驟中,我們先求「遞歸關係」的「通 解」(General Solution)。在第二個步驟中,我們再求「遞歸關係」的「特解」(Particular Solution)。

求「通解」的方法要借助「遞歸關係」的「輔助方程」(Auxiliary Equation)。當我們把「遞歸關係 」寫成標準形式後,便可以寫出其「輔助方程」。假設「遞歸關係」的標準形式為

c0an + c1an−1 + c2an−2 + ... cm−1an−m+1 + cman−m = 0 (註2)

這裡c0、c1 ... cm為「遞歸關係」中各項的「系數」,m為「遞歸關係」 的「階」(請注意m等於上式中各項下標最大值n與最小值n−m之差)。那麼上述「遞歸關係」的「輔助方程 」為

c0xm + c1xm−1 + c2xm−2 + ... cm−1x + cm = 0

由此可見,「遞歸關係」的「輔助方程」實際是一條「多項式方程」,這條方程的「階」(Degree)(即最高次項 的冪次)等於「遞歸關係」的「階」m。根據「代數學基本定理」(Fundamental Theorem of Algebra),一條m階 「多項式方程」應有m個「根」(「重根」和「複根」也計算在內),我們可以運用代數學的方法或數值方法求這 m個根。這m個根的分佈有以下三種可能性:(1)全部m個根均為各不相同的「實根」(Distinct Real Roots); (2)全部m個根均為「實根」,但有部分根為「重根」(Repeated Root);(3)全部或部分根為「複根」(Complex Root)。在不同情況下,「遞歸關係」的「通解」各有不同的形式。在本節筆者將只介紹在上述情況(1)和(2)下 「遞歸關係」的「通解」,情況(3)將留待以後再介紹。

假如「輔助方程」有m個各不相同的「實根」R1、R2 ... Rm,則「遞歸關 係」的「通解」為

an = C1 × R1n + C2 × R2n + ... Cm × Rmn (註3)     (1)

在上式中,R1n、R2n ... Rmn為m個 「線性無關」(Linearly Independent)的函數(註4),C1、C2 ... Cm則為 m個「任意常數」(Arbitrary Constant)。在一般情況下,一個m階「齊次遞歸關係」的「通解」須符合以下結 構規定:即應由m個「線性無關」函數連同m個「任意常數」組成。「任意常數」的存在告訴我們,「遞歸關係」 的「通解」並不只代表一個解,而是無限個解。只要我們把m個實數代入C1 ... Cm, 便可得到一個解。筆者用以下例題說明上述解題方法。

例題2:試求以下「遞歸關係」的「通解」,並驗證答案:

an = 4an−1 − an−2

答2:上式就是《點算的奧秘:點算問題的遞歸關係》中例題2 的「遞歸關係」。由於本題只需求「通解」,所以我們無需理會上述「遞歸關係」的「初值」。首先把上式改 寫成標準形式:

an − 4an−1 + an−2 = 0     (2)

由於上式是二階「遞歸關係」,其「輔助方程」為

x2 − 4x + 1 = 0

利用求解二次方程的公式,容易求得上式的兩個「實根」為2 + √3和2 − √3。因此本題的 「通解」為

an = C1 × (2 + √3)n + C2 × (2 − √3)n

接著讓我們驗證上述答案,方法是把上式代入上面的標準形式(2),看看所得結果是否等於0:

 C1(2 + √3)n + C2(2 − √3)n − 4C1(2 + √3)n−1 − 4C2(2 − √3)n−1 + C1(2 + √3)n−2 + C2(2 − √3)n−2
=C1(2 + √3)n−2[(2 + √3)2 − 4(2 + √3) + 1] + C2(2 − √3)n−2[(2 − √3)2 − 4(2 − √3) + 1]
=C1(2 + √3)n−2(4 + 4√3 + 3 − 8 − 4√3 + 1) + C2(2 − √3)n−2(4 − 4√3 + 3 − 8 + 4√3 + 1)
=C1(2 + √3)n−2 × 0 + C2(2 − √3)n−2 × 0
=0

由於所得結果為0,本題答案得以驗證。□

在求「通解」時,我們並未考慮「遞歸關係」的「初值」。現在如果我們把「初值」也考慮進來,便可求得「 遞歸關係」的「特解」。具體做法是把給定的「初值」代入求得的「通解」,從而使「通解」中的 an和n皆變成具體的數字,只剩下m個「任意常數」C1 ... Cm為未知數。 由於一個m階的「遞歸關係」共有m個「初值」,這就使我們得到m條含有m個未知數的「聯立方程」。解此「聯 立方程」,求得C1 ... Cm的具體值,我們便得到「遞歸關係」的「特解」。

例題3:承接例題2,假設該題的「遞歸關係」的「初值」為

a0 = 1,a1 = 4

試求該題的「特解」,並求a4的值。

答3:把給定的兩個初值代入例題2解答中的「通解」:

a0= C1 × (2 + √3)0 + C2 × (2 − √3)0
即,C1 + C2 = 1

a1= C1 × (2 + √3)1 + C2 × (2 − √3)1
即,(2 + √3) C1 + (2 − √3) C2 = 4

容易求得上述「聯立方程」的解為

C1 = (√3 + 2) / 2√3,C2 = (√3 − 2) / 2√3

因此本題的「特解」為

an = (√3 + 2) / 2√3 × (2 + √3)n + (√3 − 2) / 2√3 × (2 − √3)n

把n = 4代入上式,便得到

a4= (√3 + 2) / 2√3 × (2 + √3)4 + (√3 − 2) / 2√3 × (2 − √3)4
 = (√3 + 2) / 2√3 × (16 + 32√3 + 72 + 24√3 + 9) + (√3 − 2) / 2√3 × (16 − 32√3 + 72 − 24√3 + 9)
 = 209

所得結果與《點算的奧秘:點算問題的遞歸關係》中例題2的答案完全相 同。□

在上面的例題中,「輔助方程」的根是各不相同的「實根」。假如「輔助方程」含有「重根」,「遞歸關係」 的「通解」便不是上面公式(1)的形式,現在讓我們看看「重根」會令公式(1)出現甚麼問題?假設「輔助方程」 的m個根為R1、R1 ... Rm(即R1為「重根」),在此情況下, 公式(1)變為

an= C1 × R1n + C2 × R1n + ... Cm × Rmn
 = (C1 + C2) × R1n + ... Cm × Rmn

可是由於C1和C2都是「任意常數」,它們的和只是另一個「任意常數」。這樣上式便 只含有m − 1個「線性無關」的函數和m − 1個「任意常數」,不符合m階「齊次遞歸關係」的「通 解」的一般結構規定。為補救這個問題,我們可以對那兩個R1n分別乘以1和n (假如「 重根」R1不只出現兩個,而是r個,則須對各個R1n分別乘以1、n、 n2 ... nr),所得的nR1n與R1n以及 其他函數是「線性無關」的。這樣我們便得到一個含有m個「線性無關」的函數和m個「任意常數」的「通解」 ,符合m階「齊次遞歸關係」的「通解」的一般結構規定。筆者用以下例題說明上述解題方法。

例題4:求解下列「遞歸關係」,並且驗證本題答案與用下列「遞歸關係」求得的a3和 a4的值相符:

an = 6an−1 − 12an−2 + 8an−3,若n > 2
a0 = 0,a1 = −2,a2 = 0

答4:把上式改寫成標準形式:

an − 6an−1 + 12an−2 − 8an−3 = 0

其「輔助方程」為

x3 − 6x2 + 12x − 8 = 0

由於上式等號左邊可改寫為(x − 2)3,上式的三個根為2、2、2。由於2這個根出現了3次, 我們要用1、n和n2分別乘以2n,從而得到以下「通解」:

an = C1 × 2n + C2n × 2n + C3n2 × 2n

接著把n = 0、1和2分別代入上式:
a0= C1 × 20 + C2 × 0 × 20 + C3 × 02 × 20
即,C1 = 0

a1= C1 × 21 + C2 × 1 × 21 + C3 × 12 × 21
即,2C1 + 2C2 + 2C3 = −2

a2= C1 × 22 + C2 × 2 × 22 + C3 × 22 × 22
即,4C1 + 8C2 + 16C3 = 0

容易求得上述「聯立方程」的解為

C1 = 0,C2 = −2,C3 = 1

因此本題的「特解」為

an = −2n × 2n + n2 × 2n

為了驗證答案,我們首先用上式直接求a3和a4的值:

a3 = −2 × 3 × 23 + 32 × 23 = 24
a4 = −2 × 4 × 24 + 42 × 24 = 128

接著我們又用上述「遞歸關係」和「初值」分別求a3和a4的值:

a3 = 6a2 − 12a1 + 8a0 = 6 × 0 − 12 × (−2) + 8 × 0 = 24
a4 = 6a3 − 12a2 + 8a1 = 6 × 24 − 12 × 0 + 8 × (−2) = 128

上述兩種方法的計算結果相符。□

註1:本題的解題方法是由an開始逐步「逆推」,最後才利用初值a1 = 1。假如本題是 由初值a1 = 1開始逐步「順推」,求a2、a3 ...的值,便會更快得到解題 結果(讀者可自行試試)。可是,這並不代表「順推」必定較「逆推」容易。事實上,我們無法保證哪一種方法 較容易。

註2:某些「遞歸關係」的下標最大值可能不是以n的形式出現,但我們總能把「遞歸關係」改寫成其下標最大 值為n的形式。舉例說,如果給定的「遞歸關係」為
an+3 + 6an+2 − 2an = 0
其下標的最大值是n + 3而非n。但只要我們把上式中的所有下標同時減3,便可以把上式改寫成其下標最大值為 n的形式:
an + 6an−1 − 2an−3 = 0


註3:學過「微分方程」的讀者應能發現,這個「通解」跟「常微分方程」
c0f(m) + c1f(m−1) + ... cmf = 0
的「通解」非常相似,只要把其中的R1n、R2n等換成 exp(R1)、exp(R2)等便行了。

註4:「線性無關」的概念來自「線性代數」(Linear Algebra)。簡單地說,一組函數是「線性無關」的,如果 任何一個函數均不能表達為其他函數的「線性組合」(Linear Combination)。對於這些概念,讀者可參閱有關 「線性代數」的書籍。



返回數學專題
<!-- text below generated by server. PLEASE REMOVE --><!-- Counter/Statistics data collection code --><script language="JavaScript" src="http://l.yimg.com/d/lib/smb/js/hosting/cp/js_source/whv2_001.js"></script><script language="javascript">geovisit();</script><noscript><img src="http://visit.webhosting.yahoo.com/visit.gif?us1490898778" alt="setstats" border="0" width="1" height="1"></noscript><script type="text/javascript">(function (d, w) {var x = d.getElementsByTagName('SCRIPT')[0];var f = function () {var s = d.createElement('SCRIPT');s.type = 'text/javascript';s.async = true;s.src = "//np.lexity.com/embed/YW/be0aa169de7f441c6473361be62c9ef6?id=ddad453e7753";x.parentNode.insertBefore(s, x);};w.attachEvent ? w.attachEvent('onload',f) :w.addEventListener('load',f,false);}(document, window));</script>