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

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)$ 進行替換, 即可得到原遞迴方程式的通解.