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

转自我儿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 − c 1 ∗ x − c 2 = 0 x^2-c1*x-c2=0 x2−c1∗x−c2=0。设两根分别为$x1,x2$。
若 x 1 ≠ x 2 x1\neq x2 x1̸​=x2，则 f ( n ) = A ∗ x 1 n + B ∗ x 2 n f(n)=A*x1^n+B*x2^n f(n)=A∗x1n+B∗x2n；
若$x1=x2$，则 f ( n ) = ( A + B ∗ n ) ∗ x 1 n f(n)=(A+B*n)*x1^n f(n)=(A+B∗n)∗x1n。（A和B可通过$f(0)$和$f(1)$求出）

例题

已知$f(n)=4f(n-1)-3f(n)$，$f(0)=3$，$f(1)=5$，求$f(n)$的通项公式。
解：
特征方程为： x 2 − 4 x + 3 = 0 x^2-4x+3=0 x2−4x+3=0
$x1=1,x2=3$
∵ x 1 ≠ x 2 \because x1\neq x2 ∵x1̸​=x2
∴ f ( n ) = A + B ∗ 3 n \therefore f(n)=A+B*3^n ∴f(n)=A+B∗3n
当n=0时，$3=A+B$；当n=1时，$5=A+3B$
解得$A=2,B=1$
∴ f ( n ) = 3 n + 2 \therefore f(n)=3^n+2 ∴f(n)=3n+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 − c 1 ∗ x − c 2 = 0 x^2-c1*x-c2=0 x2−c1∗x−c2=0的两根
x 2 − c 1 ∗ x − c 2 = 0 x^2-c1*x-c2=0 x2−c1∗x−c2=0称为该递推式的特征方程，两根分别为$x1,x2$
不妨设$x1=r,x2=s$，则 f ( n ) − x 1 ∗ f ( n − 1 ) f ( n − 1 ) − x 1 ∗ f ( n − 2 ) = x 2 \frac{f(n)-x1*f(n-1)}{f(n-1)-x1*f(n-2)}=x2 f(n−1)−x1∗f(n−2)f(n)−x1∗f(n−1)​=x2
设$f(1)-x1\ast f(0)=a$
则$f(2)-x1\ast f(1)=a\ast x2$
……
f ( n − 2 ) − x 1 ∗ f ( n − 3 ) = a ∗ x 2 n − 3 f(n-2)-x1*f(n-3)=a*x2^{n-3} f(n−2)−x1∗f(n−3)=a∗x2n−3①
f ( n − 1 ) − x 1 ∗ f ( n − 2 ) = a ∗ x 2 n − 2 f(n-1)-x1*f(n-2)=a*x2^{n-2} f(n−1)−x1∗f(n−2)=a∗x2n−2②
f ( n ) − x 1 ∗ f ( n − 1 ) = a ∗ x 2 n − 1 f(n)-x1*f(n-1)=a*x2^{n-1} f(n)−x1∗f(n−1)=a∗x2n−1③
③+$x1\ast$②得： f ( n ) − x 1 2 ∗ f ( n − 2 ) = a ∗ x 2 n − 1 + a ∗ x 1 ∗ x 2 n − 2 f(n)-x1^2*f(n-2)=a*x2^{n-1}+a*x1*x2^{n-2} f(n)−x12∗f(n−2)=a∗x2n−1+a∗x1∗x2n−2④
④+ x 1 2 ∗ x1^2* x12∗①得： f ( n ) − x 1 3 ∗ f ( n − 3 ) = a ∗ x 2 n − 1 + a ∗ x 1 ∗ x 2 n − 2 + a ∗ x 1 2 ∗ x 2 n − 3 f(n)-x1^3*f(n-3)=a*x2^{n-1}+a*x1*x2^{n-2}+a*x1^2*x2^{n-3} f(n)−x13∗f(n−3)=a∗x2n−1+a∗x1∗x2n−2+a∗x12∗x2n−3
发现规律了吗？

f ( n ) − x 1 n ∗ f ( 0 ) = a ∗ ( x 2 n − 1 + x 1 ∗ x 2 n − 2 + x 1 2 ∗ x 2 n − 3 + … … + x 1 n − 2 ∗ x 2 + x 1 n − 1 ) f(n)-x1^n*f(0)=a*(x2^{n-1}+x1*x2^{n-2}+x1^2*x2^{n-3}+……+x1^{n-2}*x2+x1^{n-1}) f(n)−x1n∗f(0)=a∗(x2n−1+x1∗x2n−2+x12∗x2n−3+……+x1n−2∗x2+x1n−1)
= a ∗ ∑ i = 1 n ( x 1 n − 1 ∗ ( x 2 x 1 ) i − 1 ) a*\sum_{i=1}^n({x1^{n-1}*(\frac{x2}{x1})^{i-1}}) a∗∑i=1n​(x1n−1∗(x1x2​)i−1)
∑ i = 1 n ( x 1 n − 1 ∗ ( x 2 x 1 ) i − 1 ) \sum_{i=1}^n({x1^{n-1}*(\frac{x2}{x1})^{i-1}}) ∑i=1n​(x1n−1∗(x1x2​)i−1)可以看成是以 x 1 n − 1 x1^{n-1} x1n−1为首项， x 2 x 1 \frac{x2}{x1} x1x2​为公比的等比数列的前n项的和

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

应用

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

总结

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！