利用线性代数的方法求斐波那契数列的通项

By Z.H. Fu https://fuzihaofzh.github.io/blog/ 这是之前的一篇文章，方法是某天中午睡觉的时候突然梦到的。今天把它搬运过来。

利用线性代数的方法求斐波那契数列的通项
程序员们一定知道斐波那契数列的故事斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34…… 这个数列从第三项开始，每一项都等于前两项之和。以前高中竞赛的时候或许人学习过特征方程来解这个问题，但当时也仅仅是会这种方法，到底是什么原理，还必须从线代的角度上来解释。
我们先来讲讲线性变换的概念怎么用于斐波那契数列。数列一项一项往前递推，就好像线性变换一次又一次地作用到一个向量上，那么作用n次后得到的向量中的某一项，就对应于数列的某一项。我们来看看具体的例子。对于斐波那契数列，我们有 $a_n=a_{n-1}+a_{n-2}$ 那么可以用矩阵的形式来表示这个变换：
我们首先通过前几项来找到变换矩阵$\mathbf{A}$

$$\left[ \begin{matrix} {a}_{2} \\ {a}_{3} \\ \end{matrix} \right]= \left[ \begin{matrix} ? & ? \\ ? & ? \\ \end{matrix} \right]\left[ \begin{matrix} {a}_{1} \\ {a}_{2} \\ \end{matrix} \right]$$

很明显，通过通项之间的关系可以看出：

$$\mathbf{A}=\left[ \begin{matrix} 0 & 1 \\ 1 & 1 \\ \end{matrix} \right]$$

令$\mathbf{x_n}=\left[ \begin{matrix}a_n \\ a_{n+1}\end{matrix} \right]$，那么我们根据这个递推关系，很容易得出:

$$\mathbf{x_n}=\mathbf{A}^{n-1} \mathbf{x_1}$$

于是，求数列通项的问题就转化成了求矩阵$\mathbf{A}^{n-1}$的问题。这个问题很容易用特征值的方法来求。求得$\mathbf{A}$的特征值为：$\frac{1+\sqrt 5}{2},\frac{1-\sqrt 5}{2}$，他们对应的特征向量为$(\frac{-1+\sqrt 5}{2},1)$和$(\frac{-1-\sqrt 5}{2},1)$,因此，$\mathbf{A}$有相似对角型$\mathbf{D}$
$D=\left[\begin{matrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{matrix}\right]=\left[\begin{matrix} \frac{1+\sqrt 5}{2} & 0 \\ 0 & \frac{1-\sqrt 5}{2} \end{matrix}\right]$
而存在变换矩阵$\mathbf{P}$使得$\mathbf{A}=\mathbf{PDP}^{-1}$,而$\mathbf{P}$由$\mathbf{A}$的特征向量组成：

$$\mathbf{P}=\left[\begin{matrix} \mathbf{v_1} & \mathbf{v_2} \end{matrix}\right]=\left[\begin{matrix} \frac{-1+\sqrt 5}{2} & \frac{-1-\sqrt 5}{2} \\ 1 & 1 \end{matrix}\right]$$

将向量$\mathbf{x_1}$向特征向量上分解得$\mathbf{x_1}=C_1 \mathbf{v_1}+C_2 \mathbf{v_2}$
而向量$(C_1,C_2)$恰好是向量$\mathbf{x_1}$在特征向量张成的空间中的坐标，因此

$$\left[\begin{matrix} C_1 \\ C_2 \end{matrix}\right]=\mathbf{P}^{-1}\mathbf{x_1}=\left[\begin{matrix} \frac{5+3\sqrt5}{10} \\ \frac{5-3\sqrt5}{10} \end{matrix}\right]$$

而我们知道，线性变换作用在特征向量上，相当于特征向量乘以对应的特征值。因此，我们有：

$$\mathbf{x_n}=\mathbf{A}^{n-1} \mathbf{x_1}=C_1\mathbf{A}^{n-1}\mathbf{v_1}+C_2\mathbf{A}^{n-1}\mathbf{v_2}=C_1\lambda_1^{n-1}\mathbf{v_1}+C2\lambda_2^{n-1} \\ =\frac{5+3\sqrt5}{10} (\frac{1+\sqrt5}{2})^{n-1}\left[\begin{matrix}\frac{-1+\sqrt5}{2} \\ 1 \end{matrix}\right]+\frac{5-3\sqrt5}{10} (\frac{1-\sqrt5}{2})^{n-1}\left[\begin{matrix}\frac{-1-\sqrt5}{2} \\ 1 \end{matrix}\right]$$

而$\mathbf{x_n}$的第一个分量就是$a_n$

$$a_n=\frac{5+\sqrt5}{10} (\frac{1+\sqrt5}{2})^{n-1}+\frac{5-\sqrt5}{10} (\frac{1-\sqrt5}{2})^{n-1}$$

用mathematica验证一下，结果正确！