【算法】斐波那契通项公式

特征方程和通项公式

如果数列a_n的递推公式：a_n=c_1a_{n-1}+c_2a_{n-2}-----(1)

根据待定系数法，假设a_n-xa_{n-1}=y(a_{n-1}-xa_{n-2})-----（2）

（1）和（2）比较得
\begin{equation} \left\{ \begin{array}{lr} x+y=c_1\\ xy=-c_2\\ \end{array} \right. \end{equation}
根据韦达定理，x,y是方程t^2-c_1t-c_2=0的两个根，我们也将这个方程称为数列a_n的特征方程

根据方程（2）可以推出a_n-xa_{n-1}=y^{n-1}(a_1-xa_0)（等比数列）-----（3）

下面我们将两个根t_1,t_2分别带入方程（3）得
\begin{equation} \left\{ \begin{array}{lr} a_n-t_1a_{n-1}=t_2^{n-1}(a_1-t_1a_0)......(4)\\ a_n-t_2a_{n-1}=t_1^{n-1}(a_1-t_2a_0)......(5)\\ \end{array} \right. \end{equation}
将(5)*t_1-(4)*t_2得

(t_1-t_2)a_n=(a_1-t_2a_0)t_1^n-(a_1-t_1a_0)t_2^n

再整理得

a_n=\frac{a_1-t_2a_0}{t_1-t_2}t_1^n-\frac{a_1-t_1a_0}{t_1-t_2}t_2^n

而a_0,a_1,t_1,t_2均已知，可当作常项，于是a_n的通项公式：

a_n=At_1^n+Bt_2^n

t_1,t_2是特征方程的两个根

A,B是常项，一般通过待定系数法求出

斐波那契通项公式

斐波那契数列的递推公式：a_n=a_{n-1}+a_{n-2}

于是特征方程为：x^2-x-1=0的两个根：x_1=\frac{1+\sqrt5}{2}和x_2=\frac{1-\sqrt5}{2}

则a_n=Ax_1^n+Bx_2^n，将a_1=1,a_2=1带入可求得A=\frac{1}{\sqrt5},B=-\frac{1}{\sqrt5}

即通项公式：a_n=\frac{1}{\sqrt5}[(\frac{1+\sqrt5}{2})^n-(\frac{1-\sqrt5}{2})^n]

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容