推导斐波那契数列通项公式的6种方法

1 绪论

  斐波那契数列定义为 $F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}\ (n\geq 2)$。它是一个二阶线性递推数列，通项公式（比内公式）为

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

  这个式子本身并不复杂，但导出它的路径有很多条。本文用 6 种方法分别推导，它们从不同角度切入，最终都落到同一个公式：

  对同一个问题给出多种解法，价值不在于重复劳动，而在于同一个数学对象在不同语言（差分方程、幂级数、线性代数、算子、连分数）中的不同面貌。下面逐一推导。

2 特征方程法

  对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，假设解$F_n$的基本形式。

  ①常数，$F_n=C$。$C=C+C\Rightarrow C=0$，不符。

  ②一次函数，$F_n=rn+s$，$rn+s=r(n-1)+s+r(n-2)+s\Rightarrow n=3-\frac{s}{r}$，不符。

  ③三角函数，$F_n=sin(n)$。$sin(n)=sin(n-1)+sin(n-2)$，不符。

  ④对数函数，$F_n=ln(n)$。$ln(n)=ln(n-1)+ln(n-2)$，不符。

  ⑤指数函数，$F_n=r^n$。$r^n=r^{n-1}+r^{n-2}\Rightarrow r^2=r+1\Rightarrow r^2-r-1=0$，可能满足。

  故猜测$F_n=r^n$，并且$r$满足$r^2-r-1=0$。

  $r$有两个解，$r_1=\frac{1+\sqrt{5}}{2}$，$r_2=\frac{1-\sqrt{5}}{2}$。

  $F_n$通解即为两个线性无关解的组合。

$$F_n=Ar_1^n+Br_2^n$$

  当$n=0$时，$F_0=A+B=0\Rightarrow B=-A$。

  当$n=1$时，$F_1=Ar_1+Br_2=1$，带入$B=-A$，得

$$A(r_1-r_2)=1\Rightarrow A=\frac{1}{\sqrt{5}}\Rightarrow B=-\frac{1}{\sqrt{5}}$$

  代入$F_n=Ar_1^n+Br_2^n$得，

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

  代入$n=0$和$n=1$验证，满足条件。

3 生成函数法

  对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，定义

$$F(x)=\sum_{n=0}^{\infty}F_nx^n=F_0+F_1x+F_2x^2+F_3x^3+...$$

  等式两边同时乘$x$，$x^2$，并于原式比较，

$$\begin{aligned} F(x) &=F_0 + \hspace{-1em}&&F_1x + &&\hspace{-1em}F_2x^2 + &&\hspace{-1em}F_3x^3 + &&\hspace{-1em}...\\ x\cdot F(x) &= &&F_0x + &&\hspace{-1em}F_1x^2 + &&\hspace{-1em}F_2x^3 + &&\hspace{-1em}F_3x^4 + &&\hspace{-1em}...\\ x^2\cdot F(x)&= && &&\hspace{-1em}F_0x^2 + &&\hspace{-1em}F_1x^3 + &&\hspace{-1em}F_2x^4 + &&\hspace{-1em}F_3x^5 + &&\hspace{-1em}... \end{aligned}$$

  故有，

$$\begin{aligned} (1-x-x^2)F(x)&=F_0+F_1x-F_0x+\sum_{n=2}^{\infty}(F_n-F_{n-1}-F_{n-2})x^n\\ &=F_0+F_1x-F_0x\\ &=x \end{aligned}$$

  即，

$$F(x)=\frac{x}{1-x-x^2}$$

  尝试将分母$1-x-x^2$因式分解，令

$$1-x-x^2=0$$

  解得，

$$x_1=\frac{-1+\sqrt{5}}{2}，x_2=\frac{-1-\sqrt{5}}{2}$$

  故有，

$$\begin{aligned} 1-x-x^2=&-\left(x-\frac{-1+\sqrt{5}}{2}\right)\cdot\left(x-\frac{-1-\sqrt{5}}{2}\right)\\ =&-\left(\frac{-1+\sqrt{5}}{2}\cdot\frac{-1-\sqrt{5}}{2}\right)\left(x\cdot\frac{2}{-1+\sqrt{5}}-\frac{-1+\sqrt{5}}{2}\cdot\frac{2}{-1+\sqrt{5}}\right)\cdot\\ &\left(x\cdot\frac{2}{-1-\sqrt{5}}-\frac{-1-\sqrt{5}}{2}\cdot\frac{2}{-1-\sqrt{5}}\right)\\ =&\left(\frac{1+\sqrt{5}}{2}x-1\right)\cdot\left(\frac{1-\sqrt{5}}{2}x-1\right)\\ =&\left(1-\frac{1+\sqrt{5}}{2}x\right)\cdot\left(1-\frac{1-\sqrt{5}}{2}x\right) \end{aligned}$$

  设

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

  通分得，

$$\begin{aligned} F(x)&=\frac{A\left(1-\frac{1-\sqrt{5}}{2}x\right)+B\left(1-\frac{1+\sqrt{5}}{2}x\right)}{1-x-x^2}\\ &=\frac{(A+B)-\left(A\cdot\frac{1-\sqrt{5}}{2}+B\cdot\frac{1+\sqrt{5}}{2}\right)x}{1-x-x^2}\\ &=\frac{x}{1-x-x^2} \end{aligned}$$

  可得，$A=\frac{1}{\sqrt{5}}=-B$。

  故有，

$$F(x)=\frac{1}{\sqrt{5}}\left[\frac{1}{1-\frac{1+\sqrt{5}}{2}x}-\frac{1}{1-\frac{1-\sqrt{5}}{2}x}\right]$$

  由几何级数

$$\frac{1}{1-ax}=\sum_{n=0}^{\infty}a^nx^n$$

  得

$$F(x)=\frac{1}{\sqrt{5}}\sum_{n=0}^{\infty}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]x^n$$

  与$F(x)=\sum_{n=0}^{\infty}F_nx^n$比较系数，得

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

4 矩阵法

  对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，有

$$\begin{aligned} F_n &=1\cdot F_{n-1}+1\cdot F_{n_2}\\ F_{n-1}&=1\cdot F_{n-1}+0\cdot F_{n_2} \end{aligned}$$

  写成矩阵，

$$\begin{aligned} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix} \end{aligned}$$

  记

$$M= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$$

  故有

$$\begin{aligned} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = M \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix} = M^2 \begin{pmatrix} F_{n-2} \\ F_{n-3} \end{pmatrix} =... = M^{n-1} \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} \end{aligned}$$

  代入$F_0=0$，$F_1=1$，

$$\begin{aligned} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = M^{n-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{aligned}$$

  不难发现，只需要求出$M^{n-1}$即可求出$F_n$。

  计算$M= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}$的特征值与特征向量，

$$\lambda_1=\frac{1+\sqrt{5}}{2}，\lambda_2=\frac{1-\sqrt{5}}{2}$$

$$\begin{aligned} \varphi_1= \begin{pmatrix} \lambda_1 \\ 1 \end{pmatrix} ， \varphi_2= \begin{pmatrix} \lambda_2 \\ 1 \end{pmatrix} \end{aligned}$$

  对角化矩阵$M$,

$$M=PDP^{-1}$$

  其中，

$$\begin{aligned} P= \begin{pmatrix} \varphi_1 & \varphi_2 \end{pmatrix} = \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \end{aligned}$$

$$\begin{aligned} D= \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} \end{aligned}$$

$$\begin{aligned} P^{-1}=\frac{1}{\sqrt{5}} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \end{aligned}$$

  由对角化的性质，可得

$$\begin{aligned} M^{n-1}=PD^{n-1}P^{-1}&=\frac{1}{\sqrt{5}} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1^{n-1} & 0 \\ 0 & \lambda_2^{n-1} \end{pmatrix} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix}\\ &=\frac{1}{\sqrt{5}} \begin{pmatrix} \lambda_1^n & \lambda_2^n \\ \lambda_1^{n-1} & \lambda_2^{n-1} \end{pmatrix} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \end{aligned}$$

  故有

$$\begin{aligned} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} = M^{n-1} \begin{pmatrix} 1 \\ 0 \end{pmatrix} &=\frac{1}{\sqrt{5}} \begin{pmatrix} \lambda_1^n & \lambda_2^n \\ \lambda_1^{n-1} & \lambda_2^{n-1} \end{pmatrix} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix}\\ &=\frac{1}{\sqrt{5}} \begin{pmatrix} \lambda_1^n & \lambda_2^n \\ \lambda_1^{n-1} & \lambda_2^{n-1} \end{pmatrix} \begin{pmatrix} 1 \\ -1 \end{pmatrix}\\ &=\frac{1}{\sqrt{5}} \begin{pmatrix} \lambda_1^n-\lambda_2^n \\ \lambda_1^{n-1}-\lambda_2^{n-1} \end{pmatrix} \end{aligned}$$

  只看第一行，可得

$$F_n=\frac{1}{\sqrt{5}}(\lambda_1^n-\lambda_2^n)$$

  即

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

5 移位算子法

  对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，定义移位算子$E$

$$EF_n=F_{n+1}$$

  故有

$$E^2F_n=EF_{n+1}=F_{n+2}$$

  同理可得，

$$E^kF_n=F_{n+k}$$

  同时，也可以看出

$$F_n=E^nF_0=E^n$$

  由$F_n=F_{n-1}+F_{n-2}$得

$$F_n=EF_n+E^2F_n\Rightarrow(E^2+E-1)F_n=0$$

  由于$F_n$不恒为$0$，故有

$$E^2+E-1=0$$

  解方程，得

$$E_1=\frac{1+\sqrt{5}}{2}，E_2=\frac{1-\sqrt{5}}{2}$$

  对于特解$E_1$，我们有$F_n=E_1^n$。对于特解$E_2$，我们有$F_n=E_2^n$。

  故$E$得通解应为

$$E^n=AE_1^n+BE_2^n$$

  当$n=0$时，$F_0=E^0=A+B=0$。

  当$n=1$时，$F_1=E^1=AE_1+BE_2$。

  可得，$A=\frac{1}{\sqrt{5}}=-B$

  故有

$$F_n=E^n=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]$$

6 构造等比数列法

  对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，假设可以凑出以下形式

$$F_n-pF_{n-1}=q(F_{n-1}-pF_{n-2})$$

  并且令

$$G_n=F_n-pF_{n-1}$$

  故有

$$G_n=qG_{n-1}$$

  这是一个首项$G_0=1$，公比为$q$的等比数列。可以求得

$$G_n=q^{n-1}$$

  将凑的式子$F_n-pF_{n-1}=q(F_{n-1}-pF_{n-2})$化简，得

$$F_n=(p+q)F_{n-1}-pqF_{n-2}$$

  与$F_n=F_{n-1}+F_{n-2}$对比系数，得

$$\begin{aligned} \begin{cases} p + q&=1\\ \quad pq&=-1 \end{cases} \end{aligned}$$

  解得

$$\begin{aligned} \begin{cases} p=\frac{1+\sqrt{5}}{2}\\ q=\frac{1-\sqrt{5}}{2} \end{cases} \quad 或\quad \begin{cases} p=\frac{1-\sqrt{5}}{2}\\ q=\frac{1+\sqrt{5}}{2} \end{cases} \end{aligned}$$

  令

$$\begin{aligned} \begin{cases} s_1=\frac{1+\sqrt{5}}{2}\\ s_2=\frac{1-\sqrt{5}}{2} \end{cases} \end{aligned}$$

  故

$$\begin{aligned} \begin{cases} p=s_1\\ q=s_2 \end{cases} \quad 或\quad \begin{cases} p=s_2\\ q=s_1 \end{cases} \end{aligned}$$

  当$p=s_1，q=s_2$时，有$G_n=F_n-pF_{n-1}=q^{n-1}$，即$F_n-s_1F_{n-1}=s_2^{n-1}①$。

  当$p=s_2，q=s_1$时，有$G_n=F_n-pF_{n-1}=q^{n-1}$，即$F_n-s_2F_{n-1}=s_1^{n-1}②$。

  $①\cdot s_2-②\cdot s_1$得，$(s_2-s_1)=F_n=s_2^n-s_1^n$，即

$$F_n=\frac{s_2^n-s_1^n}{s_2-s_1}$$

  代入$s_1$和$s_2$得

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

7 无穷连分数法

  对于$F_0=0$，$F_1=1$，$F_n=F_{n-1}+F_{n-2}(n\geq 2)$，我们对$F_n=F_{n-1}+F_{n-2}$等式两边同时除以$F_{n-1}$，得

$$\frac{F_n}{F_{n-1}}=1+\frac{F_{n-2}}{F_{n-1}}$$

  令

$$x_n=\frac{F_n}{F_{n-1}}$$

  故有

$$x_n=1+\frac{1}{x_{n-1}}$$

  将上式一直迭代，得

$$x_n=1+\frac{1}{x_{n-1}}=1+\frac{1}{1+\frac{1}{x_{n-2}}}=1+\frac{1}{1+\frac{1}{1+\frac{1}{x_{n-3}}}}=...$$

  取极限

$$\varphi=\lim_{n\rightarrow\infty}x_n=1+\frac{1}{1+\frac{1}{1+\frac{1}{\ddots}}}$$

  故有

$$\varphi=1+\frac{1}{\varphi}$$

  取$\varphi>0$解得

$$\varphi=\frac{1+\sqrt{5}}{2}$$

  现在证

$$\varphi^n=\varphi F_n+F_{n-1}$$

  成立，用归纳法。

  由$\varphi=1+\frac{1}{\varphi}$得，

$$\varphi^2=\varphi+1$$

  当$n=1$时，有$\varphi^1=\varphi F_1+F_0$成立；

  当$n=k$且$\varphi^{k-1}=\varphi F_{k-1}+F_{k-2}$时，

$$\begin{aligned} &\varphi^{k-1}=\varphi F_{k-1}+F_{k-2}\\ \Rightarrow&\varphi^k=\varphi^2F_{k-1}+\varphi F_{k-2}\\ \Rightarrow&\varphi^k=(\varphi+1)F_{k-1}+\varphi F_{k-2}\\ \Rightarrow&\varphi^k=\varphi(F_{k-1}+F_{k-2})+F_{k-1}\\ \Rightarrow&\varphi^k=\varphi F_k+F_{k-1} \end{aligned}$$

  综上，

$$\varphi^n=\varphi F_n+F_{n-1}$$

  成立。

  即

$$F_n=\varphi^{n-1}-\varphi^{-1}F_{n-1}$$

  继续迭代

$$\begin{aligned} F_n&=\varphi^{n-1}-\varphi^{-1}(\varphi^{n-2}-\varphi^{-2}F_{n-2})\\ &=\varphi^{n-1}-\varphi^{n-3}+\varphi^{-3}F_{n-2}\\ &=\varphi^{n-1}-\varphi^{n-3}+\varphi^{n-5}-\varphi^{-5}F_{n-3}\\ &=\varphi^{n-1}-\varphi^{n-3}+\varphi^{n-5}-\varphi^{n-7}+\varphi^{-7}F_{n-4}\\ &=\varphi^{n-1}-\varphi^{n-3}+\varphi^{n-5}-...-(-1)^n\varphi^{-n+1}+(-1)^n\varphi^{-2n+1}F_0\\ &=\varphi^{n-1}-\varphi^{n-3}+\varphi^{n-5}-...-(-1)^n\varphi^{-n+1}\\ &=\frac{\varphi^{n-1}[1-(-\varphi^{-2})^n]}{1+\varphi^{-2}}\\ &=\frac{\varphi^{n-1}-(-1)^n\varphi^{-n-1}}{1+\varphi^{-2}}\\ &=\frac{\varphi^{-1}}{1+\varphi^{-2}}[\varphi^{n}-(-\frac{1}{\varphi})^n]\\ \end{aligned}$$

  代入$\varphi=\frac{1+\sqrt{5}}{2}$，得

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

8 方法小结

  6 种方法得出了完全相同的通项公式，但它们的性质并不相同，可按“是否需要先猜出解的形式”分两类。

  第一类：需要先猜解的形式。 特征方程法假设 $F_n=r^n$，代入后得到特征方程 $r^2-r-1=0$——这是最直接的一条路，但“为什么可以假设是指数形式”需要事先有判断（第 1 节中用排除法逐一试了常数、一次函数、三角函数、对数函数）。构造等比数列法本质上也是同一思路的变形：不去直接猜 $F_n$，而是凑出满足等比关系的组合。

  第二类：不需要猜，从递推式本身机械地推出来。 生成函数法把数列整体打包成幂级数，通过代数运算解出闭式，再展开取系数——整个过程不依赖任何灵感；矩阵法把递推写成矩阵幂，用线性代数中的对角化工具求解，几何意义清晰（对角化即换到特征向量基上）；移位算子法把递推式当作算子方程，形式上最接近差分方程的常规解法。无穷连分数法的路线最为特殊：它先得到相邻项之比 $F_n/F_{n-1}$ 的连分数表示，取其收敛值 ParseError: KaTeX parse error: Unexpected character: '' at position 1: ̲arphi=\frac{1+\…（黄金比），再反推出通项。

  值得注意的是，特征方程法中的特征根 $r_1=\frac{1+\sqrt{5}}{2}$、无穷连分数法的收敛值 $\varphi$、矩阵法中矩阵 $\begin{pmatrix}1&1\\1&0\end{pmatrix}$ 的特征值，三者是同一个数（另一个特征根为 $\frac{1-\sqrt{5}}{2}=-1/\varphi$）。这正是这些方法殊途同归的根本原因——它们都在以不同方式求解同一个特征值问题。

  由此也能看出通项公式的结构：$\frac{1}{\sqrt{5}}(r_1^n-r_2^n)$ 是两个指数项之差，由于 $|r_2|<1$，当 $n$ 较大时 $r_2^n$ 迅速衰减，$F_n$ 趋近于 $\frac{1}{\sqrt{5}}r_1^n=\frac{\varphi^n}{\sqrt{5}}$——这也解释了为什么 $F_n$ 近似按黄金比 $\varphi\approx1.618$ 成比例增长。