递归关系
##递归关系的建立
定义 4.1 设 $(a_0,a_1,\dots,a_r,\dots)$ 是一个序列，把该序列中的 $a_r$ 和它前面几个 $a_i(0\leq i<r)$ 关联起来的方程，称为一个递归（递推）关系。
Fibonacci 兔子 问题
第 $n$ 个月时，兔子的总数应该是上个月就有的 $F_{n-1}$ 只，再加上新出生的 $F_{n-2}$ 只。
可以列出这样一个递推式：
$$
\begin{cases}
F_n=F_{n-1}+F_{n-2},&n\geq2\
F_0=1,F_1=1
\end{cases}
$$
Hanoi 塔 问题
设 $a_n$ 表示从一根柱子上的 $n$ 个圆盘全部转移到另一根柱子上的转移次数，则$a_1=1$。
考虑转移的方法：先把柱子 A 上的 $n-1$ 个圆盘转移到柱子 B 上，需要 $a_{n-1}$ 次，然后把柱子 A 上的最后一个大圆盘转移到柱子 C 上，最后再把柱子 B 上的 $n-1$ 个圆盘转移柱子 C 上，又需要 $a_{n-1}$ 次。则将 A 上的 $n$ 个圆盘全部转移到 C 上共需要 $2a_{n-1}+1$ 次。
这一递推关系也可以这样表示：
$$
\begin{cases}
a_n=2a_{n-1}+1,&n\geq2\
a_1=1
\end{cases}
$$
常系数线性其次递归关系
4.1 中的 Fibonacci 兔子 问题的递归是其实就是一个常系数线性其次递归关系。
定义 4.2 序列 $(a_0,a_1,\dots,a_n,\dots)$ 中相邻的 $k+1$ 项的关系若为
$$
a_n=b_1a_{n-2}+b_2a_{n-2}+\dots+b_ka_{n-k},\quad n\geq k\tag{4.1}
$$
则称 $(4.1)$ 为原序列的 $k$ 阶常数线性其次递归关系。其中 $b_i(i\in[1,k])$ 是常数，且 $b_k\neq0$ .
解这类递归关系可以利用特征根法。
####无重复特征根
定义 4.3 与式 $(4.1)$ 相联系的方程
$$
x^k-b_1x^{k-1}-b_2x^{k-2}-\dots-b_k=0 \tag{4.2}
$$
称作递归关系 $(4.1)$ 的特征方程，方程式 $(4.2)$ 的根称作递归关系式 $(4.1)$ 的特征根。
定理 4.1 若 $q\neq0,a_n=q^n$ 是递归关系式 $(4.1)$ 的解，当且仅当 $q$ 是特征方程式 $(4.2)$ 的根。
定义 4.4 称 $a_0=h_0,a_1=h_1,a_{k-1}=h_{k-1}$ ，是递归关系式 $(4.1)$ 的初始条件，其中 $h_i(i\in[1,k))$ 为常数。
####有重复特征根
定理 4.2 若 $q_1,q_2,\dots,q_k$ 是递归关系式 $(4.1)$ 的特征根，$c_1,c_2,\dots,c_k$ 是任意常数，则
$$
a_n=c_1q_1^n+c_2q_2^n+\dots+c_kq_k^n \tag{4.3}
$$
是递归关系式 $(4.1)$ 的解。
定义 4.5 若对递归关系式 $(4.1)$ 的任意一个解 $a_n$ 都存在一组适当的常数 $c_1,c_2,\dots,c_k$ 使得 $a_n$ 可以表示为是 $(4.3)$ 的形式，则称式 $(4.3) $ 是递归关系式 $4.1$ 的通解。
定理 4.3 若 $q_1,q_2,\dots,q_k$ 是递归关系式 $(4.1)$ 的互不相同的特征根，则式 $(4.3)$ 是递归方程式 $(4.1)$ 的通解。
Fibonacci 兔子 问题
有了上述的定义和定理，就可以轻松解决无重复特征根的递归问题了。
$$
\begin{cases}
F_n=F_{n-1}+F_{n-2},&n\geq2\
F_0=1,F_1=1
\end{cases}
$$
其特征方程为 $x^2-x-1=0$ c
解得：其特征根 $q_1=\frac{1+\sqrt 5}{2},q_2=\frac{1-\sqrt 5}{2}$ .
则其通解为 $F_n=c_1q_1^n+c_2q_2^n$
由其初始条件 $F_0=1,F_1=1$
解得：$c_1=\frac{\sqrt 5+1}{2\sqrt 5},c_2=\frac{\sqrt 5-1}{2\sqrt 5}$
故原递归关系式的解为 $$F_n=\frac{1}{\sqrt 5}\left[\left(\frac{1+\sqrt 5}{2}\right)^{n+1}-\left(\frac{1-\sqrt 5}{2}\right)^{n+1}\right]$$
定理 4.4 若递归关系式 $(4.1)$ 的特征方程式 $(4.2)$ 有一个 $m$ 重根 $q$ , 则 $q_n,nq^n,\dots,n^{m-1}q^n$ 都是递归关系式 $(4.1)$ 的通解。
定理 4.5 设 $q_1,q_2,\dots,q_t$ 分别是特征方程式 $(4.2)$ 相异的 $m_1,m_2,\dots,m_t$ 重根，且 $$\sum_{i=1}^tm_i=k$$ , 则
$$
a_n=\sum_{i=1}^t\sum_{j=1}^{m_i}c_{ij}n^{j-1}q_i^n \tag{4.4}
$$
是递归关系式 $(4.1)$ 的通解。
一道毒瘤题：
解递归关系式：$$\begin{cases}a_n=-a_{n-1}+3a_{n-2}+5a_{n-3}+2a_{n-4},&n\geq4\a_0=1,a_1=0,a_2=1,a_3=2\end{cases}$$
特征方程是： $x^4+x^3-3x^2-5x-2=0$
解得： $q_1=q_2=q_3=-1,q_4=2$
则 $a_n=c_1(-1)^n+c_2n(-1)^n+c_3n^2(-1)^n+c_42^n$
由初始条件 $a_0=1,a_1=0,a_2=1,a_3=2$ 得以下方程组：
$$
\left{\begin{align}&c_1+c_4=1\&-c_1-c_2-c_3+2c_4=0\&c_1+2c_2+4c_3+4c_4=1\&-c_1-3c_2-9c_3+8c_4=2\end{align}\right.
$$
解得： $c_1=\frac{7}{9},c_2=-\frac{1}{3},c_3=0,c_4=\frac{2}{9}$
所以 $$a_n=\frac{7}{9}(-1)^n-\frac{1}{3}n(-1)^n+\frac{2^{n+1}}{9}$$
###常系数线性非齐次递归关系
定义 4.6 序列 $(a_0,a_1,\dots,a_n,\dots)$ 中相邻的 $k+1$ 项之间的关系
$$
a_n=b_1a_{n-1}+b_2a_{n-2}+\dots+b_ka_{n-k}+f(n)\tag{4.5}
$$
称作序列 $(a_0,a_1,\dots,a_n,\dots)$ 的 $k$ 阶常系数现行非齐次递归关系。其中 $b_i(i\in[1,k])$ 是常数，且 $b_k\neq0$ .
定义 4.7 在式 $(4.5)$ 中，若 $f(n)=0$ ，则称
$$
a_n=b_1a{n-1}+b_2a{n-2}+\dots+b_ka_{n-k}\tag{4.6}
$$
为由式 $(4.5)$ 导出的常系数线性齐次递归关系。
之所以给出 定义 4.7 是因为想要解式 $(4.5)$ ，需要研究其导出的常系数线性齐次递归关系，具体的关系如下：
定理 4.6 若 $\bar{a}n$ 是式 $4.5$ 的一个特解，而 $a_n^*=\sum{i=1}^t\sum_{j=1}^{m_i}c_{ij}n^{j-1}q_i^n$ 是由式 $(4.5)$ 导出齐次线性递归关系的通解，则 $a_n=\bar{a}_n+a_n^*$ 是常系数非齐次线性递归关系式 $4.5$ 的通解。
$f(n)$ 是 $n$ 的 $t$ 次多项式
分为两种情况：
$1$ 不是式 $(4.6)$ 的特征根，此时递归关系式 $(4.5)$ 具有以下形式的特解：
$$
\bar{a}_n=A_0n^t+A_1n^{t-1}+\dots+A_t
$$$1$ 是式 $(4.6)$ 的 $m$ 特征重根 $m\geq1$，此时递归关系式 $(4.5)$ 具有以下形式的特解：
$$
\bar{a}_n=(A_0n^t+A_1n^{t-1}+\dots+A_t)n^m
$$
Hanoi 塔 问题
$$
\begin{cases}
a_n=2a_{n-1}+1,&n\geq2\
a_1=1
\end{cases}
$$
原式导出的齐次递归关系式 $a_n-2a_{n-1}=0$ 的特征方程为 $x-2=0$
故其特征根为 $q_1=2$
那么导出式的通解为 $a_n^*=2^nc$
由于 $f(n)=1$ ，且 $1$ 不是导出式的特征根，故设原式的特解为 $\bar{a}_n=A$
带入原式得 $A=2A+1\implies A=-1$
故 $\bar{a}_n=-1$
故原式的通解为 $a_n=\bar{a}_n+a_n^*=-1+2^nc$
又由初始条件 $a_1=1$ 可得 $-1+2c=1\implies c=1$
故有 $a_n=2^n-1$