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

Recurrence Relation

考慮數列

$a_0,a_1,\cdots ,a_n$ ，如果

$a_n$ 可以用之前的若干項表示，則稱此種表達式為遞迴關係式

用數學歸納法證明

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

例如知名的 Ackerman's function:

$$\{\begin{array}{ll}\mathrm{Ack}(0,n)=& n+1\\ \mathrm{Ack}(m,0)=& \mathrm{Ack}(m-1,1),& m>0\\ \mathrm{Ack}(m,n)=& \mathrm{Ack}(m-1,\mathrm{Ack}(m,n-1)),& m,n>0\end{array}$$

Show

$\mathrm{\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$ 原式亦成立
故由數學歸納法知，

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

---

Suppose that

$a_{m,n}$ is defined recursively by

$a_{m,n}=\{\begin{array}{ll}0& \text{ if }n=0,m=0\\ a_{m-1,n}+1& \text{ if }n=0,m>0\\ a_{m,n-1}+n& \text{ if }n>0\end{array}$. Show that

$a_{m,n}=m+n(n+1)/2,\mathrm{\forall }(m,n)\in \mathbb{N}\times \mathbb{N}$.

Sol:

對

$\mathbb{N}\times \mathbb{N}$ 中所有有序對依字典順序排序，而對

$(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>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,\mathrm{\forall }(m,n)\in \mathbb{N}\times \mathbb{N}$

代入求解大法

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

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

例如：

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

$T(1)=1$

Sol:

$$\begin{array}{rl}T(n)=& 2(2T(n-2)+1)+1\\ =& 2^{2}T(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{array}$$

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

$T(1)=0$

Sol:

$$\begin{array}{rl}T(n)=& 2^{2}T(\frac{n}{2^2})+2n\\ =& 2^{k}T(\frac{n}{2^k})+kn\end{array}$$

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{array}{lll}{a}_0=& c_1+c_2& =1\\ a_1=& 3c_1-c_2& =1\end{array}$$

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

$$a_n=\frac{1}{2}[3^n+(-1{)}^n],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_{2}n{3}^n$

$$\{\begin{array}{lll}{a}_0=& c_1& =5\\ a_1=& 3c_1+3c_2& =12\end{array}$$

$$\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{array}{lll}{a}_0=& B_1& =1\\ a_1=& \sqrt{2}(\frac{-B_1}{\sqrt{2}}+\frac{B_2}{\sqrt{2}})& =1\end{array}$$

$$\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_1{a}_{n-1}+\cdots c_k{a}_{n-k}=f(n),c_k\ne 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_{1}n+\cdots d_t{n}^t$	若有 $s$ 個特徵根為 $1$ ，修正為 $(d_0+d_{1}n+\cdots d_t{n}^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_{0}n-4d_0(n-1)+3d_0(n-2)=4,d_0=-2$$

故

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

$$\{\begin{array}{lll}{a}_1=& c_1+3c_2-2& =-9\\ a_2=& c_1+9c_2-4& =-5\end{array}$$

$$\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 _{i=0}^{\mathrm{\infty }}{x}^i,\left|x\right|<1$

$(1+x{)}^{-n}=\sum _{r=0}^{\mathrm{\infty }}(\genfrac{}{}{0ex}{}{-n}{r})x^r=\sum _{r=0}^{\mathrm{\infty }}(-1{)}^r(\genfrac{}{}{0ex}{}{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{array}{lll}{a}_0=& c_1+c_2& =1\\ a_1=& 3c_1+5c_2& =6\end{array}$$

所以我們搶先算出了

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

接著才是用生成函數開始計算，首先我們要把原式變成

$\sum _{n=?}^{\mathrm{\infty }}{a}_n{x}^n$ 的模樣

原式是

$a_{n+2}-8a_{n+1}+15a_n=0$
所以寫成

$\sum _{n=0}^{\mathrm{\infty }}{a}_{n+2}\cdot x^n-8\cdot \sum _{n=0}^{\mathrm{\infty }}{a}_{n+1}\cdot x^n+15\cdot \sum _{n=0}^{\mathrm{\infty }}{a}_n\cdot x^n=0$

可以看到係數的部分還沒都是

$a_n$，接著我們要對

$\sum$ 的 index 動手腳 使得每個係數都能寫成

$a_n$ 的模樣：

$$\begin{array}{rl}& \sum _{n=0}^{\mathrm{\infty }}{a}_{n+2}\cdot x^n-8\cdot \sum _{n=0}^{\mathrm{\infty }}{a}_{n+1}\cdot x^n+15\cdot \sum _{n=0}^{\mathrm{\infty }}{a}_n\cdot x^n=0\\ \Rightarrow & \sum _{n=2}^{\mathrm{\infty }}{a}_n\cdot x^n-8\cdot \sum _{n=2}^{\mathrm{\infty }}{a}_{n-1}\cdot x^n+15\cdot \sum _{n=2}^{\mathrm{\infty }}{a}_{n-2}\cdot x^n=0\\ \Rightarrow & \sum _{n=2}^{\mathrm{\infty }}{a}_n\cdot x^n-8x\cdot \sum _{n=1}^{\mathrm{\infty }}{a}_n\cdot x^n+15x^2\cdot \sum _{n=0}^{\mathrm{\infty }}{a}_n\cdot x^n=0\\ \Rightarrow & (1-8x+15x^2)\sum _{n=0}^{\mathrm{\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 _{n=0}^{\mathrm{\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 _{n=0}^{\mathrm{\infty }}{a}_n\cdot x^n=\frac{1}{2}[-\sum _{i=0}^{\mathrm{\infty }}(3x{)}^i+3\sum _{i=0}^{\mathrm{\infty }}(5x{)}^i]\end{array}$$

比對等號左右兩邊的係數，便可得

$a_n=\frac{1}{2}(-3^n+3\cdot 5^n),n\ge 0$
回去看一下事先算好的答案，我們算對了

可以看到，生成函數的算法很考驗你的細心，還有熟不熟悉生成函數
基本上是建議可以直接把原式寫成

$a_n-8a_{n-1}+15a_{n-2}=0$
然後就能跳到上面計算過程的第二步：

$\sum _{n=2}^{\mathrm{\infty }}{a}_n\cdot x^n-8\cdot \sum _{n=2}^{\mathrm{\infty }}{a}_{n-1}\cdot x^n+15\cdot \sum _{n=2}^{\mathrm{\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}),\mathrm{\forall }n\ge 3$,

$D_1=0,D_2=1$

考慮任一數

$i$ (

$1\le i\le n$) 放置到位置

$j$ (

$i\ne 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 _{n=0}^{\mathrm{\infty }}\frac{D_n{x}^n}{n!}$, then

$f(x)=\frac{e^{-x}}{1-x}$

根據

$D_n=(n-1)(D_{n-1}+D_{n-2})$ 得

$D_n-n{D}_{n-1}=(-1)[D_{n-1}-(n-1)D_{n-2}]=(-1{)}^{n-2}(D_2-2D_1)=(-1{)}^{n-2}=(-1{)}^n$

(用代入大法)

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

$$D_n-n{D}_{n-1}=(-1{)}^n$$

$$\begin{array}{rl}& \sum _{n=1}^{\mathrm{\infty }}\frac{D_n}{n!}{x}^n-n\cdot \sum _{n=1}^{\mathrm{\infty }}\frac{D_{n-1}}{n!}{x}^n=\sum _{n=1}^{\mathrm{\infty }}\frac{(-1{)}^n}{n!}{x}^n\\ \Rightarrow & \sum _{n=1}^{\mathrm{\infty }}\frac{D_n}{n!}{x}^n-x\cdot \sum _{n=0}^{\mathrm{\infty }}\frac{D_n}{n!}{x}^n=\sum _{n=1}^{\mathrm{\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{array}$$

(3)

$D_n$ 通解？

$$\begin{array}{rl}f(x)& =\sum _{n=0}^{\mathrm{\infty }}\frac{D_n{x}^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 _{n=0}^{\mathrm{\infty }}(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1{)}^n}{n!})x^n\\ \therefore D_n& =n!(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1{)}^n}{n!})\end{array}$$

應用問題

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 有講過要怎麼想出遞迴關係式，不過我沒有說明 Catalan number 怎麼從遞迴關係式解出通解

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

至於各種姿勢的 Catalan number 證法可以參考wiki

Fibonacci Number

費氏數，老朋友了吧，用特徵函數能求出

$F_n=\frac{1}{\sqrt{5}}({\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n)$
這數字應該要很熟悉了

其中

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

$\phi$)

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

有些題目呢，看起來無關但其實就是費氏數
例如著名的爬樓梯問題(LeetCode 上有一題，你可以點開此連結來寫)

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$

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