斐波那契数列大家应该非常熟悉, 这是一个典型的递归定义的数列. 那么这样一个递归定义的数列的通项式是怎样的, 它又是如何推导出来的呢? 这里我们从寻找矩阵的 n 次方说起.
矩阵的 n 次方
首先只有方阵才有与自己相乘, 所以我们实际讨论的是方阵的 n 次方. 为了高效地求得一个 的矩阵 的 n 次方 , 我们的做法是找到一个矩阵 和一个对角矩阵 , 使得 . 这个过程称为矩阵的对角化(Diagonalize). 因为有 , 必然有 . 所以
因为 是对角矩阵, 所以我们就可以很快地求出 了.
为了对角化矩阵, 我们需要找到所有的实数 和非零单位向量 使得
成立. 实数 就被称为矩阵 的特征值, 与之对应的向量 就被称为矩阵 的特征向量. 这也就是说对于向量 来说, 乘上矩阵 和乘上实数 的效果是一样的.
我们在 右边乘上单位矩阵 , 可以转换成 . 把 看作未知数, 这就是个齐次线性方程. 因为 是非零向量, 也就是说这个方程要有非零解; 而 是方阵, 这样的齐次线性方程有非零解的条件就是 . 解这个方程就可得到若干个特征值 . 然后把这些特征值带入 (1) 式, 就可得到每个特征值对应的特征向量.
以 为例. 首先我们解方程
得到两个特征值 . 然后我们分别将 代入 (1) 式, 得到关于每个特征向量的方程. 注意到特征向量是单位向量, 因此每个方程都有唯一解.
对于 ,
对于 ,
求得特征向量和特征值之后, 我们就可以对角化矩阵了. 假设一个 的矩阵 有 m 个不同的特征值和特征向量, 我们以特征向量为列向量构造矩阵 . 那么有
我们记对角矩阵 为 , 所以有 . 因为 有 m 个不同的特征值, 所以这些特征值对应的特征向量是线性无关的(证明略). 因此矩阵 的逆存在, 所以有 和 . 这就完成了矩阵的对角化.
我们还以 为例, 有两个特征值 和与之对应的特征向量 . 因此 和 . 可以计算出
斐波那契数列的通项式
斐波那契数列 定义 , 且 . 因此我们有
问题转换成求矩阵 的 n 次方.
那么我们首先求解方程 :
又根据 (1) 式, 有
可得 . 所以 .
接下来求 :
由 (2) 式得
最后我们得到斐波那契数列的通项公式为
参考资料