常系数齐次线性递推

1.**递推式** $f_{n}=a_{1}\times$ $f_{n-1}+a_{2}$ $\times$ $f_{n-2}$ $...+$ $a_{k}$ $\times$ $f_{n-k}$ 其中$a_{1},a_{2}...a_{k}$,为常数则称数列 $f_{n}$ 为线性递推数列 $ps:f_{n}$ 即使不是线性递推方程但满足任何一个线性递推多项式即可， 例如 $f_{n}$−$f_{n-1}=1$ 不是线性递推方程但可得到 $f_{n}-2\times\;f_{n-1}+f_{n-2}=0$ 因此${f_n}$为线性递推数列 2.**k阶常系数线性递推方程**: $H_{n}-a_{1}\times\;H_{n-1}-a_2\times\;H_{n-2}-...-a_k\times\;H_{n-k}=f_{n}$ $H_{0}=b_0,H_{1}=b_1,H_{2}=b_2,...,H_{k-1}=b_{k-1}$ 其中$a_1,a_2,...,a_k$为常数,$a_k\neq0$,这个方程称为**k阶常系数线性递推方程** $b_0,b_1,...,b_{k-1}$为$k$个初值(边界). 当$f_{n}=0$时称这个递推方程为**齐次方程**. 3.定义$f_n$的**特征方程**: 设一常系数线性齐次递推方程如下： $H_n-a_1\times\;H_{n-1}-a_2\times\;H_{n-2}-...-a_k\times\;H_{n-k}=0.....(1)$ $H_0=b_0,H_1=b_1,H_2=b_2,...,H_{k-1}=b_{k-1}$ 其解的形式为$H_n=...$; 则方程： $x^k-a_1\times\;x^{k-1}-...-a_k=0$ 为该递推方程的特征方程 特征方程的根为递推方程的**特征根**. 由基本代数定理： $C_x=0$的解(称为特征根)有k个，设为$q_1,q_2...q_k$ 4.定理&推论： 递推方程及其特征根的关系： 定理[1]: [1].设1是非零复数,则q^n是递推方程(1)的解当且仅当q为它的特征根. 证:$H_n=q^n$ $\Leftarrow\Rightarrow\;q^n -a_1\times\;q^{n-1}-a_2\times\;q^{n-2}-...-a_k\times\;q^{n-k}=0$(代入) $ \;\;\;\;\;(H_n-a_1\times\;H_{n-1} -a_2\times\;H_{n-2} -... -a_k\times\;H_{n-k}=0)$(递推方程) $\Leftarrow\Rightarrow\;q^{n-k}\times\;(q^k-a_1\times\;q^{k-1}-a_2\times\;q^{k-2}-...-a_k)=0$(提出q^(n-k)) $\Leftarrow\Rightarrow\;q^k-a_1\times\;q^{k-1}-a_2\times\;q^{k-2}-...-a_k=0$(除去$q^{n-k}$) $ \;\;\;\;\;(x^k-a_1\times\;x^{k-1}-a_2\times\;x^{k-2}-...-a_k=0)$(特征方程) $\Leftarrow\Rightarrow\;q$为它的特征根 定理[2]: [2].设$h_1(n)$和$h_2(n)$是递推方程$(1)$的解,$c_1,c_2$为任意常数,则$c_1\times\;h_1(n)+c_2\times\;h_2(n)$也是这个递推方程的解. 证:代入即可 由以上[1][2]可得推论: 若$q_1,q_2,...,q_k$为$(1)$的特征根，则$c_1\times\;q_1^n+c_2\times\;q_2^n+...+c_k\times\;q_k^n$是该递推方程的解,其中$c_1,c_2,...,c_k$为任意常数. 总结:$ c_1\times\;q_1^n+c_2\times\;q_2^n+...+c_k\times\;q_k^n $为该递推方程的解(最多$k$个根). ## 是否还有其他形式的解？ **通解**的定义: [4].若对$(1)$由不同的初值确定的每一个解$h(n)$都存在一组常数$c_1',c_2',...c_k'$,使得 $h(n)=c_1'\times\;q_1^n+c_2'\times\;q_2^n+...+c_k'\times\;q_k^n$ 成立(即常数$c_1',c_2',...c_k'$固定已得,变化),则称$c_1\times\;q_1^n+c_2\times\;q_2^n+...+c_k\times\;q_k^n$为该递推方程的通解 下面的定理说明,当k个特征根彼此不等时,上述的解就是递推方程$(1)$的**通解** [3].设$q_1,q_2,...,q_k$是递推方程$(1)$的不同特征根,则$H(n)=c_1\times\;q_1^n+c_2\times\;q_2^n+...+c_k\times\;q_k^n$为该递推方程的通解 证:根据推论知H(n)为解，将初值代入: $c_1+c_2+...+c_k=b_0$ $c_1\times\;q_1+c_2\times\;q_2+...+c_k\times\;q_k=b_1$ $\ldots\ldots$ $c_1\times\;q_1^{k-1}+c_2\times\;q_2^{k-1}+...+c_k\times\;q_k^{k-1}$ 如果有唯一一组解$c_1',c_2',...c_k'$,则说明$h(n)=c_1'\times\;q_1^n+c_2'\times\;q_2^n+...+c_k'\times\;q_k^n$ ### 附注: 特征根中若有重根,使用线性无关的解来构造通解 [4]设$q_1,q_2,...,q_t$是递推方程(1)的不相等的特征根,$q_i$的重数为$e_i$,其中$i=1,2,...,t$令 $H_i(n)=(c_{i1}+c_{i2}\times\;n+...+c_{ie_{i}}\times\;n^{e_{i}-1})\times\;q_i^n$ 则该递推方程通解为: $H(n)=\sum_{i=1}^t H_i(n)$ 总结思路: 1.写出特征方程 2.解出特征根 3.写出代入特征根的通解 4.代入初值写出线性方程组 5.解出常数$c$ 6.代入通解出通项 [例]求解斐波那契数列的递推方程 解: 线性递推方程$f_{n}=f_{n-1}+f_{n-2}$的特征方程为 $q^2-q-1=0$ 特征方程有两个实根 $q_1=\frac{ 1+\sqrt{5 } }{ 2 }$,$q_1=\frac{ 1-\sqrt{5 } }{ 2 }$ 因此线性递推方程的通解为 $F_n=c_1\times(\frac{ 1+\sqrt{5 } }{ 2 })^n+c_2\times(\frac{ 1+\sqrt{5 } }{ 2 })^n$ 将 $F_0=F_1=1$代入上式求得 $c_1=\frac{\sqrt{ 5 }}{ 5 },c_2=-\frac{\sqrt{ 5 }}{ 5 }$ 因此斐波那契数列的通项公式为 $F_n=\frac{\sqrt{ 5 }}{ 5 }\times((\frac{ 1+\sqrt{5 } }{ 2 })^n-(\frac{ 1-\sqrt{5 } }{ 2 })^n)$