在《點算的奧秘：齊次遞歸關係的解》中，筆者介紹了求解「常系數一元線性齊次遞歸關係」的方法，在本網頁筆者將介紹求解「常系數一元線性非齊次遞歸關係」的方法。在這裡首先重溫「非齊次遞歸關係」的定義。當我們把一個「遞歸關係」寫成標準形式，即把含有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亦要具有同類型的複雜形式，現把這些情況總結成下表：
| 類型 | 「遞歸關係」的「非齊次部分」 | pn的形式 |
|---|---|---|
| 指數函數 | 3 × 2n | A × 2n |
| 多項式 | n3 − 1 | An3 + Bn2 + Cn + D |
| 混合指數函數 | 3 × 2n − 5n | A × 2n + B × 5n |
| 指數函數 + 多項式 | 3 × 2n + 6n2 − 3 | A × 2n + Bn2 + Cn + D |
在上表中，A、B、C、D是未定的系數，當我們把上述含有未定系數的「特解」代入給定的「遞歸關係」後，便可解出這些系數的值。筆者用以下例題說明如何運用「未定系數法」。
例題1：試求以下「遞歸關係」的「特解」：
答1：本題的「遞歸關係」就是《點算的奧秘：點算問題的遞歸關係》中例題3的「遞歸關係」。首先把上式改寫成標準形式：
由於上式的「非齊次部分」是「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後，我們便可以把pn加上前述「相關齊次遞歸關係」的「通解」gn，這樣便得到「非齊次遞歸關係」的「通解」，即
請注意上述「通解」須符合以下一般結構規定：gn與pn的各項應是「線性無關」的。由於上述「通解」含有若干個「任意常數」，如果我們把給定的「初值」代入上述「通解」，便可求出這些「任意常數」的值，從而得到滿足給定「初值」的「特解」。
例題2：承接例題1，假設該題的「遞歸關係」的「初值」為
試求解上述「遞歸關係」，並求a4的值。
答2：本題的「相關齊次遞歸關係」為
上式的「輔助方程」為
由於上述方程只有一個「實根」2，我們求得本題的「相關齊次遞歸關係」的「通解」為
把上面的gn與在例題1求得的pn加起來，便得到本題的「通解」為
把給定的「初值」代入上式，便得到
| a1 = C × 21 − 1 − 1 |
| 即，2C − 2 = 0 |
容易求得C = 1。因此滿足本題給定「初值」的「特解」為
把n = 4代入上式，我們便求得
上述答案與《點算的奧秘：點算問題的遞歸關係》例題3的答案完全吻合。□
當「非齊次部分」的某部分與gn的某部分具有相同的形式時，假如我們仍然沿用上面表1所示pn的形式，這就會使gn與pn在某部分重合，因而不符合「線性無關」的要求，違反有關遞歸關係「通解」的結構規定。為補救此一問題，我們可以仿照上節處理「重根」的做法，對pn中與gn重合的部分乘以n。筆者用以下例題說明上述解題方法。
例題3：求解以下「遞歸關係」並求a4的值：
| an = 2an−1 + 3n−1 − 2n−1 | ，若n > 1 |
| a1 = 0 |
答3：本題的「遞歸關係」就是《點算的奧秘：點算問題的遞歸關係》中例題4的「遞歸關係」。首先把上述「遞歸關係」改寫成標準形式：
本題的「相關齊次遞歸關係」的「輔助方程」為
因此本題的「相關齊次遞歸關係」的「通解」為
接著求pn。由於本題的「非齊次部分」為3n−1 − 2n−1，本來根據表1，
但這個pn的一部分(B × 2n)與上述的gn具有相同的形式，pn與gn並不符合「線性無關」的要求。因此我們要對pn中與gn重合的部分乘以n，從而得到以下經修訂的pn(讀者可自行驗證，如果不對pn作出如下修訂，我們將無法解出A和B)：
把上述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加起來，便得到本題的「通解」為
接著把給定的「初值」代入上式，便得到
| a1 = C × 20 + 30 − 0 × 20−1 |
| 即，C + 1 = 0 |
容易求得C = −1。因此滿足本題給定「初值」的「特解」為
把n = 4代入上式，我們便求得
上述答案與《點算的奧秘：點算問題的遞歸關係》例題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：由於給定的「遞歸關係」本身已是以標準形式出現，容易看到本題的「相關齊次遞歸關係」的「輔助方程」為
容易驗證可以把上式因式分解為
由於在上式的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)與上述gn中的兩個部分(C和E × 2n)具有相同的形式，pn與gn並不符合「線性無關」的要求。現在我們分別研究如何修訂pn的兩個部分，首先考慮A。假如對此項乘以n，所得結果An仍然與gn中的Dn具有相同的形式。假如對此項乘以n2，所得結果An2不再與gn中的任何部分重合。其次考慮B × 2n。假如對此項乘以n，所得結果Bn × 2n不與gn中的任何部分重合。因此，經修訂的pn為
把上述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 |
上式應等於給定「遞歸關係」的等號右端：
比較上式等號兩端，容易解得A = −1，B = 4。因此
| pn | = −n2 + 4n × 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和a4的值：
上述兩種方法的計算結果相符。□
註1：「遞歸關係」的「特解」有兩種意義(其實「常微分方程」的「特解」也是如此)，它既可以指滿足某「遞歸關係」的給定「初值」的解，這種「特解」要透過把「初值」代入「遞歸關係」的「通解」來求得；亦可以指滿足某「非齊次遞歸關係」的不含「任意常數」的解，這種「特解」要使用下文將要介紹的「未定系數法」來求。本網頁會同時用到這兩種意義的「特解」。筆者不知為何數學界要用同一個名稱指稱兩個很不同的概念，這確實是一種很不理想的情況，有時會造成混亂。但由於這兩種意義的「特解」在數學界中沿用已久，本網頁惟有依循數學界的習慣，並在此提醒讀者小心分辨這兩種意義。