考研相關文章參考資料為 wjungle 大神提供的筆記

L5 遞迴關係

L5-2 常係數線性遞迴

定義

若數列 $(a_n)$ 滿足 $c_0a_n+c_1a_{n-1}+\cdots+c_ka_{n-k}=f(n)$

其中 $c_0,c_1,\ldots,c_k$ 為常數，且 $c_0\ne0$ ， $c_k\ne0$ ，則稱為 $k$ 階常係數線性遞迴關係。

求 $a_n$ 時，需給定前 $k$ 項初始值。
當 $f(n)=0$ 時，稱為 homogeneous (齊次) 遞迴關係。
當 $f(n)\ne0$ 時，稱為 nonhomogeneous (非齊次) 遞迴關係。

齊次解

方法

對齊次遞迴關係，設 $a_n=A\alpha^n$ ，代入 $c_0a_n+c_1a_{n-1}+\cdots+c_ka_{n-k}=0$

可得 $A\alpha^{n-k}(c_0\alpha^k+c_1\alpha^{k-1}+\cdots+c_k)=0$

因此特徵方程為 $c_0\alpha^k+c_1\alpha^{k-1}+\cdots+c_k=0$
其根的重數總和為 $k$ 。

相異根

若特徵方程有 $k$ 個相異根 $\alpha_1,\alpha_2,\ldots,\alpha_k$ ，則

$a_n=d_1\alpha_1^n+d_2\alpha_2^n+\cdots+d_k\alpha_k^n$

其中 $d_1,d_2,\ldots,d_k$ 由前 $k$ 項初始值決定。

重根

若相異根為 $\alpha_1,\alpha_2,\ldots,\alpha_r$ ，且 $\alpha_i$ 的重數為 $m_i$ ，則

$a_n=\sum_{i=1}^{r}\left(d_{i,0}+d_{i,1}n+\cdots+d_{i,m_i-1}n^{m_i-1}\right)\alpha_i^n$

其中 $m_1+m_2+\cdots+m_r=k$ ，所有常數由前 $k$ 項初始值決定。重複 $m$ 次的根會額外乘上 $1,n,\ldots,n^{m-1}$ 。

共軛複根

若特徵方程有一對共軛複根
$\alpha_1=\delta+i\omega,\quad \alpha_2=\delta-i\omega,\quad \omega\ne0$

令 $\rho=\sqrt{\delta^2+\omega^2}$ ，並令 $\alpha_1=\rho e^{i\theta}$ 、 $\alpha_2=\rho e^{-i\theta}$ 。由 Euler 公式可得實數通解

$a_n=\rho^n\left(B_1\cos(n\theta)+B_2\sin(n\theta)\right)$
其中 $B_1,B_2$ 由初始值決定。

非齊次解

非齊次遞迴關係的通解為 $a_n=a_n^{(h)}+a_n^{(p)}$

其中 $a_n^{(h)}$ 為對應齊次遞迴關係的通解， $a_n^{(p)}$ 為與 $f(n)$ 有關的一個特解。

多項式

若 $f(n)=C_0+C_1n+\cdots+C_mn^m,\quad C_m\ne0$

則可設特解為 $a_n^{(p)}=n^r\left(d_0+d_1n+\cdots+d_mn^m\right)$

其中 $r$ 為特徵方程中根 $1$ 的重數；若 $1$ 不是特徵根，則 $r=0$ 。將此式代回原遞迴關係，可解出 $d_0,d_1,\ldots,d_m$ 。

指數型式取 $\alpha=1$ 的特例

指數

若 $f(n)=\left(C_0+C_1n+\cdots+C_mn^m\right)\alpha^n,\quad C_m\ne0$

則可設特解為 $a_n^{(p)}=n^r\left(d_0+d_1n+\cdots+d_mn^m\right)\alpha^n$

其中 $r$ 為特徵方程中根 $\alpha$ 的重數；若 $\alpha$ 不是特徵根，則 $r=0$ 。將此式代回原遞迴關係，可解出 $d_0,d_1,\ldots,d_m$ 。

三角函數

若 $f(n)=C_1\rho^n\cos(n\theta)\quad\text{或}\quad f(n)=C_2\rho^n\sin(n\theta)$

則可設特解為 $a_n^{(p)}=n^r\rho^n\left(B_1\cos(n\theta)+B_2\sin(n\theta)\right)$

其中 $r$ 為特徵方程中 $\rho e^{i\theta}$ 與 $\rho e^{-i\theta}$ 的重數；若兩者皆非特徵根，則 $r=0$ 。

Note

求非齊次解流程:

求對應齊次遞迴關係的特徵方程根 $\alpha$ ，並判斷相關根的重數 $r$ 。
依 $f(n)$ 的型式設特解 $a_n^{(p)}$ ，將其代入原遞迴關係，求出特解中的待定係數。
組合 $a_n=a_n^{(h)}+a_n^{(p)}$ ，再代入前 $k$ 項初始值，求出齊次解 $a_n^{(h)}$ 的係數。

L5-4 生成函數法

Note

令數列 $(a_n)$ 的 GF 為 $A(x)=a_0+a_1x+a_2x^2+\cdots=\sum_{n=0}^{\infty}a_nx^n$

調整求和下標時，可先以 $x$ 的冪次配合數列下標做位移。

$a_n$ 型
- $\sum_{n=1}^{\infty}a_nx^n=A(x)-a_0$
- $\sum_{n=2}^{\infty}a_nx^n=A(x)-a_0-a_1x$
$a_{n-1}$ 型
- $\sum_{n=1}^{\infty}a_{n-1}x^n=xA(x)$
- $\sum_{n=2}^{\infty}a_{n-1}x^n=x\left(A(x)-a_0\right)$
$a_{n-2}$ 型
- $\sum_{n=2}^{\infty}a_{n-2}x^n=x^2A(x)$
- $\sum_{n=3}^{\infty}a_{n-2}x^n=x^2\left(A(x)-a_0\right)$

範例

L5-5 應用問題

範例

L5-6 特殊型遞迴

定理

設 $(a_n)$ 、 $(b_n)$ 為兩數列，定義

$c_n=(a\otimes b)_n=\sum_{k=0}^{n}a_kb_{n-k}$

稱數列 $(c_n)$ 為 $(a_n)$ 與 $(b_n)$ 的 convolution (卷積)。

Note

若 $(a_n)$ 、 $(b_n)$ 、 $(c_n)$ 的 GF 分別為 $A(x)$ 、 $B(x)$ 、 $C(x)$ ，且 $c_n=(a\otimes b)_n$ ，則 $C(x)=A(x)B(x)$

若 $c_n=(a\otimes a)_n$ ，則 $C(x)=A(x)^2$ 。

Catalan 數

範例

求有 $n$ 個節點的 binary ordered tree (二元有序樹) 數量。

其數量為第 $n$ 個 Catalan 數，記為 $C_n$ ，具有下列兩種表現形式:

$C_0=1,\quad C_n=\sum_{k=0}^{n-1}C_kC_{n-k-1}\quad(n\ge1)$

$C_n=\frac{1}{n+1}\binom{2n}{n}$

Note

Catalan 數遞迴式的索引平移:

若 $a_0=1$ ，且 $\displaystyle a_n=\sum_{k=0}^{n-1}a_ka_{n-k-1}$ ，則 $a_n=C_n$ 。
若 $a_1=1$ ，且 $\displaystyle a_n=\sum_{k=1}^{n-1}a_ka_{n-k}$ ，則 $a_n=C_{n-1}$ 。
若 $a_2=1$ ，且 $\displaystyle a_n=\sum_{k=2}^{n-1}a_ka_{n+1-k}$ ，則 $a_n=C_{n-2}$ 。