斐波那契数列通项公式是怎样推导出来的？

Question

斐波那契数列通项公式是怎样推导出来的？

请问斐波那契数列通项公式是怎样推导出来的？

关注者

659

被浏览

540,839

64 个回答

( 这里用 F_n 代表斐波那契数列第 n 项，且约定 F_0=0 )

设有一个矩阵 M 使得 \begin{pmatrix}F_n\\F_{n+1}\end{pmatrix}=M\begin{pmatrix}F_{n-1}\\F_{n}\end{pmatrix}

设 M=\begin{pmatrix}A&C\\B&D\end{pmatrix} 就有 \begin{pmatrix}F_n\\F_{n+1}\end{pmatrix}=\begin{pmatrix}AF_{n-1}+CF_{n}\\BF_{n-1}+DF_{n}\end{pmatrix}

直接令 A=0 ，再令 C=B=D=1 ，得到 M=\begin{pmatrix}0&1\\1&1\end{pmatrix}

把 M 特征分解，就可以求出 \begin{pmatrix}F_n\\F_{n+1}\end{pmatrix} 的通项式

\begin{pmatrix}F_n\\F_{n+1}\end{pmatrix}=M\begin{pmatrix}F_{n-1}\\F_{n}\end{pmatrix}\Rightarrow\begin{pmatrix}F_n\\F_{n+1}\end{pmatrix}=M^n\begin{pmatrix}F_{0}\\F_{1}\end{pmatrix}\Rightarrow\begin{pmatrix}F_n\\F_{n+1}\end{pmatrix}=PD^nP^{-1}\begin{pmatrix}0\\1\end{pmatrix}

解特征方程 \det(M-\lambda I)=0 得到 M 的特征值 \lambda=\frac{1\pm\displaystyle\sqrt{5}}{2}

然后得到两个的特征向量 \begin{pmatrix}1\\\\\displaystyle\frac{1\pm\sqrt 5}{2}\end{pmatrix}

\begin{aligned}P^{-1}&=\begin{vmatrix}1&1\\\\\displaystyle\frac{1+\sqrt 5}{2}&\displaystyle\frac{1-\sqrt 5}{2}\end{vmatrix}^{-1}\begin{pmatrix}\displaystyle\frac{1-\sqrt 5}{2}&-\displaystyle\frac{1+\sqrt 5}{2}\\\\-1&1\end{pmatrix}^{\rm T}\\&=\begin{pmatrix}\displaystyle\frac{\sqrt 5-1}{2\sqrt 5}&\displaystyle\frac{1}{\sqrt 5}\\\\\displaystyle\frac{\sqrt 5 + 1}{2\sqrt 5}&\displaystyle-\frac{1}{\sqrt 5}\end{pmatrix}\end{aligned}

\begin{aligned}F_n&=\begin{pmatrix}1&0\end{pmatrix}\begin{pmatrix}1&1\\\\\displaystyle\frac{1+\sqrt 5}{2}&\displaystyle\frac{1-\sqrt 5}{2}\end{pmatrix}\begin{pmatrix}\displaystyle\left(\frac{1+\sqrt 5}{2}\right)^{n}&0\\0&\displaystyle\left(\frac{1-\sqrt 5}{2}\right)^n\end{pmatrix}\begin{pmatrix}\displaystyle\frac{\sqrt 5-1}{2\sqrt 5}&\displaystyle\frac{1}{\sqrt 5}\\\\\displaystyle\frac{\sqrt 5 + 1}{2\sqrt 5}&\displaystyle-\frac{1}{\sqrt 5}\end{pmatrix}\begin{pmatrix}0\\1\end{pmatrix}\\&=\begin{pmatrix}1&0\end{pmatrix}\begin{pmatrix}1&1\\\\\displaystyle\frac{1+\sqrt 5}{2}&\displaystyle\frac{1-\sqrt 5}{2}\end{pmatrix}\begin{pmatrix}\displaystyle\left(\frac{1+\sqrt 5}{2}\right)^{n}&0\\0&\displaystyle\left(\frac{1-\sqrt 5}{2}\right)^n\end{pmatrix}\begin{pmatrix}\displaystyle\frac{1}{\sqrt{5}}\\\\\displaystyle-\frac{1}{\sqrt{5}}\end{pmatrix}\\&=\frac{2^{-n}}{\sqrt 5}\begin{pmatrix}1&0\end{pmatrix}\begin{pmatrix}1&1\\\\\displaystyle\frac{1+\sqrt 5}{2}&\displaystyle\frac{1-\sqrt 5}{2}\end{pmatrix}\begin{pmatrix}\displaystyle\left(1+\sqrt 5\right)^n\\-\displaystyle\left(1-\sqrt 5\right)^n\end{pmatrix}\\&=\frac{\displaystyle\left(\frac{1+\displaystyle\sqrt{5}}{2}\right)^n-\displaystyle\left(\frac{1-\displaystyle\sqrt{5}}{2}\right)^n}{\displaystyle\sqrt{5}}\end{aligned}

所以

F_n=\frac{\displaystyle\left(\frac{1+\displaystyle\sqrt{5}}{2}\right)^n-\displaystyle\left(\frac{1-\displaystyle\sqrt{5}}{2}\right)^n}{\displaystyle\sqrt{5}}

Mathematica：

Simplify[{{1, 0}}.Transpose[Eigenvectors[{{0, 1}, {1, 1}}]].MatrixPower[DiagonalMatrix[Eigenvalues[{{0, 1}, {1, 1}}]], n].Inverse[Transpose[Eigenvectors[{{0, 1}, {1, 1}}]]].{0, 1}]

编辑于 2018-08-08 11:14

土家族大酋长 文理两开花 · Accepted Answer

先说结论，任意形如 a_{n+2}=pa_{n+1}+qa_{n} 的数列求通项，都可以令 a_{n}=z^n 将递推公式简化为 z^2=pz+q 从而求解通项公式。下面先用这个方法求解斐波那契数列的通项公式（高中生也能轻松掌握的初等方法），再介绍一般解法。

斐波那契数列的递推关系式为：

a_{n+2}=a_{n+1}+a_{n} ；

令 a_{n}=z^n ，代入上式得：

z^2=z+1 ，解得：

z_{1}=\frac{1+\sqrt{5}}{2}; \; \; \; \; z_{2}=\frac{1-\sqrt{5}}{2} ;

重点：若 A,B 为任意实数则： a_{n}=Az_{1}^n+Bz_{2}^n [1]

亦满足原递推关系式 a_{n+2}=a_{n+1}+a_{n} ，

证明如下：

a_{n+2}=Az_{1}^{n+2}+Bz_{2}^{n+2}=A(z_{1}^{n}z_1^2)+B(z_{2}^{n}z_2^2)

\; \; \; \; \;\; \; \; =A[z_{1}^{n}(z_1+1)]+B[z_{2}^{n}(z_2+1)]

\; \; \; \; \; \; \;\; =(Az_{1}^{n+1}+Bz_{2}^{n+1})+(Az_{1}^{n}+Bz_{2}^{n})

\;\;\;\;\;\;\;\;=a_{n+1}+a_{n}

将数列前两项的值 a_{1}=1，a_{2}=1 分别代入 [1] 式得二元一次方程组：

A\cdot\frac{1+\sqrt{5}}{2}+B\cdot\frac{1-\sqrt{5}}{2}=1

A\cdot(\frac{1+\sqrt{5}}{2})^2+B\cdot(\frac{1-\sqrt{5}}{2})^2=1

解得： A=\frac{1}{\sqrt{5}}，B=-\frac{1}{\sqrt{5}} ;代入 [1] 式得：

a_n=\frac{(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}}

---------------------------------------------------------------------

下面再举一个更具一般性的例子，并通过这个例子来总结一般方法。

例如数列：1，4，6，4，-4，-16，-24......,它的后一项为前两项差的两倍，可以写作：

a_{n+2}=2(a_{n+1}-a_{n})

令 a_{n}=z^n ，代入上式化简得：

z^2=2z-2

解得： z_{1}=1+i; \; \; \; \; z_{2}=1-i

同样，对任意复数 A,B,\;a_{n}=Az_{1}^n+Bz_{2}^n [1]

亦满足原递推关系式 a_{n+2}=2(a_{n+1}-a_{n})

如若要在实数域内求解,只需令 B 为 A 的共轭复数。（why?）

令 A=a+bi ， B=\bar{A}=a-bi ,代入 [1] 式得：

\begin{align} a_{n}&=Az_{1}^n+\bar{A}z_{2}^n\\ &=(a+bi)(1+i)^n+(a-bi)(1-i)^n\\ &=(a+bi)(\sqrt{2}e^{i\pi/4})^{n}+(a-bi)(\sqrt{2}e^{-i\pi/4})^{n}\\ &=(\sqrt{2})^na(e^{in\pi/4}+e^{-in\pi/4})+i(\sqrt{2})^nb(e^{in\pi/4}-e^{-in\pi/4})\\ &=2(\sqrt{2})^na\cos(n\pi/4)-2(\sqrt{2})^nb\sin(n\pi/4)\\ &=2(\sqrt{2})^n[a\cos(n\pi/4)-b\sin(n\pi/4)] \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;[2] \end{align}

将数列前两项的值 a_{1}=1，a_{2}=4 分别代入 [2] 式得一个二元一次方程组，解得：

a=-\frac{1}{2}，b=-1 ，故原数列的通项公式为：

a_n=2(\sqrt{2})^n[-\frac{1}{2}\cos(n\pi/4)+\sin(n\pi/4)]

总结：一般的，对于形如 a_{n+2}=pa_{n+1}+qa_{n} 的递推数列

令 a_{n}=z^n 得到： z^2=pz+q

设 z_1=re^{i\theta},z_2=re^{-i\theta} 为方程的两个复数根， A,B 为任意复数，则： a_{n}=Az_{1}^n+Bz_{2}^n 亦满足原递推关系式 a_{n+2}=pa_{n+1}+qa_{n} 。证明如下： \begin{align} a_{n+2}&=Az_{1}^{n+2}+Bz_{2}^{n+2}\\ &=A(z_{1}^{n}z_1^2)+B(z_{2}^{n}z_2^2)\\ &=A[z_{1}^{n}(pz_1+q)]+B[z_{2}^{n}(pz_2+q)]\\ &=Apz_{1}^{n+1}+Aqz_{1}^{n}+Bpz_{2}^{n+1}+Bqz_{2}^{n}\\ &=p(Az_{1}^{n+1}+Bz_{2}^{n+1})+q(Az_{1}^{n}+Bz_{2}^{n})\\ &=p\;a_{n+1}+q\;a_{n} \end{align}

令 A=a+bi ， B=\bar{A}=a-bi ,根据 [2] 式的计算过程可知：

a_n=2r^n[a\cos(n\theta)-b\sin(n\theta)] [3]

再根据数列前两项的值解出a，b的值并代入 [3] 式，即可得原数列的通项公式。

另外，根据复数运算的几何意义，我们还可以将 [3] 式写作：

a_n=2 Re\left[ A\cdot z_1^n\right]

请大家自行验证。