摘要訊息 : 使用特徵根法解一個遞迴方程式.

0. 前言

在《【遞迴方程式】替代法與歸納法》中, 我們講解了使用替換法, 歸納法和列表法三種方法去解一個遞迴方程式. 但是對於比較複雜的遞迴方程式, 這三種方法可能都難以得到最終的解.

更新紀錄 :

• 2022 年 6 月 5 日進行第一次更新和修正.

1. 線性遞迴方程式

定義 1. 若遞迴方程式 f(n) 滿足 \displaystyle {f(n) = \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n), \ \ \ \ \ \ \ \ \ \ (\mathrm {I})} 其中 g_{i}(n) (i = 1, 2, ..., k) 與 g(n) 都是關於 n 的函數, 而不是關於 f 的函數; k 為任意正整數; g_{k}(n) \neq 0, 那麼我們稱 f(n) 為線性遞迴方程式 (linear recurrence).

根據定義 1, 若 g_{k}(n) = 0, 則 \displaystyle {f(n) = \sum \limits_{i = 1}^{k - 1}g_{i}(n)f(n - i) + g(n)}, 其遞迴深度未達到 k, 不能稱為線性遞迴方程式.

定義 2. 若存在 k 個整數 a_{1}, a_{2}, ..., a_{k} 使得 g_{1}(n) = a_{1}, g_{2}(n) = a_{2}, ..., g_{k}(n) = a_{k}, 那麼 f(n) = \sum \limits_{i = 1}^{k}g_{i}(n)f(n - i) + g(n) 可以展開為 \displaystyle {f(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n). \ \ \ \ \ \ \ \ \ \ (\mathrm {II})} 其中, a_{k} \neq 0 且 n \geq k. 當 g(n) = 0 時, 稱 f(n) 為齊次線性遞迴方程式 (homogeneous recurrence); 當 g(n) \neq 0 時, 稱 f(n) 為非齊次線性遞迴方程式 (non-homogeneous recurrence).

實際上, (\mathrm {II}) 式就是分而治之演算法 (《分而治之演算法》) 時間複雜度的一種表達. 這裡, 我們採用的方式是一分為 k.

對於 \displaystyle {f(n) = \begin {cases} c_{1} ^{n = 1} \\ 2f \left ( \frac {n}{2} \right ) + c_{2}n & {n \geq 2} \end {cases}, \text {其中 } \log_{2}{n} \text { 為整數}}. 由於線性遞迴方程式要求右側的 f 為 f(n - i) 的形式, i = 1, 2, ..., k. 而上述遞迴方程式中, f \left ( \frac {n}{2} \right ) 不滿足這樣的形式, 因此上述遞迴方程式不是線性遞迴方程式. 但因為 \log_{2}{n} 為整數, 因此 f(n) 可以寫為 \displaystyle {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}), 則有 \displaystyle {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 的值, 我們稱 (\mathrm {I}) 式為 k 階線性遞迴方程式 (linear recurrence of order k). 因此 h(k) 是一個一階線性遞迴方程式. 其中, g_{1}(k) = 2 且 g(k) = c_{2}2^{k}. h(k) 是一個一階非齊次線性遞迴方程式.

再考慮 \displaystyle {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 時, \displaystyle {T(n) = \frac {2}{n}\sum \limits_{i = 1}^{n - 1}T(i) + c_{2}n. \ \ \ \ \ \ \ \ \ \ (\mathrm {III})} 等式兩側同時乘以 n, 可得 nT(n) = 2\sum \limits_{i = 1}^{n - 1}T(i) + c_{2}n^{2}. 使用 n - 1 替換 n, 有 \displaystyle {(n - 1)T(n - 1) = 2\sum \limits_{i = 1}^{n - 2}T(i) + c_{2}(n - 1)^{2}. \ \ \ \ \ \ \ \ \ \ (\mathrm {IV})} 使用 (\mathrm {III}) 式減去 (\mathrm {IV}) 式, 得 \displaystyle {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}}. 展開之後有 \displaystyle {nT(n) - nT(n - 1) + T(n - 1) = 2T(n - 1) + c_{2}(2n - 1)}. 移項得 \displaystyle {nT(n) = (n + 1)T(n - 1) + c_{2}(2n - 1)}. 等式兩側同時乘以 \frac {1}{n}, 最終可得 \displaystyle {T(n) = \frac {n + 1}{n}T(n - 1) + c_{2}\left ( 2 - \frac {1}{n} \right )}. 不難看出, T(n) 是一個一階非齊次線性遞迴方程式. 其中, g_{1}(n) = \frac {n + 1}{n}, g(n) = c_{2}\left ( 2 - \frac {1}{n} \right ).

2. 特徵根法

對於函數 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) 可以表示為 \displaystyle {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} 的值.

在代數學中我們知道, 對於非齊次線性遞迴方程式 \displaystyle {f(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n)} 的解是其對應的齊次線性遞迴方程式的通解 \displaystyle {f_{h}(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) \ \ \ \ \ \ \ \ \ \ (\mathrm {V})} 再加上一個非齊次線性遞迴方程式的一個特解 \displaystyle {f_{p}(n) = a_{1}f(n - 1) + a_{2}f(n - 2) + ... + a_{k}f(n - k) + g(n). \ \ \ \ \ \ \ \ \ \ (\mathrm {VI})} 即 f(n) 的通解可以表示為 f_{h}(n) + f_{p}(n).

為了確定 f_{h}(n), 我們首先對 (V) 式進行移項, 得 \displaystyle {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. 將解代入上述方程式, 可以得到 \displaystyle {Ax^{n} - a_{1}Ax^{n - 1} - a_{2}Ax^{n - 2} - ... - a_{k}Ax^{n - k} = 0} 等式兩側同時乘以 \frac {1}{A} 並提取 x^{n - k} 可得到 \displaystyle {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}\left ( x^{k} - \sum \limits_{i = 1}^{k}a_{i}x^{k - 1} \right ) = 0. 顯然這個方程式有 n 個根, 其中有 n - k 個根是 0, 剩下 k 個根取決於 \displaystyle {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) 的特徵方程式 \displaystyle {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) 可以表示為 \displaystyle {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. 解二階齊次線性遞迴方程式 \displaystyle {F(n) = \begin {cases} 0 & {n = 0} \\ 1 & {n = 1} \\ F(n - 1) + F(n - 2) & {n > 1}. \end {cases}} 這個遞迴方程式是非常有名的費氏數列 (Fibonacci number sequence).

解 :

設其通解為 F_{h}(n) = Ax^{n}, 其中 A \neq 0, 將 F_{h}(n) 代入上式得到其特徵方程式 \displaystyle {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. 故 \displaystyle {u_{1}(n) = c_{1}\left ( -\frac {\sqrt {5}}{2} + \frac {1}{2} \right )^{n}, u_{2}(n) = c_{2}\left ( \frac {\sqrt {5}}{2} + \frac {1}{2} \right )^{n}}. 因此, F(n) = F(n - 1) + F(n - 2) 的通解為 \displaystyle {F_{h}(n) = u_{1}(n) + u_{2}(n) = c_{1}\left ( -\frac {\sqrt {5}}{2} + \frac {1}{2} \right )^{n} + c_{2}\left ( \frac {\sqrt {5}}{2} + \frac {1}{2} \right )^{n}}. 考慮 F(0) = 0, F(1) = 1, 得到一個方程式組並解這個方程式組可以得到 \displaystyle {\begin {cases} F(0) = c_{1} + c_{2} = 0 \\ F(1) = c_{1}\left ( -\frac {\sqrt {5}}{2} + \frac {1}{2} \right ) + c_{2}\left ( \frac {\sqrt {5}}{2} + \frac {1}{2} \right ) = 1, \end {cases} \ \ \ \Rightarrow \ \ \ \begin {cases} c_{1} = -\frac {1}{\sqrt {5}} \\ c_{2} = \frac {1}{\sqrt{5}}. \end {cases}}

故費氏數列的通項公式可以表示為 \displaystyle {F(n) = \frac {1}{\sqrt {5}}\left ( \frac {1 + \sqrt {5}}{2} \right )^{n} - \frac {1}{\sqrt {5}}\left ( \frac {1 - \sqrt {5}}{2} \right )^{n}}

\blacksquare

目前, 我們僅得到了齊次線性遞迴方程式的求解方法, 對於 g(n) \neq 0 的情況, 我們還需要得到一個特解 f_{p}(n). 對於任意 g(n) = 0, 目前還沒有一個適用於任意 g(n) 的特解 f_{p}(n). f_{p}(n) 的形式取決於 g(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) 有如下形式 \displaystyle {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) 中, 得到 \displaystyle {\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}, 其中 a 與 c 為任意常數, a > 0, 那麼特解 f_{p}(n) 有如下形式 \displaystyle {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} 的值即可.

自此, 我們得到了使用特徵根法來求解遞迴方程式的過程. 對於線性遞迴方程式 \displaystyle {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), 寫下其特徵方程式 \displaystyle {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), 並令 \displaystyle {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. 考慮 g(n) :
   • 若 g(n) = 0, 則 \displaystyle {f_{p}(n) = 0};
   • 若 g(n) = \sum \limits_{i = 1}^{d}e_{i}n^{i}, 其中 e_{d} \neq 0, e_{i} (i = 1, 2, ..., d) 為任意常數. 則 \displaystyle {f_{p}(n) = p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{d + m}n^{d + m}};
   • 若 g(n) = ca^{n}, 其中 a 與 c 為任意常數, a > 0, 則 \displaystyle {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) 的解為 \displaystyle {f(n) = f_{h}(n) + f_{p}(n)}.

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

斷言 1. 通過特徵根法的七個步驟找到的 f(n) = f_{h}(n) + f_{p}(n) 是線性遞迴方程式 f(n) 的惟一解.

這個斷言我們暫時不進行證明.

3. 一些非線性情形

某些非線性遞迴方程式也可以通過適當的變換, 將其轉化為線性遞迴方程式, 再利用特徵根法進行求解. 考慮 \displaystyle {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), 則有 \displaystyle {q(n) = \sum \limits_{i = 1}^{k}a_{i}q(n - i) + g(n)}. 此時, 非線性的 f^{c}(n) 就轉化為了線性的 q(n).

另外, 某些線性遞迴方程式可能具有非恆定的係數 : \displaystyle {nf(n) = \sum \limits_{i = 1}^{k}a_{i}f(n - i) + g(n)}, 其中 n \geq k. 我們無法直接使用特徵根法進行求解, 但也可以作適當的變換, 使其具有恆定係數. 記 q(n) = nf(n), 則有 \displaystyle {q(n) = \sum \limits_{i = 1}^{k}a_{i}q(n - i) + g(n)}. 在這樣的情況下, 我們得到的是關於 q(n) 的通解, 此時只需將 q(n) 使用 f(n) 進行替換, 即可得到原遞迴方程式的通解.