一、递推关系 Recurrence Relations

1. 基本概念

• 一个数列 $\set{a_n}$ 的递推关系，是指用一个或多个该数列的前项来表示 $a_n$ 的方程
• 若一个数列的项满足递推关系，则称该数列为该递推关系的解（Solution）

**示例：**斐波那契数列

• $f_1=f_2=1$
• $f_n=f_{n-1}+f_{n-2}$，当 $n≥3$ 时

**示例：**汉诺塔问题的移动步数

• 令 $H_n$ 表示解决 $n$ 个碟子的汉诺塔问题所需的移动步数
• $H_1=1$
• $H_n=2H_{n-1}+1$
• 该递推关系的解： $H_n=2^n-1$

示例：

示例：

2. 递推关系求解的相关定义

1. 定义：k 阶线性齐次常系数递推关系

   Linear Homogeneous Recurrence Relation of Degree k with Constant Coefficients 它是形如 $a_n=c_1a_{n-1}+c_2a_{n-2}+…+c_ka_{n-k}$ 的递推关系，其中 $c_1,…,c_k$ 都是实数，且 $c_k \neq 0$

   反例：

   • 递推关系 $a_n=a_{n-1}+a_{n-2}^2$ 不是线性的
   • 递推关系 $a_n=2a_{n-1}+1$ 不是齐次的
   • 递推关系 $a_n=na_{n-1}$ 不是常系数的

2. 定义：特征方程与特征根

   为求解线性齐次常系数递推关系，我们需要列出递推关系的特征方程，根据特征方程求出特征根

   • 特征方程（Characteristic Equation）：在递推关系中代入 $a_n=r^n$，即得到特征方程
     • 设递推关系为 $a_n=c_1a_{n-1}+c_2a_{n-2}+…+c_ka_{n-k}$
     • 其特征方程为 $r^k-c_1r^{k-1}-c_2r^{k-2}-…-c_{k-1}r-c_k=0$
   • 特征根（Characteristic Roots）：特征方程的解

3. 求解 2 阶线性齐次常系数递推关系

• **定理：**令 $c_1,c_2$ 为实数，若特征方程 $r^2-c_1r-c_2=0$ 有 2 个不同的根 $r_1,r_2$，则递推关系的解形如：

  $a_n=\alpha_1r_1^n+\alpha_2r_2^n$

• **定理：**令 $c_1,c_2$ 为实数，若特征方程 $r^2-c_1r-c_2=0$ 只有 1 个根 $r$，则递推关系的解形如：

  $a_n=\alpha_1r_0^n+\alpha_2nr_0^n$

4. 求解 k 阶线性齐次常系数递推关系

• **定理：**令 $c_1,…,c_k$ 为实数，若特征方程 $r^k-c_1r^{k-1}-c_2r^{k-2}-…-c_{k-1}r-c_k=0$ 有 $k$ 个不同的根 $r_1,…,r_k$，则递推关系的解形如：

  $a_n=\alpha_1r_1^n+\alpha_2r_2^n+…+\alpha_kr_k^n$

• **定理：**令 $c_1,…,c_k$ 为实数，若特征方程 $r^k-c_1r^{k-1}-c_2r^{k-2}-…-c_{k-1}r-c_k=0$ 有 $t$ 个不同的根 $r_1,…,r_t$，且它们的重数（Multiplicities）分别为 $m_1,…,m_t$，则递推关系的解形如：

  $a_n=(\alpha_{1,0}+\alpha_{1,1}n+…+\alpha_{1,m_1}n^{m_1-1})r_1^n\\+(\alpha_{2,0}+\alpha_{2,1}n+…+\alpha_{2,m_2}n^{m_2-1})r_2^n\\+...\\+(\alpha_{t,0}+\alpha_{t,1}n+…+\alpha_{t,m_t}n^{m_t-1})r_t^n$

示例：

5. 求解线性非齐次常系数递推关系