常系数齐次线性递推

· · Personal

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阶常系数线性递推方程

当$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

$ \;\;\;\;\;(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)