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

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

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

$f(n) = \begin {cases} c_{1} ^{n = 1} \\ 2f(\frac {n}{2}) + c_{2}n & {n \geq 2} \end {cases}, 其中\ \log_{2}{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}$

$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}$

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

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

$(n - 1)T(n - 1) = 2\sum \limits_{i = 1}^{n - 2}T(i) + c_{2}(n - 1)^{2}\ \ \ \ \ \ \ \ \ \ (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)$

$T(n) = \frac {n + 1}{n}T(n - 1) + 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) = \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_{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) - a_{1}f(n - 1) - a_{2}f(n - 2) - ... - a_{k}f(n - k) = 0$

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

$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$

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

$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$

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

$解$ :

$x^{2} - x - 1 = 0$

$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_{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}$

$\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$

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

\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}

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

$f_{p}(n) = (p_{0} + p_{1}n + p_{2}n^{2} + ... + p_{w}n^{w})a^{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}$

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)$

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}$

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

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

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)$

$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$

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

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