翻书复习之时，看到斐波那契数列，于是将一些关于数列递推关系方面的内容整理了一下。
定义1：一个常系数的 $k$ 阶线性齐次递推关系是形如 $a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots+c_{k}a_{n-k}$ 的递推关系，其中 $c_{1},c_{2},\cdots,c_{k}$ 是实数，$c_{k}\neq 0$。
这个定义中递推关系是线性的，因为它的右边是数列前项的倍数之和。这个递推关系是齐次的，因为所出现的各项都是 $a_{j}$ 的倍数。数列各项的系数都是常数而不是依赖于 $n$ 的函数。阶为 $k$ 是因为 $a_{n}$ 由序列前面的 $k$ 项来表示。
例1：递推关系 $p_{n}=2p_{n-1}$ 是 $1$ 阶的线性齐次递推关系。递推关系 $f_{n}=f_{n-1}+f_{n-2}$ 是 $2$ 阶的线性齐次递推关系。
例2：递推关系 $a_{n}=a_{n-1}+a_{n-2}^{2}$ 不是线性的。递推关系 $h_{n}=2h_{n-1}+1$ 不是齐次的。递推关系 $b_{n}=nb_{n-1}$ 不是常系数的。
求解常系数线性齐次递推关系的基本方法是寻找形如 $a_{n}=r^{n}$ 的解，其中 $r$ 是常数。注意 $a_{n}=r^{n}$ 是递推关系 $a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\cdots+c_{k}a_{n-k}$ 的解，当且仅当 $$r^{n}=c_{1}r^{n-1}+c_{2}r^{n-2}+\cdots+c_{k}r_{n-k}$$ 当等式两边除以 $r^{n-k}$ 并且从左边减去右边时，我们得到等价的方程 $$r^{k}-c_{1}r^{k-1}-c_{2}r^{k-2}-\cdots-c_{k-1}r-c_{k}=0$$ 因此，数列 $\left\{a_{n}\right\}$ 以 $a_{n}=r^{n}$ 作为解，当且仅当 $r$ 使者后一个方程的解。这个方程叫作该递推关系的特征方程。方程的解叫做该递推关系的特征根。
我们首先看一个 $2$ 阶常系数线性齐次递推关系的处理结果。然后，叙述相应的阶可能大于 $2$ 的一般性结果。
定理1：设 $c_{1}$ 和 $c_{2}$ 是实数。假设 $r_{2}-c_{1}r-c_{2}=0$ 有两个不等的根 $r_{1}$ 和 $r_{2}$，那么数 $\left\{a_{n}\right\}$ 是递推关系 $a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}$ 的解，当且仅当 $a_{n}=\alpha_{1}\cdot r_{1}^{n}+\alpha_{2}\cdot r_{2}^{n},n=0,1,2,\cdots$，其中 $\alpha_{1}$ 和 $\alpha_{2}$ 是常数。
例3：求斐波那契数列的通项公式。
解：斐波那契数列满足递推关系 $f_{n}=f_{n-1}+f_{n-2}$ 和初始条件 $f_{1}=f_{2}=1$。特征方程 $r^{2}-r-1=0$ 的两个根是 $r_{1,2}=\frac{1\pm\sqrt{5}}{2}$。因此，由定理 1 的斐波那契数列通项公式为：$$f_{n}=\alpha_{1}\cdot \left(\frac{1+\sqrt{5}}{5}\right)^{n}+\alpha_{2}\cdot \left(\frac{1-\sqrt{5}}{2}\right)^{n}$$ 其中 $\alpha_{1},\alpha_{2}$ 为常数。可由初始条件 $f_{1}=f_{2}=1$ 确定这两个常数，我们有 $$\begin{cases} f_{1}=\alpha_{1}\cdot \left ( \frac{1+\sqrt{5}}{2} \right )+\alpha {2}\cdot \left ( \frac{1-\sqrt{5}}{2} \right )=1 \\ f{2}=\alpha_{1}\cdot \left ( \frac{1+\sqrt{5}}{2} \right )^{2}+\alpha {2}\cdot \left ( \frac{1-\sqrt{5}}{2} \right )^{2}=1 \end{cases}$$ 从而得到 $\alpha{1}=\frac{\sqrt{5}}{5},\alpha_{2}=-\frac{\sqrt{5}}{5}$，于是斐波那契数列的通项公式为：$$f_{n}=\frac{\sqrt{5}}{5}\left(\frac{1+\sqrt{5}}{5}\right)^{n}-\frac{\sqrt{5}}{5}\left(\frac{1-\sqrt{5}}{2}\right)^{n}$$
当存在二重特征根的时候，定理1不再适用。如果遇到这种情况，当 $r_{0}$ 是特征方程的一个二重根时，那么 $a_{n}=nr_{0}^{n}$ 是递推关系的另一个解。
定理2：设 $c_{1}$ 和 $c_{2}$ 是实数。假设 $r_{2}-c_{1}r-c_{2}=0$ 只有一个根 $r_{0}$。数列 $\left{a_{n}\right}$ 是递推关系 $a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}$ 的解，当且仅当 $a_{n}=\alpha_{1}\cdot r_{0}^{n}+\alpha_{2}\cdot n\cdot r_{0}^{n},n=0,1,2,\cdots$，其中 $\alpha_{1}$ 和 $\alpha_{2}$ 是常数。
例4：数列 $\left\{a_{n}\right\}$ 满足 $a_{n}=6a_{n-1}-9a_{n-2}$，且$a_{1}=6，a_{2}=27$，求数列 $\left\{a_{n}\right\}$ 的通项公式。
解：$r^{2}-6r+9=0$ 唯一的根是 $r=3$。因此这个递推关系的解是 $$a_{n}=\alpha_{1}\cdot 3^{n}+\alpha_{2}\cdot n\cdot 3_{n}$$ 其中 $\alpha_{1},\alpha_{2}$ 是常数。使用初始条件得 $\alpha_{1}=\alpha_{2}=1$，所以 $\left\{a_{n}\right\}$ 的通项公式为 $$a_{n}=3^{n}+n\cdot 3^{n}$$
例5：求满足 $a_{1}=5,a_{2}=15,a_{3}=47$ 的递推关系 $a_{n}=6a_{n-1}-11a_{n-2}+6a_{n-3}$ 的通项公式。
解：有这个递推关系的特征方程 $r^{3}-6r^{2}+11r-6=0$ 得到三个特征根 $r_{1}=1,r_{2}=2,r_{3}=3$，于是递推关系的解的形式为：$$a_{n}=\alpha_{1}\cdot 1^{n}+\alpha_{2}\cdot 2^{n}+\alpha_{3}\cdot 3^{n}$$ 通过初始条件得到 $\alpha_{1}=1,\alpha_{2}=-1,\alpha_{3}=2$。于是通项公式为：$$a_{n}=1-2^{n}+2\cdot 3^{n}$$