在前面幾節，筆者介紹了求解「遞歸關係」的「標準」方法，這種方法跟求解「微分方程」的「標準」方法非常相似。不過，正如「微分方程」有其他解題方法(例如「拉普拉斯變換」Laplace Transform)，「遞歸關係」也有一種類似「積分變換」(Integral Transform)的解題方法，那就是「母函數」方法。
筆者在以前曾指出，「母函數」是一種記載某些數值信息的方法。現設我們有一個「遞歸關係」，各項的值為a0、a1、a2 ... an ...，那麼我們可以把這些值寫成以下這個「母函數」：
如果給定某一「遞歸關係」，我們能求得相應的f(x)，這便等於求得該「遞歸關係」的解。以下讓我們看如何利用某些代數方法求這個f(x)。這些代數方法需要用到以下的公式：
上面的公式(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)，於是得到
為了方便以下的計算，我們首先對上式作一些調整：
接著我們利用關係式m = n − 1對上式中等號右端第一項的「求和變項」進行變換，得到下式：
接著我們把上式中某些項的下限改為0 (但這樣做實際等於在原來的項上加上某些新的項，我們須減去這些多出的項。舉例說，如果我們把Σ1 ≤ n < ∞ anxn改為Σ0 ≤ n < ∞ anxn，這實際等於在原來的Σ1 ≤ n < ∞ anxn上加上a0，因此我們須在更改下限後減去這個a0)，得到
至此，我們可以利用上面的公式(1)、(2)、(3)和本題給定的「初值」(註2)把上式改寫為
對上式求解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為二次項，所以我們假設
其中A、B、C為待求的常數。對上式等號兩端同時乘以(1 − x)2(1 − 2x)，便得到
接著我們固然可以展開上式等號右端，得到三條「聯立方程」，並從而解出A、B和C，但較簡便的方法是把一些常數代入上式中的x，從而化簡上式。例如把x = 1代入上式，便可得到
其次把x = 1 / 2代入上式，便可得到
最後把x = 0代入上式，便可得到
這樣我們同樣可得到三條「聯立方程」，但那是非常簡單的「聯立方程」。容易看到，這三條「聯立方程」的解為A = 0，B = −1，C = 1。至此我們成功求得
把以上結果代入上面(4)，便得到
最後我們再次運用公式(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。
最後，比較上面等號兩端，我們看到本題答案為
以上的答案與《點算的奧秘：非齊次遞歸關係的解》中例題2的答案完全相同。□
從上題的解答可見，用「母函數」來求解「遞歸關係」，無需區分「齊次遞歸關係」與「非齊次遞歸關係」，也無需區分求「通解」與「特解」的步驟，這是「母函數」解題法的優點。不過其缺點是，須對「母函數」進行各種變換(例如變換其「求和變項」、分解為部分分式、適當地利用像(2)和(3)那樣的公式等)，有時可能涉及頗繁複的計算。
接著讓我們看另一個例題。
例題2：求解以下「遞歸關係」：
| an = 2an−1 + 3n−1 − 2n−1 | ，若n > 0 |
| a0 = 0 |
答2：本題就是《點算的奧秘：非齊次遞歸關係的解》中的例題3。我們首先對上式各項乘以xn，然後對x求和(下限為1)，於是得到
接著對上式進行各種變換：
| Σ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) |
接著我們要把上式等號右端的分式分解為「部分分式」。我們假設
對上式等號兩端同時乘以(1 − 3x)(1 − 2x)2，得到
現在，把x = 1 / 2代入上式，便可得到
其次，把x = 1 / 3代入上式，得到
最後，把x = 0代入上式，得到
利用上面三條「聯立方程」，容易求得
把以上結果代入(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 |
比較上面等號兩端，我們看到
上式跟《點算的奧秘：非齊次遞歸關係的解》中例題3的答案相符。□
以下讓我們看如何用「母函數」方法求解含複數解的「遞歸關係」。由於這類「遞歸關係」可能涉及繁複的計算，以下只舉一個簡單的例子。
例題3：求解以下「遞歸關係」，把答案表達為「三角函數」的形式，並驗證答案：
| an = −an−2，若n > 1 |
| a0 = 2，a1 = −2 |
答3：首先對上式各項乘以xn，然後對x求和(下限為2，因為給定的「遞歸關係」的限制條件為n > 1)：
接著對上式進行各種變換：
| Σ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)。因此我們可以嘗試把上式等號右端的分式分解為「部分分式」，即假設
經過一番計算，容易求得解得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 |
比較上面等號兩端，我們看到
可是上面不是「三角函數」的形式。不過，我們可以把上面4個「複數」改寫為「極坐標」形式：
另外，根據《點算的奧秘：含複數解的遞歸關係》中的定理1，
把以上結果代入(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依次代入上式時，便會得到
由於「三角函數」是「周期函數」(Periodic Function)，當n = 4時，cos90n° = cos360° = cos0°，sin90n° = sin360° = sin0°，所以a4 = a0。由此可知，an的值不斷以2、−2、−2、2的次序循環，由此我們可以總結出
容易看到，以上序列符合給定的「遞歸關係」，所以上面求得的答案是正確的。□
從上題的解答我們看到一個有趣的現象，雖然上題最初求得的答案(6)表面上含有「虛數單位」i，但在把(6)中的複數改寫為「極坐標」形式後，含有i的部分最終互相抵消了，因此上題的最終答案不含任何i。這是完全合理的，因為既然給定的「遞歸關係」和「初值」全為「實數」，那麼本題的解答也應只含有實數。