“ $$ 一个常系数的k阶线性齐次递推关系是形如：\ a_n=c_1 \cdot {a}{n-1}+c_2 \cdot {a}{n-2}+c_3 \cdot {a}{n-3}+\cdots c_k \cdot {a}{n-k}\ 的递推关系，其中 c_1,c_2,c_3 \cdots c_k 是实数，且 c_k \neq 0 $$ ”
乍一看很迷的一个定义，一个一个拆解其中的定义：
- 常系数：
c1,c2,c3......ck都是常数，且在其中没有n的变量之类的 - k阶：
a_n的值由前面的k项来决定 - 线性：
a_n的值是由前面几项的倍数之和 - 齐次：其中各项都是
a_j的倍数
举几个例子： $$ p_n=(1.11){p}{n-1}：1阶齐次线性递推关系\ f_n={f}{n-1}+{f}{n-2}:2阶齐次线性递推关系\ a_n=a_5：5阶齐次线性递推关系\ a_n={a}{n-1}+{a}{n-2}^{2}：非线性\ H_n=2\cdot {H}{n-1}+1：非齐次\ B_n=n \cdot {B}_{n-1}：非常系数 $$
简单点来说就是将上面的常系数线性齐次递推关系转换成n和a_n的函数。
首先是第一种形式的递推关系的解： $$ 递归关系的形式如下：a_n=c_1 \cdot {a}{n-1}+c_2 \cdot {a}{n-2}，其中 c_1,c_2 \in R \ 再来要求：r^2 - c_1 \cdot r -c_2=0，有两个不相等的解 r_1，r_2。\ 那么 a_n= k_1 \cdot {r}{1}^{n}+k_2 \cdot {r}{2}^{n}\ 就是上面递推关系的解\ k_1,k_2 \in R，一般情况下可以根据已知条件推算出来 $$ 例子：求解 $$ a_n= {a}{n-1} + 2 \cdot {a}{n-2} 的解，其中 a_0=2,a_1=7 $$ 解答过程： $$ 套用上面的公式可知：c_1=1,c_2=2，所以 \ r^2 - c_1 \cdot r -c_2 = r^2-r-2=0 \ 解有2个：r_1=2,r_2=-1 \ 所以解为：a_n=k_1 \cdot {r}{1}^{n}+k_2 \cdot {r}{2}^{n}=k_1 \cdot 2^n +(-1)^n \ 因为\ a_0=2=k_1 \cdot 2^0 +(-1)^0 \ a_1=7=k_1 \cdot 2^1 +(-1)^1 \ 所以解出：k_1=3，k_2=-1 \ 所以：a_n=3 \cdot 2^n + (-1) \cdot (-1) ^ n=3 \cdot 2^n - (-1)^n $$ 看完例子之后，来证明这样做的原理： $$ 假设：\ r_1^2-c_1 \cdot r_1-c_2=0\ r_2^2-c_1 \cdot r_2-c_2=0\ r_1 \neq r_2 \ a_n=k_1 {r}{1}^n+k_2 {r}{2}^{n} \ 那么：\ a_n=k_1 {r}{1}^{n-2} \cdot{r}{1}^{2} +k_2 {r}{2}^{n-2} \cdot {r}{2}^{2}\ =k_1 {r}{1}^{n-2}(c_1 \cdot r_1+c_2)+k_2 {r}{2}^{n-2} (c_1 \cdot r_2+c_2) \ =k_1 {r}{1}^{n-1} c_1+ k_1 {r}{1}^{n-2} c_2 + k_2 {r}{2}^{n-1} c_1+k_2 {r}{2}^{n-2} c_2 \ =(k_1 {r}{1}^{n-1}+k_2 {r}{2}^{n-1}) \cdot c_1+(k_1 {r}{1}^{n-2}+k_2 {r}{2}^{n-2}) \cdot c_2\ ={a}{n-1} \cdot c_1+{a}{n-2} \cdot c_2\ 所以在假设成立的条件下：\ a_n=k_1 {r}{1}^n+k_2 {r}{2}^{n}是递推关系 a_n={a}{n-1} \cdot c_1+{a}{n-2} \cdot c_2的解 $$ 下面还需要证明一个东西：k1和k2一定存在吗？ $$ 假设这两个值一定存在，则：\ a_0=k_1 \cdot {r}{1}^{0}+k_2 \cdot {r}{2}^{0}=k_1+k_2 \ a_1=k_1 \cdot {r}{1}^{1}+k_2 \cdot {r}{2}^{1}=k_1 \cdot r_1 +k_2 \cdot r_2\ 用解二元一次方程组的方式来解，可以得出：\ k_1=\frac{a_1-a_0 \cdot r_2}{r_1-r_2}\ k_2=a_0-k_1=\frac{a_0 \cdot r_1-a_1}{r_1-r_2}\ 因为 r_1 \neq r_2，所以上面的方程一定有解 $$
在上面的证明过程中，我们有一个要求是 $$ r^2-c_1 \cdot r -c_2 =0 有两个解，如果其只有一个相同的解，那么就是这里考虑的内容了。 $$ 还是模仿上面的定义： $$ 递推关系如下：a_n=c_1 \cdot {a}{n-1}+c_2 \cdot {a}{n-2} \ 再来要求：r^2-c_1 \cdot r-c_2=0，只有一个解 r_0\ 那么：a_n=k_1 {r}{0}^n+k_2 \cdot n \cdot {r}{0}^n \ 就是递推关系的解 $$ 这个的证明我推导的时候总是有一个值消不掉，可能是我推导有问题，所以暂时没有证明。
在上面只有2阶的情况下，如果是多阶的情况下： $$ 如果 r_n 是对于方程：\ r^k-c_1 \cdot {r}^{k-1} + c_2 \cdot {r}^{k-2} \cdots + c_k =0 的k个不同的解，则\ a_n=k_1 {r}{1}^{n}+k_2 {r}{2}^{n}+k_3 {r}{3}^{n} \cdots k_n {r}{k}^{n} 是 \ a_n=c_1 {a}{n-1}+ c_2 {a}{n-2}+ \cdots c_k {a}_{n-k}的递推关系的解 $$
同时，这里的r与k组成的方程叫做特征方程，方程的解，也就是r_n的值叫做特征根。
例子： $$ 假设 a_0=2,a_1=5,a_2=15，a_n=6 \cdot {a}{n-1}-11 \cdot {a}{n-2}+6 \cdot {a}_{n-3} \ 求递推关系的解：\ 首先 c_1=6,c_2=-11,c_3=6,k=3，所以 \ r^3-6 \cdot r^2 +11 \cdot r-6=0\ 得出：r_1=1,r_2=2,r_3=3 \ 同时因为：\ a_0=2=k_1 \cdot 1^0 + k_2 \cdot 2^0 + k_3 \cdot 3^0 \ a_1=5=k_1 \cdot 1^1 + k_2 \cdot 2^1 + k_3 \cdot 3^1 \ a_2=15=k_1 \cdot 1^2 + k_2 \cdot 2^2 + k_3 \cdot 3^2 \ 所以：k_1=1,k_2=-1,k_3=2 \ 所以：a_n=1 \cdot 1^n +(-1) \cdot 2^n + 2 \cdot 3^n =1-2^n+2\cdot 3^n $$
上面是k个不同的解，如果其中有相同的解时： $$ 假设特征方程为：\ r^k-c_1 \cdot {r}^{k-1} + c_2 \cdot {r}^{k-2} \cdots + c_k =0，\ 特征根中的重数（相同的值的个数）分别为 m_1,m_2,m_3 \cdots m_t \ 那么对于方程：\ a_n=c_1 {a}{n-1}+ c_2 {a}{n-2}+ \cdots c_k {a}{n-k}的解为：\ a_n=({k}{1.0}+{k}{1,1} \cdot n+ {k}{1,2} \cdot n^2 + {k}{1,3} \cdot n^3 \cdots {k}{1,m_1-1} \cdot {n}^{m_1-1}) {r}{1}^{n} \ +({k}{2.0}+{k}{2,1} \cdot n+ {k}{2,2} \cdot n^2 + {k}{2,3} \cdot n^3 \cdots {k}{2,m_2-1} \cdot {n}^{m_2-1}) {r}{2}^{n} \ \vdots \ +({k}{t.0}+{k}{t,1} \cdot n+ {k}{t,2} \cdot n^2 + {k}{t,3} \cdot n^3 \cdots {k}{t,m_t-1} \cdot {n}^{m_t-1}) {r}_{t}^{n} $$
例子： $$ 已知：a_0=1,a_1=-2,a_2=-1,a_n=-3 \cdot {a}{n-1}-3 \cdot {a}{n-2} - {a}{n-3}，求这个递推关系的解。\ 解答过程：\ k为3，所以特征方程为 r^3+3 \cdot r^2 + 3 \cdot r^2+1=0 \ 特征根为 r_0=-1，为重根。\ 所以 a_n=({k}{1,0}+{k}{1,1}\cdot n+{k}{1,2} \cdot n^2) \cdot (-1)^n\ 同时：\ a_0=1=({k}{1,0}+{k}{1,1}\cdot 0+{k}{1,2} \cdot 0^2) \cdot (-1)^0 \ a_1=-2=({k}{1,0}+{k}{1,1}\cdot 1+{k}{1,2} \cdot 1^2) \cdot (-1)^1 \ a_3=-3=({k}{1,0}+{k}{1,1}\cdot 2+{k}{1,2} \cdot 2^2) \cdot (-1)^2 \ 所以：\ {k}{1,0}=1 \ {k}{1,1}=3\ {k}{1,2}=-2 \ 所以：a_n=(1+3n-2 \cdot n^2) \cdot (-1)^n $$