斐波那契数列通项公式的证明及推广

注：本文包含背景部分和正文部分。背景部分涉及斐波那契数列的基本知识及对正文部分基础知识的视觉化科普，后者适合学过向量的同学。

正文部分则利用基础的线性代数知识证明了斐波那契数列通项公式，及对一般二元线性齐次递推数列通项公式及一般元线性齐次递推数列通项公式的通式进行了推导与证明。元线性递推数列通项公式的通式的推导与证明由笔者自己完成，可能会有不严谨和错误的地方，敬请大家谨慎阅读。

背景部分介绍 介

相信大家都见过这个公式

这是斐波那契数列的二阶线性齐次递推公式。“二阶”表示等号右边有2项，“线性”表示每项次幂为1，“齐次”表示没有常数项，“递推”表示是由小于它的几项组合得来。 它的通项公式相较于递推公式会难记很多：

那该怎么证明它呢？

简单的证明方法

这个证法的关键是假设

是一个等比数列：

则

则知

（很关键的一步，这个叫特征方程）

然后通项公式中括号里的两项就出来了：

观察发现，这个等比数列好像有两个比值. 那我们就把看作是两个比值的某种组合：

（很关键的另外一步）

所以我们把=1和=1代入这个方程，做一个二元一次方程组就把和求出来了。他们都是

.于是

这个证明方法非常的简单和不严谨，但是却非常直接。如果哪天你需要证明这个公式，从特征方程写起，哪怕你根本不知道为什么要这么做，只要在前面加一个“特征根法”老师就会放你过了.（应该吧） 以后，只要你看见哪里有一个形如

的方程，把

看成

看成

看成1,解掉

这个特征方程求出

,把

写成

的形式，再利用

的值（或其他的，题一般给这两个，因为最好算）求出:

这个方程中的

就好了。 评语 如果你看到了这里，可能会对上面的证明过程有一些疑惑：这算哪门子证明过程？

就一定可以写成

的形式吗？“特征根法”又是什么东西？为什么要把{

}设为一个等比数列？又不是所有的数列都是等比数列！凭什么要这么做？解出

就可以把所有形如

的数列都表达成

吗？理论依据在哪呢？ 事实上，当笔者初次看到类似于以上对特征根法的解释时，也是这么想的：

注：初次见到特征根法时做的批注，来源[张垚《组合数学》] 于是我们需要一种更严谨的证法。而这首先需要用到一点线性代数的知识。 背景知识：矩阵变换，特征矩阵 在一些数学教材里，你会看到向量会被这样子表示出来：

把他们组合起来，就形成了一个矩阵：

而这个是一个单位矩阵：

，它代表平面上的向量

和

来源：3blue1brown 把这两个矩阵相乘，我们就对这个矩阵做了一次变换：

来源：3blue1brown

可以看到，在变换中，红色箭头方向变了，但绿色的却没有。我们把绿色箭头这种方向不变的向量成为特征向量，它被放大或缩小的倍数称为特征值（

）。 我们来看看红色箭头代表的

和绿色箭头代表的

经过矩阵变换后分别变成了什么样子：

可以看到，红色箭头换了方向，而绿色箭头则没换，而是被延长了三倍。

来源：3blue1brown 事实上，还有一个不太明显的向量也没有变方向，它就是

，我们暂且叫它黄色向量. 它的特征值，也就是它被拉伸的倍数，是2. 在

的矩阵变换中，除了绿色向量和黄色向量，其他向量都会变方向。

来源：3blue1brown 把两个没有变方向的向量组合起来，就变成了特征向量矩阵

： 一般来说，

乘以某个矩阵后都会变成另外一个矩阵，我们用

表示。 但是特征向量矩阵

不同。它乘

以后还是

,只不过这里面的的向量们被乘以了属于它们的特征值。这个由特征值组成的矩阵叫做对角矩阵。由大写的

表示：

所以

就变成了

. 于是

就变成了

. 把等号左边的

挪到右边，等式就变成了

. 这个

有个特征，即在

个

相乘等于

个

相乘：

利用

我们就可以严谨地证明斐波那契数列地通项公式了。

正文部分

斐波那契数列通项公式的证明 设斐波那契数列为

构造一个方程组：

我们知道，斐波那契数列的前几项是

令

. 设

为

，

.这解释了为什么

有点像一个等比数列。 将

分解成

的形式，我们需要求出

的特征根

. 这也是“特征根法”的来源。

得到

。这就是

的特征方程。解得

根据两个

求出

的两个值

再根据这两个特征向量写出

。 首先

求出

。通过这个矩阵是独立的，所以将

看作

和

的组合，即

等于某些实数

乘以

，

，即

解出

，得

现在通过

求出

. 把

化为矩阵

, 则

. 所以

最后，在斐波那契数列中

.利用

求出

的通式:

证明方法参考Gilbert Stang, Introduction to Linear Algebra. 二元线性齐次递推数列的推广 猜想：现在我们已知对于任意

但是

是什么？如果说我们能证明任意

都是

的形式的话，那么对于所有

就一定可以被表达成

。所以证明

的关键在于，特征向量矩阵

可以被表达成

的形式。 证明：

从一个简单的例子开始。设

，则

，

，求出

的特征根

。

然后求出X.

得

可以看到，

的特征向量矩阵也是

。 所以，我们推广至所有的

，则

，利用

求出它的特征根为：

用

求出

:

同理，把相同的步骤用于

, 我们就会发现当

是

时，

所以在二元线性递推数列中，特征向量矩阵X可以被表达成

的形式。

k元线性齐次递推数列的推广 那么k元线性齐次递推数列也符合这个规律吗？换句话说，对于一个k元线性齐次递推数列(这里用k表示n),

的特征向量矩阵是否也可以被表达成：

的形式？ 我们构造以下矩阵：

再根据k元一次方程构造矩阵

:

在2元线性齐次递推数列中，

中的

可以利用二次方程求根公式求出来，但是在k元线性齐次递推数列中却不会有

的求根公式

。我们不妨暂且不求，而是跳过这一步，直接观察

这个矩阵有什么特性使其有特定的

使

设

的解为

，则

我们的猜想是

， 将其带入方程，得

易知，除第一行以外，其他行的和都是0. 那么怎么证明第一行也是0呢？这需要利用到余子式（cofactor）. 设

的第一行第一列为

,第一行第二列为

, 它们的余子式为

, 以此类推。 观察

的余子式，它是

，其中

是

的符号模式，

。

则是

的值。

的一个很巧妙的地方在于，

的余子式都恰好是

个

的乘积。所以

把第二项移到等号右边，得

这正是我们要证明的。于是对于每个特征根

都成立，

全部解集

， 特征向量方程为

命题得证。