在《點算的奧秘：點算問題的遞歸關係》中，筆者介紹了把某些點算問題表達為「遞歸關係」的方法。這種方法的優點是，無論點算問題多麼複雜，只要我們利用有關「遞歸關係」，從初值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：根據上述「遞歸關係」，我們有
現在，把上式中的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中的「遞歸關係」便可以寫成以下標準形式：
寫成標準形式後，等號左邊便有點類似一個「多項式」(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)。當我們把「遞歸關係」寫成標準形式後，便可以寫出其「輔助方程」。假設「遞歸關係」的標準形式為
這裡c0、c1 ... cm為「遞歸關係」中各項的「系數」，m為「遞歸關係」的「階」(請注意m等於上式中各項下標最大值n與最小值n−m之差)。那麼上述「遞歸關係」的「輔助方程」為
由此可見，「遞歸關係」的「輔助方程」實際是一條「多項式方程」，這條方程的「階」(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，則「遞歸關係」的「通解」為
在上式中，R1n、R2n ... Rmn為m個「線性無關」(Linearly Independent)的函數(註4)，C1、C2 ... Cm則為m個「任意常數」(Arbitrary Constant)。在一般情況下，一個m階「齊次遞歸關係」的「通解」須符合以下結構規定：即應由m個「線性無關」函數連同m個「任意常數」組成。「任意常數」的存在告訴我們，「遞歸關係」的「通解」並不只代表一個解，而是無限個解。只要我們把m個實數代入C1 ... Cm，便可得到一個解。筆者用以下例題說明上述解題方法。
例題2：試求以下「遞歸關係」的「通解」，並驗證答案：
答2：上式就是《點算的奧秘：點算問題的遞歸關係》中例題2的「遞歸關係」。由於本題只需求「通解」，所以我們無需理會上述「遞歸關係」的「初值」。首先把上式改寫成標準形式：
由於上式是二階「遞歸關係」，其「輔助方程」為
利用求解二次方程的公式，容易求得上式的兩個「實根」為2 + √3和2 − √3。因此本題的「通解」為
接著讓我們驗證上述答案，方法是把上式代入上面的標準形式(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，假設該題的「遞歸關係」的「初值」為
試求該題的「特解」，並求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 | |
容易求得上述「聯立方程」的解為
因此本題的「特解」為
把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：把上式改寫成標準形式：
其「輔助方程」為
由於上式等號左邊可改寫為(x − 2)3，上式的三個根為2、2、2。由於2這個根出現了3次，我們要用1、n和n2分別乘以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 | |
容易求得上述「聯立方程」的解為
因此本題的「特解」為
為了驗證答案，我們首先用上式直接求a3和a4的值：
接著我們又用上述「遞歸關係」和「初值」分別求a3和a4的值：
上述兩種方法的計算結果相符。□
註1：本題的解題方法是由an開始逐步「逆推」，最後才利用初值a1 = 1。假如本題是由初值a1 = 1開始逐步「順推」，求a2、a3 ...的值，便會更快得到解題結果(讀者可自行試試)。可是，這並不代表「順推」必定較「逆推」容易。事實上，我們無法保證哪一種方法較容易。