k阶常系数齐次-非齐次线性递推

二阶常系数齐次递推式的通项公式

引入与结论

常见模型为 $f_n=a\times f_{n-1}+b\times f_{n-2}$ ，$a,b$ 为常数，已知 $f_0,f_1$ 求 $f_n$ 的通项公式

不难利用矩乘得到答案

其结论为：

设该递推式的特征方程为 $\lambda^2-a\times \lambda-b=0$ ，其两个特征根为 $\lambda_1,\lambda_2$

若 $\lambda_1\not ={\lambda_2}$ ，则 $f_n=A\times \lambda^n+B\times \lambda_2^n$

若 $\lambda_1=\lambda_2$ ，则 $f_n=(A+b\times n)\times\lambda_1^n$

其中 $A=f_0-\frac{c}{\lambda_2-\lambda_1},B=\frac{c}{\lambda_2-\lambda_1},c=f_1-\lambda_1f_0$

证明

考虑将递推式转化为一个类似等比数列的式子

$$f_n-\lambda_1\times f_{n-1}=\lambda_2\times (f_{n-1}-\lambda_2\times f_{n-2})$$ $$f_n=(\lambda_1+\lambda_2)\times f_{n-1}-\lambda_1\times \lambda_2\times f_{n-2}$$

再考虑原递推式，由韦达定理不难得 $\lambda_1,\lambda_2$ 即是递推式的特征方程 $\lambda^2-a\times \lambda-b=0$ 的根

不妨设 $c=f_1-\lambda_1f_0$ ，不难得：

$$\begin{cases} f_1-\lambda_1f_0=c \\ f_2-\lambda_1f_1=c\lambda_2 \\ ...\\ f_{n-2}-\lambda_1f_{n-3}=c\lambda_2^{n-3} &\text{1}\\ f_{n-1}-\lambda_1f_{n-2}=c\lambda_2^{n-2} &\text{2}\\ f_n-\lambda_1f_{n-1}=c\lambda_2^{n-1} &\text{3}\\ \end{cases}$$

3 式加 $\lambda_1\times$ 2 式得：

$$f_n-\lambda_1^2\times f_{n-2}=c\times \lambda_2^{n-1}+c\times \lambda_1\lambda_2^{n-2} \qquad\text{4}$$

4 式加 $\lambda_1^2\times$ 1 式得：

$$f_n-\lambda_1^3 \times f_{n-3}=c\times \lambda_2^{n-1}+c\times \lambda_1\lambda_2^{n-2}+c\times \lambda_1^2\lambda_2^{n-3}$$

将上述的 $n$ 个式子相加，能得到：

$$\begin{aligned} f_n-\lambda_1^n\times f_0 &=c\times (\lambda_2^{n-1}+\lambda_1\times \lambda_2^{n-2}+\lambda_1^2\lambda_2^{n-3}+...+\lambda_1^{n-2}\times \lambda_2+\lambda_1^{n-1}) \\ &=c\times \sum_{i=1}^n \left(\lambda_1^{n-1}\times \left(\frac{\lambda_2}{\lambda_1}\right)^{i-1} \right) \end{aligned}$$

最后的求和式可以看作以 $\lambda_1^{n-1}$ 为首项，$\displaystyle{\frac{\lambda_2}{\lambda_1}}$ 为公比的等比数列前 $n$ 项之和

• 若 $\lambda_1==\lambda_2$

  $$\begin{aligned} f_n-\lambda_1^nf_0&=c\times \lambda_1^{n-1}\times n \\ f_n&=c\times \lambda_1^{n-1}\times n+\lambda_1^nf_0 \\ f_n&=\left(f_0+\frac{c}{\lambda_1}\times n \right) \times \lambda_1^n \\ \end{aligned}$$

• 若 $\lambda_1\not ={\lambda_2}$

  由等比数列求和得：

  $$\begin{aligned} f_n-\lambda_1^nf_0&=c\times \lambda_1^{n-1}\frac{\left(\frac{\lambda_1}{\lambda_2}\right)^n-1}{\frac{\lambda_2}{\lambda_1}-1} \\ f_n&=c\times \frac{\lambda_2^n-\lambda_1^n}{\lambda_2-\lambda_1}+\lambda_1^nf_0 \\ f_n&=\left(f_0-\frac{c}{\lambda_2-\lambda_1}\right) \lambda_1^n+\frac{c}{\lambda_2-\lambda_1}\lambda_2^n \\ \end{aligned}$$

常系数齐次线性递推

NOIP没退役就来学

咕咕咕