某一類的遞迴方程式 f(n) 滿足以下形式 :

f(n) = \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n)\ \ \ \ \ \ \ \ \ \ (I)

其中, g_{i}(n) (i = 1, 2, ..., k)g(n) 都是關於 n 的函數, 而不是關於 f 的函數. 除此之外, k 為任意正整數, g_{k}(n) \neq 0. 我們稱類似的 f(n) 為線型遞迴方程式. 若 g_{k}(n) = 0, 則

f(n) = \sum \limits_{i = 1}^{k - 1}g_{i}(n)f(n - i) + g(n)

其遞迴深度未達到 k, 不能稱為線型遞迴方程式

若存在 k 個整數 a_{1}, a_{2}, ..., a_{k} 使得 g_{1}(n) = a_{1}, g_{2}(n) = a_{2}, ..., g_{k}(n) = a_{k}, 那麼 f(n) 可以展開為

f(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n)\ \ \ \ \ \ \ \ \ \ (II)

其中, a_{k} \neq 0, n \geq k. 當 g(n) = 0 時, 稱 f(n) 為齊次線型遞迴方程式; 當 g(n) \neq 0 時, 稱 f(n) 為非齊次線型遞迴方程式

對於

f(n) = \begin {cases} c_{1} ^{n = 1} \\ 2f(\frac {n}{2}) + c_{2}n & {n \geq 2} \end {cases}, 其中\ \log_{2}{n}\ 為整數

由於線型遞迴方程式要求右側的 ff(n - i) 的形式, i = 1, 2, ..., k. 而上述遞迴方程式中, f(\frac {n}{2}) 不滿足這樣的形式, 因此上述遞迴方程式不會線型遞迴方程式. 但因為 \log_{2}{n} 為整數, 因此 f(n) 可以寫為

f(2^{k}) = \begin {cases} c_{1} & {k = 0} \\ 2f(2^{k - 1}) + c_{2}2^{k} & {k \geq 1} \end {cases}

h(k) = f(2^{k}), 則有

h(k) = \begin {cases} c_{1} & {k = 0} \\ 2h(k - 1) + c_{2}2^{k} & {k \geq 1} \end {cases}

顯然, h(k)f(k) 等價, 解 h(k) 實質上就是要解 f(n). 而 h(k) 顯然是一個線型遞迴方程式. 根據 k 的值, 我們稱 (I) 式為 k 階線型遞迴方程式. 因此 h(k) 是一個一階線型遞迴方程式. 其中, g_{1}(k) = 2, g(k) = c_{2}2^{k}. h(k) 是一個一階非齊次線型遞迴方程式

考慮

T(n) = \begin {cases} c_{1} & {n \leq 1} \\ \frac {2}{n}\sum \limits_{i = 1}^{n - 1}T(i) + c_{2}n & {n > 1} \end {cases}

其中, c_{1}c_{2} 為任意常數. T(n) 同樣不是線型遞迴方程式, 但是可以通過轉化, 讓其成為線型遞迴方程式. 當 n > 1 時,

T(n) = \frac {2}{n}\sum \limits_{i = 1}^{n - 1}T(i) + c_{2}n\ \ \ \ \ \ \ \ \ \ (III)

等式兩側同時乘以 n, 得

nT(n) = 2\sum \limits_{i = 1}^{n - 1}T(i) + c_{2}n^{2}

使用 n - 1 替換上式中的 n, 有

(n - 1)T(n - 1) = 2\sum \limits_{i = 1}^{n - 2}T(i) + c_{2}(n - 1)^{2}\ \ \ \ \ \ \ \ \ \ (IV)

使用 (III) 式減去 (IV) 式, 得

nT(n) - (n - 1)T(n - 1) = 2\sum \limits_{i = 1}^{n - 1}T(i) - 2\sum \limits_{i = 1}^{n - 2}T(i) + c_{2}n^{2} - c_{2}(n - 1)^{2}

展開之後有

nT(n) - nT(n - 1) + T(n - 1) = 2T(n - 1) + c_{2}(2n - 1)

移項得

nT(n) = (n + 1)T(n - 1) + c_{2}(2n - 1)

等式兩側同時乘以 \frac {1}{n}, 最終可得

T(n) = \frac {n + 1}{n}T(n - 1) + c_{2}(2 - \frac {1}{n})

不難看出, T(n) 是一個一階非齊次線型遞迴方程式. 其中, g_{1}(n) = \frac {n + 1}{n}, g(n) = c_{2}(2 - \frac {1}{n})

費氏數列

F(n) = \begin {cases} 0 & {n = 0} \\ 1 & {n = 1} \\ F(n - 1) + F(n - 2) & {n > 1} \end {cases}

是一個典型的二階齊次線型遞迴方程式

(II) 式在演算法分析中經常會遇到, 特別是針對使用了分而治之思想的演算法

對於函數 f(n) = \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n) 時需要 k 個初始值的 : f(0), f(1), ..., f(k - 1), 從而使得 f(k), f(k + 1), ... 有惟一值. 此時, f(n) 可以表示為

f(n) = \begin {cases} c_{1} & {n = 0} \\ c_{2} & {n = 1} \\ \vdots & {\vdots} \\ c_{k - 1} & {n = k - 1} \\ \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n) & {n \geq k} \end {cases}

對於函數 f(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n), 若已知 f(0), f(1), ..., f(k - 1), 則我們可以通過建立方程式組來得到 a_{1}, a_{2}, ..., a_{k} 的值

在代數學中, 我們知道, 對於非齊次線型遞迴方程式

f(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n)

的解是其對應的齊次線型遞迴方程式的通解

f_{h}(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k)\ \ \ \ \ \ \ \ \ \ (V)

再加上一個非齊次線型遞迴方程式的特解

f_{p}(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n)\ \ \ \ \ \ \ \ \ \ (VI)

f(n) 的通解可以表示為 f_{h}(n) + f_{p}(n)

為了確定 f_{h}(n), 我們首先對 (V) 式進行移項, 得

f_{h}(n) - a_{1}f(n - 1) - a_{2}f(n - 2) - ... - a_{k}f(n - k) = 0

不妨假設上述方程式可以得到一個解 f_{h}(n) = Ax^{n}, 其中 A \neq 0. 將解代入上述方程式, 可以得到

Ax^{n} - a_{1}Ax^{n - 1} - a_{2}Ax^{n - 2} - ... - a_{k}Ax^{n - k} = 0

等式兩側同時乘以 \frac {1}{A} 並提取 x^{n - k}

x^{n - k}(x^{k} - a_{1}x^{k - 1} - a_{2}x^{k - 2} - ... - a_{k - 1}x - a_{k}) = 0

上式可以簡寫為

x^{n - k}(x^{k} - \sum \limits_{i = 1}^{k}a_{i}x^{k - 1}) = 0

顯然, 上述方程式有 n 個根, 其中有 n - k 個根是 0, 剩下 k 個根取決於

x_{k} - a_{1}x^{k - 1} - a_{2}x^{k - 2} - ... - a_{k - 1}x - a_{k} = 0

上述方程式成為 f_{h}(n) 的特徵方程式, 有 k 個根 : r_{1}, r_{2}, ..., r_{k}. 可能存在某個根 r_{i} (i = 1, 2, ..., k) 重複 j 次 (j \leq k)

定理 1. 若 f_{h}(n) 的特徵方程式

x_{k} - a_{1}x^{k - 1} - a_{2}x^{k - 2} - ... - a_{k - 1}x - a_{k} = 0

s 個互異解 t_{1}, t_{2}, ..., t_{s} (s \leq k). 則通解為 f_{h}(n) 可以表示為

f_{h}(n) = u_{1}(n) + u_{2}(n) + ... + u_{s}(n)

其中,

u_{i}(n) = (c_{i_{0}} + c_{i_{1}}n + c_{i_{2}}n^{2} + ... + c_{i_{w - 1}}n^{w - 1})t_{i}^{n},

w 是根 t_{i} 的重複次數, i = 1, 2, ..., s

這個定理我們暫時不證明

使用定理 1, 我們可以很容易得到其次線型遞迴方程式的通解. 考慮費氏數列當 n > 1 時的情形 :

F(n) = F(n - 1) + F(n - 2)

:

設其通解為 F_{h}(n) = Ax^{n}, 其中 A \neq 0, 將 F_{h}(n) 代入上式得到其特徵方程式

x^{2} - x - 1 = 0

解得 x_{1} = -\frac {\sqrt {5}}{2} + \frac {1}{2}, x_{2} = \frac {\sqrt {5}}{2} + \frac {1}{2}. 每個根僅重複一次, 則 w = 1. 故

u_{1}(n) = c_{1}(-\frac {\sqrt {5}}{2} + \frac {1}{2})^{n}, u_{2}(n) = c_{2}(\frac {\sqrt {5}}{2} + \frac {1}{2})^{n}

因此, F(n) = F(n - 1) + F(n - 2) 的通解為

F_{h}(n) = u_{1}(n) + u_{2}(n) = c_{1}(-\frac {\sqrt {5}}{2} + \frac {1}{2})^{n} + c_{2}(\frac {\sqrt {5}}{2} + \frac {1}{2})^{n}

考慮 F(0) = 0, F(1) = 1, 得到方程式組

\begin {cases} F(0) = c_{1} + c_{2} = 0 \\ F(1) = c_{1}(-\frac {\sqrt {5}}{2} + \frac {1}{2}) + c_{2}(\frac {\sqrt {5}}{2} + \frac {1}{2}) = 1 \end {cases} \ \ \ \Rightarrow \ \ \ \begin {cases} c_{1} = -\frac {1}{\sqrt {5}} \\ c_{2} = \frac {1}{\sqrt{5}} \end {cases}

故費氏數列的通項公式可以表示為

F(n) = \frac {1}{\sqrt {5}}(\frac {1 + \sqrt {5}}{2})^{n} - \frac {1}{\sqrt {5}}(\frac {1 - \sqrt {5}}{2})^{n}

\blacksquare

利用類似的方法來解遞迴方程式的過程, 我們稱之為特徵根法. 當然, 目前我們僅得到了齊次線型遞迴方程式的求解方法, 對於 g(n) \neq 0 的情況, 我們還需要得到一個特解 f_{p}(n). 對於任意 g(n) = 0, 目前還沒有一個適用於任意 g(n) 的特解 f_{p}(n). f_{p}(n) 的形式取決於 g(n), 因此我們僅考慮兩種形式 : g(n) 是關於 n 的多項式及 g(n) 是關於 n 的指數函數

首先, 當 g(n) = 0 時, f(n) 的特解 f_{p}(n) = 0; 當 g(n) = \sum \limits_{i = 0}^{d}e_{i}n^{i}, 其中 e_{d} \neq 0, 那麼特解 f_{p}(n) 有如下形式 :

f_{p}(n) = p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{d + m}n^{d + m}

其中, m 的值取決於 f(n) 對應的齊次線型遞迴方程式的特徵方程式的解. 如果 r = 1 時特徵方程式的解, 那麼 m 的值時根 r = 1 的重複次數; 如果 r = 1 不是特徵方程式的解, 則 m = 0

由於 f_{p}(n)f(n) 的一個特解, 為了確定 p_{0}, p_{1}, ..., p_{d + m} 的值, 我們將 f_{p}(n) 代入 f(n) 中, 得到

\begin {aligned} f_{p}(n) &= p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{d + m}n^{d + m} \\ &= a_{1}(p_{0} + p_{1}(n - 1) + p_{2}(n - 1)^{2} + ... + p_{d + m}(n - 1)^{d + m}) \ + \\ &\ \ \ \ \ a_{2}(p_{0} + p_{1}(n - 2) + p_{2}(n - 2)^{2} + ... + p_{d + m}(n - 2)^{d + m}) \ + \\ &\ \ \ \ \ ... \ + \\ &\ \ \ \ \ a_{k}(p_{0} + p_{1}(n - k) + p_{2}(n - k)^{2} + ... + p_{d + m}(n - k)^{d + m}) + g(n) \end {aligned}

觀察等式兩側, 可以得到共計 d + m 個關於 p_{i} (i = 1, 2, ..., d + m) 的方程式. 將這些方程式組成一個方程式組, 解得 p_{1}, p_{2}, ..., p_{d + m} 的值即可;

g(n) = ca^{n}, 其中 ac 為任意常數, a > 0, 那麼特解 f_{p}(n) 有如下形式 :

f_{p}(n) = (p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{w}n^{w})a^{n}

其中, w 的值取決於 f(n) 對應的齊次線型遞迴方程式的特徵方程式的解. 如果 r = a 是特徵方程式的解, 那麼 w 的值是根 r = a 的重複次數, 如果 r = a 不是特徵方程式的解, 則 w = 0

同樣地, 由於 f_{p}(n)f(n) 的一個特解, 為了確定 p_{1}, p_{2}, ..., p_{d + m} 的值, 我們將 f_{p}(n) 代入 f(n) 中, 得到共計 w 個關於 p_{i} (i = 1, 2, ..., d + m) 的方程式. 將這些方程式組成一個方程式組, 解得 p_{1}, p_{2}, ..., p_{d + m} 的值即可

自此, 我們得到了使用特徵根法來求解遞迴方程式的過程. 對於線型遞迴方程式

f(n) = \begin {cases} c_{1} & {n = 0} \\ c_{2} & {n = 1} \\ \vdots & {\vdots} \\ c_{k - 1} & {n = k - 1} \\ \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n) & {n \geq k} \end {cases}

其中, c_{1}, c_{2}, ..., c_{k - 1}, a_{1}, a_{2}, ..., a_{k} 是常數, g(n) 是關於 n 的函數而不是關於 f 的函數. f(n) 的求解過程如下 :

1. 對於 n \geq k 時的 f(n), 寫下其特徵方程式

x^{k} - \sum \limits_{i = 1}^{k}a_{i}x^{k - i} = 0

2. 求解特徵方程式的互異根 t_{1}, t_{2}, ..., t_{s} (s \leq k), 並確定任意根 r = t_{i} 的重複次數 j_{i} (i = 1, 2, ..., s, j_{i} \leq k)

3. 根據每個根 r_{i}, 寫下 u_{i}(n), 並令

f_{h}(n) = u_{1}(n) + u_{2}(n) + ... + u_{s}(n)

其中, u_{i}(n) = (c_{i_{0}} + c_{i_{1}}n + c_{i_{2}}n^{2} + ... + c_{i_{w - 1}}n^{w - 1})t_{i}^{n}, i = 1, 2, ..., s, w = j_{i}

4. 根據給定的 f(0), f(1), ..., f(k - 1) 的值, 計算每一個 u_{i}(n) 中的 c_{i_{0}}, c_{i_{1}}, ..., c_{i_{w - 1}}. 其中, i = 1, 2, ..., s, w = j_{i}

5.     1) 若 g(n) = 0, 則 f_{p}(n) = 0

2) 若 g(n) = \sum \limits_{i = 1}^{d}e_{i}n^{i}, 其中 e_{d} \neq 0, e_{i} (i = 1, 2, ..., d) 為任意常數. 則

f_{p}(n) = p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{d + m}n^{d + m}

其中, m 的值取決於 r = 1 是否為特徵方程式的根

3) 若 g(n) = ca^{n}, 其中 ac 為任意常數, a > 0, 則

f_{p}(n) = (p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{w}n^{w})a^{n}

其中, w 的值取決於 r = a 是否為特徵方程式的根

6. 若 g(n) \neq 0, 則將 f_{p}(n) 代入 f(n) 中, 求得 p_{0}, p_{1}, ..., p_{d + m} 或 p_{0}, p_{1}, ..., p_{w} 的值

7. 最終, 線型遞迴方程式 f(n) 的解為

f(n) = f_{h}(n) + f_{p}(n)

定理 2. 通過上述七個步驟找到的 f(n) = f_{h}(n) + f_{p}(n) 是線型遞迴方程式 f(n) 的惟一解

這個定理我們暫時不證明

這七個步驟稱為求解線型遞迴方程式 f(n) 的特徵根法

某些非線性遞迴方程式也可以通過適當的變換, 將其轉化為線型遞迴方程式, 再利用特徵根法進行求解. 考慮 :

f^{c}(n) = \sum \limits_{i = 1}^{k}a_{i}f^{c}(n - i) + g(n), n \geq k, c\ 為任意常數

q(n) = f^{c}(n), 則有

q(n) = \sum \limits_{i = 1}^{k}a_{i}q(n - i) + g(n), n \geq k

此時, 非線性的 f^{c}(n) 就轉化為了線型的 q(n)

另外, 某些線型遞迴方程式可能具有非恆定的係數 :

nf(n) = \sum \limits_{i = 1}^{k}a_{i}f(n - i) + g(n), n \geq k

我們無法直接使用特徵根法進行求解, 但也可以作適當的變換, 使其具有恆定係數. 記 q(n) = nf(n), 則有

q(n) = \sum \limits_{i = 1}^{k}a_{i}q(n - i) + g(n), n \geq k

在這樣的情況下, 我們得到的是關於 q(n) 的通解, 此時只需將 q(n) 使用 f(n) 進行替換, 即可得到原遞迴方程式的通解