浅谈 特征方程（二阶常系数线性齐次递推式的应用和证明）

转自我儿lzj之博客
PS：我学这个的时候，应用其实是非常简单的，先把x1和x2求出来，然后把已知的序列中的某两项带入求出A和B的值，那么通项公式就求出来嘞。
虽然证明看起来式子很多，但其实认真读一下就好啦。

前言

特征方程应该是大学里的内容，但最近做题的时候遇到了，就想把我的一点心得和大家分享一下。
但由于鄙人水平有限，故以下只讨论二阶常系数线性齐次递推式。

问题

已知$f(n)=c1\ast f(n-1)+c2\ast f(n-2)$（$c1,c2$是常数），已知$f(0)$和$f(1)$，求$f(n)$的通项公式。

结论

先求出上面递推式的特征方程：$x^2-c1\ast x-c2=0$。设两根分别为$x1,x2$。
若$x1̸=x2$，则$f(n)=A\ast x{1}^n+B\ast x{2}^n$；
若$x1=x2$，则$f(n)=(A+B\ast n)\ast x{1}^n$。（A和B可通过$f(0)$和$f(1)$求出）

例题

已知$f(n)=4f(n-1)-3f(n)$，$f(0)=3$，$f(1)=5$，求$f(n)$的通项公式。
解：
特征方程为：$x^2-4x+3=0$
$x1=1,x2=3$
$\because x1̸=x2$
$\therefore f(n)=A+B\ast 3^n$
当n=0时，$3=A+B$；当n=1时，$5=A+3B$
解得$A=2,B=1$
$\therefore f(n)=3^n+2$

证明

我们可以把递推式转化成一个类似等比数列的东西。
设$f(n)-r\ast f(n-1)=s(f(n-1)-r\ast f(n-2))$，则$f(n)=(s+r)\ast f(n-1)-r\ast s\ast f(n-2)$
可得$s+r=c1,s\ast r=-c2$
根据韦达定理，s和r是$x^2-c1\ast x-c2=0$的两根
$x^2-c1\ast x-c2=0$称为该递推式的特征方程，两根分别为$x1,x2$
不妨设$x1=r,x2=s$，则$\frac{f(n)-x1\ast f(n-1)}{f(n-1)-x1\ast f(n-2)}=x2$
设$f(1)-x1\ast f(0)=a$
则$f(2)-x1\ast f(1)=a\ast x2$
……
$f(n-2)-x1\ast f(n-3)=a\ast x{2}^{n-3}$①
$f(n-1)-x1\ast f(n-2)=a\ast x{2}^{n-2}$②
$f(n)-x1\ast f(n-1)=a\ast x{2}^{n-1}$③
③+$x1\ast$②得：$f(n)-x{1}^2\ast f(n-2)=a\ast x{2}^{n-1}+a\ast x1\ast x{2}^{n-2}$④
④+$x{1}^2\ast$①得：$f(n)-x{1}^3\ast f(n-3)=a\ast x{2}^{n-1}+a\ast x1\ast x{2}^{n-2}+a\ast x{1}^2\ast x{2}^{n-3}$
发现规律了吗？

$f(n)-x{1}^n\ast f(0)=a\ast (x{2}^{n-1}+x1\ast x{2}^{n-2}+x{1}^2\ast x{2}^{n-3}+\dots \dots +x{1}^{n-2}\ast x2+x{1}^{n-1})$
=$a\ast {\sum }_{i=1}^n(x{1}^{n-1}\ast (\frac{x2}{x1}{)}^{i-1})$
${\sum }_{i=1}^n(x{1}^{n-1}\ast (\frac{x2}{x1}{)}^{i-1})$可以看成是以$x{1}^{n-1}$为首项，$\frac{x2}{x1}$为公比的等比数列的前n项的和

在运用等比数列求和公式之前一定要讨论公比是否为1，接下来开始讨论：
1.当$x1̸=x2$时：${\sum }_{i=1}^n(x{1}^{n-1}\ast (\frac{x2}{x1}{)}^{i-1})$=$x{1}^{n-1}\ast \frac{(\frac{x2}{x1}{)}^n-1}{\frac{x2}{x1}-1}=\frac{x{2}^n-x{1}^n}{x2-x1}$
$f(n)=x{1}^n\ast f(0)+a\ast {\sum }_{i=1}^n(x{1}^{n-1}\ast (\frac{x2}{x1}{)}^{i-1})=(f(0)-\frac{a}{x2-x1})\ast x{1}^n+\frac{a}{x2-x1}\ast x{2}^n$
令$A=f(0)-\frac{a}{x2-x1},B=\frac{a}{x2-x1}$，则有$f(n)=A\ast x{1}^n+B\ast x{2}^n$
该情况证明完毕
2.当$x1=x2$时，${\sum }_{i=1}^n(x{1}^{n-1}\ast (\frac{x2}{x1}{)}^{i-1})=a\ast n\ast x{1}^{n-1}$
$f(n)=a\ast n\ast x{1}^{n-1}+x{1}^n\ast f(0)=(\frac{a\ast n}{x1}+f(0))\ast x{1}^n$
令$A=f(0),B=\frac{a}{x1}$，则有$f(n)=(A+B\ast n)\ast x{1}^n$
至此，命题证明完毕

应用

求斐波那契数列通项公式
$f(n)=f(n-1)+f(n-2),f(0)=0,f(1)=1$
根据特征方程：$x^2-x-1=0$
$x1=\frac{\sqrt{5}+1}{2},x2=\frac{\sqrt{5}-1}{2}$
那么，$f(n)=A\ast x{1}^n+B\ast x{2}^n$
代入$f(0)=0,f(1)=1$，得：$A=\frac{\sqrt{5}}{5},B=-\frac{\sqrt{5}}{5}$
整理得：$f(n)=\frac{(\frac{\sqrt{5}+1}{2}{)}^n-(\frac{\sqrt{5}-1}{2}{)}^n}{\sqrt{5}}$

总结

对于这个问题来说，其实结论比证明更加重要。但我想要在网上找证明，却很难找到，无奈，只好自己证明。不知是这个问题太过简单，各位高手不愿证明，还是别的证明比较复杂，难度较高。总之，这些证明只是我的一点小想法，希望能抛砖引玉。