# 【資工考研】離散：遞迴關係式與其求解

## Recurrence Relation

考慮數列 $a_0,a_1,\cdots ,a_n$ ，如果 $a_n$ 可以用之前的若干項表示，則稱此種表達式為遞迴關係式

## 用數學歸納法證明

通常是題目給定了遞迴關係式，我們要證明該通解是正確的

例如知名的 Ackerman's function:

$$\begin{cases}
\mathrm{Ack}(0,n) =& n+1 \\
\mathrm{Ack}(m,0) =& \mathrm{Ack}(m-1,1), &m\gt 0 \\
\mathrm{Ack}(m,n) =& \mathrm{Ack}(m-1,\mathrm{Ack}(m,n-1)), &m,n\gt 0
\end{cases}$$

> Show $\forall n\in\mathbb{N}, \mathrm{Ack}(1,n) = n+2$.

Sol:

當 $n = 0$ 時， $\mathrm{Ack}(1,0) = \mathrm{Ack}(0,1) = 1+1 = 2 = 0+2$ ，原式成立
設 $n = k\ge 0$ 時原式成立
則 $n = k+1$ 時， $\mathrm{Ack}(1,k+1) = \mathrm{Ack}(0,\mathrm{Ack}(1,k)) = \mathrm{Ack}(0,k+2) =k+3 = (k+1)+2$ 原式亦成立
故由數學歸納法知， $\forall n\in\mathbb{N}, \mathrm{Ack}(1,n) = n+2$

***

> Suppose that $a_{m,n}$ is defined recursively by $a_{m,n} = \begin{cases}
0 &\text{ if } n=0,m=0 \\
a_{m-1,n}+1 &\text{ if } n=0,m\gt 0 \\
a_{m,n-1}+n &\text{ if } n\gt 0
\end{cases}$. Show that $a_{m,n} = m+n(n+1)/2, \forall (m,n)\in\mathbb{N}\times\mathbb{N}$.

Sol:

對 $\mathbb{N}\times\mathbb{N}$ 中所有有序對依[字典順序](https://hackmd.io/@RyoukiWei/binary-relation#Lexicographic-Ordering)排序，而對 $(m,n)$ 做歸納
當 $(m,n) = (0,0)$ 時， $a_{m,n} = a_{0,0} = 0 = 0+0(0+1)/2$ ，原式成立

假設排在 $(m,n)$ 前的有序對皆使題目敘述成立
則對 $(m,n)$, 如果 $n= 0$ 則因為 $(m-1, n)$ 排在 $(m,n)$ 前，故 $a_{m,n} = a_{m-1,n}+1 = m-1+n(n+1)/2+1 = m+n(n+1)/2$ ；
若 $n\gt 0$ 則因為 $(m,n-1)$ 排在 $(m,n)$ 前，故 $a_{m,n} = a_{m,n-1}+n = m+(n-1)n/2+n = m+n(n+1)/2$

故由數學歸納法知， $a_{m,n} = m+n(n+1)/2, \forall (m,n)\in\mathbb{N}\times\mathbb{N}$

## 代入求解大法

由規律性來求出整體通解，在解遞迴演算法的時間複雜度時，是相當常用的技巧

通常代個幾項就能看出規律了

例如：

> $T(n) = 2T(n-1) + 1$, $T(1) = 1$

Sol:

$$
\begin{equation}
\begin{split}
T(n) =& 2(2T(n-2)+1) + 1 \\
=& 2^2T(n-2) + 2 +1 \\
=& 2^{n-1}T(1)+ 2^{n-2}+\cdots +2+1 \\
=& 2^{n-1} + 2^{n-1} - 1 \\
=& \theta(2^n)
\end{split}
\end{equation}
$$

> $T(n) = 2T(\frac{n}{2})+n$, $T(1) = 0$

Sol:

$$
\begin{equation}
\begin{split}
T(n) =& 2^2T(\frac{n}{2^2}) + 2n \\
=& 2^kT(\frac{n}{2^k}) + kn
\end{split}
\end{equation}
$$

Let $n = 2^k, k = \lg n$

$$
\therefore T(n) = n\lg n = \theta (n\lg n)
$$

## 特徵多項式

### 齊次 + 相異特徵根

若有 $\alpha_1, \cdots \alpha_r$ 為相異特徵根，則通解 $a_n = c_1\alpha_1^n + \cdots +c_r\alpha_r^n$

例如：

> $a_n = 2a_{n-1} + 3_{n-2}, n\ge 2$, $a_0 = 1,a_1 = 1$

特徵式： $\alpha^2 - 2\alpha -3 = 0$, $\alpha = 3$ or $-1$

Let $a_n = c_1 3^n + c_2 (-1)^n$

$$
\begin{cases}
a_0 =& c_1 + c_2 &= 1 \\
a_1 =& 3c_1 - c_2 &= 1
\end{cases}
$$

$$
\therefore c_1 = \frac{1}{2}, c_2 = \frac{1}{2}
$$

$$
a_n = \frac{1}{2}\lbrack 3^n + (-1)^n \rbrack, n\ge 0
$$

### 齊次 + 有重根

假設 $\alpha_1$ 解出有 $m_1$ 個，那就要修正成 $c_1\alpha_1^n + c_2 n\alpha_1^n + \cdots c_{m_1}n^{m_1-1}\alpha_1^n$

這是為了防止同類項合併

例如：

> $a_n-6a_{n-1}+9a_{n-2} = 0, n\ge 2$, $a_0=5,a_1=12$

解出特徵根： $3, 3$

Let $a_n = c_1 3^n + c_2n3^n$

$$
\begin{cases}
a_0 =& c_1 &= 5 \\
a_1 =& 3c_1 + 3c_2 &= 12
\end{cases}
$$

$$
\therefore c_1 = 5, c_2 = -1
$$

$$
a_n = 5\cdot 3^n - n\cdot 3^n, n\ge 0
$$

### 齊次 + 複數根

如果解出複數根如 $\alpha\pm\beta i$ ，則令 $a_n = \rho ^n (B_1 \cos\theta + B_2\sin\theta)$ ，其中 $\rho = \sqrt{\alpha^2 + \beta^2}$ 、$\cos\theta = \frac{\alpha}{\rho}, \sin\theta = \frac{\beta}{\rho}$

例如：

> $a_n + 2a_{n-1} + 2a_{n-2} = 0, n\ge 2$, $a_0=a_1=1$

解出特徵根為 $-1\pm i$

Let $a_n = (\sqrt{2})^n(B_1\cos\frac{3n\pi}{4} + B_2\sin\frac{3n\pi}{4})$

$$
\begin{cases}
a_0 =& B_1 &= 1 \\
a_1 =& \sqrt{2}(\frac{-B_1}{\sqrt{2}} + \frac{B_2}{\sqrt{2}}) &= 1
\end{cases}
$$

$$
\therefore B_1 = 1, B_2 = 2
$$

$$
a_n = (\sqrt{2})^n(\cos\frac{3n\pi}{4} + 2\sin\frac{3n\pi}{4}), n\ge 0
$$

### $k$ 階常係數線性非齊次

如果題目是長 $a_n + c_1a_{n-1} + \cdots c_ka_{n-k} = f(n), c_k\neq 0$

則通解 $a_n = a_n^{(h)} + a_n^{(p)}$ ，其中 $a_n^{(h)}$ 叫齊次解、 $a_n^{(p)}$ 為特殊解

$a_n^{(h)}$ 就是我們不看 $f(n)$ 把原式當齊次式，用上面的方法解出來的解
$a_n^{(p)}$ 則要看 $f(n)$ 的長相，求出 $a_n^{(p)}$ 的模樣後代回原式以解出其係數

|$f(n)$ 長相|$a_n^{(p)}$| 修正之注意事項 |
|:--:|:---:| :---: |
| $t$ 次多項式 | $d_0 + d_1n + \cdots d_tn^t$ | 若有 $s$ 個特徵根為 $1$ ，修正為 $(d_0 + d_1n + \cdots d_tn^t)\cdot n^s$ |
| 以 $b$ 為底的指數 | $d_0\cdot b^n$ | 若有 $s$ 個特徵根為 $b$ ，修正為 $(d_0\cdot b^n)\cdot n^s$ |
| 三角函數 | $d_0\cos n\theta + d_1\sin n\theta$ | |
| 上述情況之線性組合 | 上述之線性組合 | (遵照上面) |

這邊的修正也是防止同類項合併

例如：

> $a_n = 4a_{n-1}-3a_{n-2}+4, n\ge 3$, $a_1=-9,a_2=-5$

特徵根求出為 $1, 3$

齊次解令為 $a_n^{(h)} = c_1 1^n + c_2 3^n$
特殊解令為 $a_n^{(p)} = d_0 n$ (因為特徵根有 $1$) ，代回原式：

$$
d_0n - 4d_0(n-1) + 3d_0(n-2) = 4, d_0 = -2
$$

故 $a_n = c_1 1^n + c_2 3^n - 2n$

$$
\begin{cases}
a_1 =& c_1 + 3c_2 - 2 &= -9 \\
a_2 =& c_1 + 9c_2 - 4 &= -5
\end{cases}
$$

$$
\therefore c_1 = -10, c_2 = 1
$$

$$
a_n = -10 + 3^n - 2n, n\ge 1
$$

***

> $a_n = a_{n-1} + 2a_{n-2} + (-1)^n, n\ge 2$, $a_0=a_1=1$

特徵根為 $2,-1$

$a_n^{(p)} = d_0 (-1)^n n$ (因為有特徵根與 $f(n)$ 之底數相同)

$d_0$ 代回原式求出是 $\frac{1}{3}$

故 $a_n = c_1 2^n + c_2 (-1)^n + \frac{1}{3}n(-1)^n$

解出 $c_1 = \frac{7}{9}, c_2 = \frac{2}{9}$

## 生成函數

常見的一般生成函數要熟悉，例如 $\frac{1}{1-x} = \sum\limits_{i=0}^{\infty}x^i, \left| x \right|\lt 1$

$(1+x)^{-n} = \sum\limits_{r=0}^{\infty}\binom{-n}{r}x^r = \sum\limits_{r=0}^{\infty}(-1)^r\binom{n+r-1}{r}x^r$

一般來說，用生成函數解很佔計算空間，通常都是題目要求你要用生成函數解題才用，不然就用其他方法快速解
用生成函數算可能會出包，所以建議先用特徵方程之類的方法求出答案，再用生成函數寫計算過程，最後看看有沒有計算錯誤

例如：

> $a_{n+2}-8a_{n+1}+15a_n = 0, n\ge 0$, $a_0=1,a_1=6$

我們先偷算答案到底是多少

首先不難看出特徵根是 $3, 5$

$$
\begin{cases}
a_0 =& c_1 + c_2 &= 1 \\
a_1 =& 3c_1 + 5c_2 &= 6
\end{cases}
$$

所以我們搶先算出了 $a_n = \frac{1}{2}(-3^n + 3\cdot 5^n), n\ge 0$
我們這樣只需要花幾秒鐘

接著才是用生成函數開始計算，首先我們要把原式變成 $\sum\limits_{n=?}^{\infty}a_n x^n$ 的模樣

原式是 $a_{n+2}-8a_{n+1}+15a_n = 0$
所以寫成 $\sum\limits_{n=0}^{\infty}a_{n+2}\cdot x^n -8\cdot \sum\limits_{n=0}^{\infty}a_{n+1}\cdot x^n + 15\cdot \sum\limits_{n=0}^{\infty}a_{n}\cdot x^n = 0$

可以看到係數的部分還沒都是 $a_n$，接著我們要對 $\sum$ 的 index 動手腳 使得每個係數都能寫成 $a_n$ 的模樣：

$$
\begin{equation}
\begin{split}
&\sum\limits_{n=0}^{\infty}a_{n+2}\cdot x^n -8\cdot \sum\limits_{n=0}^{\infty}a_{n+1}\cdot x^n + 15\cdot \sum\limits_{n=0}^{\infty}a_{n}\cdot x^n = 0 \\
\Rightarrow &\sum\limits_{n=2}^{\infty}a_{n}\cdot x^n -8\cdot \sum\limits_{n=2}^{\infty}a_{n-1}\cdot x^n + 15\cdot \sum\limits_{n=2}^{\infty}a_{n-2}\cdot x^n = 0 \\
\Rightarrow &\sum\limits_{n=2}^{\infty}a_{n}\cdot x^n -8x\cdot \sum\limits_{n=1}^{\infty}a_{n}\cdot x^n + 15x^2\cdot \sum\limits_{n=0}^{\infty}a_{n}\cdot x^n = 0 \\
\Rightarrow &(1-8x+15x^2)\sum\limits_{n=0}^{\infty}a_{n}\cdot x^n - (a_0\cdot x^0 + a_1\cdot x^1) - (-8x\cdot a_0\cdot x^0) = 0 \\
\Rightarrow &\sum\limits_{n=0}^{\infty}a_{n}\cdot x^n = \frac{(1-2x)}{(1-8x+15x^2)} = \frac{-\frac{1}{2}}{1-3x} + \frac{\frac{3}{2}}{1-5x} \text{ (把 } a_0 \text{ 跟 } a_1 \text{ 的值代入，轉成熟悉的生成函數)} \\
\Rightarrow &\sum\limits_{n=0}^{\infty}a_{n}\cdot x^n = \frac{1}{2}\lbrack -\sum\limits_{i=0}^{\infty}(3x)^i + 3\sum\limits_{i=0}^{\infty} (5x)^i\rbrack
\end{split}
\end{equation}
$$

比對等號左右兩邊的係數，便可得 $a_n = \frac{1}{2}(-3^n + 3\cdot 5^n), n\ge 0$
回去看一下事先算好的答案，我們算對了

可以看到，生成函數的算法很考驗你的細心，還有熟不熟悉生成函數
基本上是建議可以直接把原式寫成 $a_n-8a_{n-1}+15a_{n-2} = 0$
然後就能跳到上面計算過程的第二步： $\sum\limits_{n=2}^{\infty}a_{n}\cdot x^n -8\cdot \sum\limits_{n=2}^{\infty}a_{n-1}\cdot x^n + 15\cdot \sum\limits_{n=2}^{\infty}a_{n-2}\cdot x^n = 0$
省一步思考的功夫，其實會輕鬆一點

***

> 將 $n$ 個自然數 $1,2,\cdots ,n$ 排列使得 $k$ 不在第 $k$ 位 (亂序排列， Derangement) ，令其方法數為 $D_n$ 則

(1)

> $D_n = (n-1)(D_{n-1}+D_{n-2}), \forall n\ge 3$, $D_1=0,D_2 = 1$

考慮任一數 $i$ ($1\le i\le n$) 放置到位置 $j$ ($i\neq j$)
則 $D_n$ 可以分成兩種情況：

1. $j$ 放到位置 $i$
2. $j$ 不放到位置 $i$

以 1. 來說，代表我們只需要考慮剩下 $n-2$ 個數的亂序方法數，即 $D_{n-2}$
至於 2. 的情況，我們就需要考慮 $n-1$ 個數亂序的方法數，即 $D_{n-1}$

而對於數字 $i$ 總共有 $n-1$ 種 $j$ 可以選擇，故 $D_n = (n-1)(D_{n-1}+D_{n-2}), n\ge 3$

只有一個數字沒得亂序，故 $D_1 = 0$ ；兩個數字之亂序只會是兩數交換位置，故 $D_2 = 1$

(2)

> Let $f(x) = \sum\limits_{n=0}^{\infty}\frac{D_nx^n}{n!}$, then $f(x) = \frac{e^{-x}}{1-x}$

根據 $D_n = (n-1)(D_{n-1}+D_{n-2})$ 得 $D_n - nD_{n-1} = (-1)\lbrack D_{n-1}-(n-1)D_{n-2}\rbrack = (-1)^{n-2}(D_2-2D_1) = (-1)^{n-2} = (-1)^n$

(用代入大法)

接著我們對上式使用生成函數法解題：

$$
D_n - nD_{n-1} = (-1)^n
$$

$$
\begin{equation}
\begin{split}
&\sum\limits_{n=1}^{\infty}\frac{D_n}{n!}x^n - n\cdot \sum\limits_{n=1}^{\infty}\frac{D_{n-1}}{n!}x^n = \sum\limits_{n=1}^{\infty}\frac{(-1)^n}{n!}x^n \\
\Rightarrow &\sum\limits_{n=1}^{\infty}\frac{D_n}{n!}x^n - x\cdot \sum\limits_{n=0}^{\infty}\frac{D_{n}}{n!}x^n = \sum\limits_{n=1}^{\infty}\frac{(-1)^n}{n!}x^n \\
\Rightarrow &(f(x) - D_0) - x\cdot f(x) = e^{-x} - 1 \\
\Rightarrow &f(x) = \frac{e^{-x} - 1 + D_0}{1-x} = \frac{e^{-x}}{1-x}
\end{split}
\end{equation}
$$

(3) $D_n$ 通解？

$$
\begin{equation}
\begin{split}
f(x) &= \sum\limits_{n=0}^{\infty}\frac{D_nx^n}{n!} = \frac{e^{-x}}{1-x} \\
&= (1-\frac{x}{1!}+\frac{x^2}{2!}-\frac{x^3}{3!}+\cdots)(1+x+x^2+x^3+\cdots) \\
&=\sum\limits_{n=0}^{\infty}\left( 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1)^n}{n!} \right)x^n \\
\therefore D_n &= n!\left( 1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1)^n}{n!} \right)
\end{split}
\end{equation}
$$

## 應用問題

1. The Tower of Hanoi ($a_n = 2^n-1$ for 3-tower)
2. 含偶數個 $0$ 的字串
3. 連 $0$ 的字串

字串型的問題，其實就是討論子字串開頭會是誰，進而構建出遞迴關係式
剩下就簡單了

子字串從原始字串開始討論

雖然看似純幹話，但遞迴應用問題基本上你想辦法構建出遞迴關係式，答案便呼之欲出了
通常就是你總覺得這問題有個模式可以重複遵循

解演算法的 DP 也是這樣子想出遞迴關係式的

## Catalan Number

我們很多東西的答案是 Catalan number ，例如 $n$ 節點的相異 binary tree 有 $C_n$ 種，即第 $n$ 個 Catalan number

我在[LeetCode 96. Unique Binary Search Trees](https://hackmd.io/@RyoukiWei/leetcode96?stext=697%3A276%3A0%3A1738526863%3ArgxPui) 有講過要怎麼想出遞迴關係式，不過我沒有說明 Catalan number 怎麼從遞迴關係式解出通解

其實呢，我們可以生成函數來解
這邊留給讀者思考怎麼求

至於各種姿勢的 Catalan number 證法可以參考[wiki](https://en.wikipedia.org/wiki/Catalan_number#Proof_of_the_formula)

## Fibonacci Number

費氏數，老朋友了吧，用特徵函數能求出 $F_n = \frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right)$
這數字應該要很熟悉了

其中 $\frac{1+\sqrt{5}}{2}$ 就是大名鼎鼎的黃金比例 ($\varphi$)

$$
\varphi^n = F_{n-1} + \varphi F_n
$$

有些題目呢，看起來無關但其實就是費氏數
例如著名的[爬樓梯問題(LeetCode 上有一題，你可以點開此連結來寫)](https://leetcode.com/problems/climbing-stairs/description/)

> You are climbing a staircase. It takes $n$ steps to reach the top.
>
> Each time you can either climb $1$ or $2$ steps. In how many distinct ways can you climb to the top?

設有 $a_n$ 種走法
分兩種情況討論：

1. 第一步走 $1$ 階樓梯：有 $a_{n-1}$ 種方式
2. 第二步走 $2$ 階樓梯：有 $a_{n-2}$ 種方式

故 $a_n = a_{n-1} + a_{n-2}, n\ge 3$, $a_1=1,a_2=2$

這不就老朋友嗎？
剩下不用我解了吧