斐波那契数列大家应该非常熟悉, 这是一个典型的递归定义的数列. 那么这样一个递归定义的数列的通项式是怎样的, 它又是如何推导出来的呢? 这里我们从寻找矩阵的 n 次方说起.
矩阵的 n 次方
首先只有方阵才有与自己相乘, 所以我们实际讨论的是方阵的 n 次方. 为了高效地求得一个 $m\times m$ 的矩阵 $A$ 的 n 次方 $A^n$, 我们的做法是找到一个矩阵 $P$ 和一个对角矩阵 $B$, 使得 $B=P^{-1}AP$. 这个过程称为矩阵的对角化(Diagonalize). 因为有 $B=P^{-1}AP$, 必然有 $A=PBP^{-1}$. 所以
\[A^n = (PBP^{-1})^n = (PBP^{-1})(PBP^{-1})...(PBP^{-1}) = PB^nP^{-1}\]因为 $B$ 是对角矩阵, 所以我们就可以很快地求出 $A^n$ 了.
为了对角化矩阵, 我们需要找到所有的实数 $\lambda$ 和非零单位向量 $v$ 使得
\[Av=\lambda v \tag 1\]成立. 实数 $\lambda$ 就被称为矩阵 $A$ 的特征值, 与之对应的向量 $v$ 就被称为矩阵 $A$ 的特征向量. 这也就是说对于向量 $v$ 来说, 乘上矩阵 $A$ 和乘上实数 $\lambda$ 的效果是一样的.
我们在 $Av=\lambda v$ 右边乘上单位矩阵 $I$, 可以转换成 $(A-\lambda I)v=0$. 把 $v$ 看作未知数, 这就是个齐次线性方程. 因为 $v$ 是非零向量, 也就是说这个方程要有非零解; 而 $(A-\lambda I)$ 是方阵, 这样的齐次线性方程有非零解的条件就是 $|A-\lambda I|=0$. 解这个方程就可得到若干个特征值 $\lambda_1, \lambda_2, …$. 然后把这些特征值带入 (1) 式, 就可得到每个特征值对应的特征向量.
以 \(A = \begin{pmatrix} 4 & -12\\ -12 & 11 \end{pmatrix}\) 为例. 首先我们解方程 $|A-\lambda I|=0$
\[\begin{vmatrix} 4 - \lambda & -12\\ -12 & 11 - \lambda \end{vmatrix} = 0 \\ (4 - \lambda)(11 - \lambda) - 144 = 0 \\ \lambda^2 - 15\lambda - 100 = 0 \\ (\lambda - 20)(\lambda + 5) = 0 \\ \lambda_1 = 20, \lambda_2 = -5\]得到两个特征值 $\lambda_1 = 20, \lambda_2 = -5$. 然后我们分别将 $\lambda_1, \lambda_2$ 代入 (1) 式, 得到关于每个特征向量的方程. 注意到特征向量是单位向量, 因此每个方程都有唯一解.
对于 $\lambda_1 = 20$,
\[\left\{\begin{matrix} \begin{pmatrix} 4 & -12\\ -12 & 11 \end{pmatrix} \begin{pmatrix} x_1\\y_1 \end{pmatrix} = 20 \begin{pmatrix} x_1\\y_1 \end{pmatrix} \\ x_1^2 + y_1^2 = 1 \end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} 4x_1 - 12y_1 = 20x_1\\ -12x_1 + 11y_1 = 20y_1\\ x_1^2 + y_1^2 = 1 \end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} 4x_1 + 3y_1 = 0 \\ x_1^2 + y_1^2 = 1 \end{matrix}\right. \\ v_1 = \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} = \begin{pmatrix} 3/5 \\ -4/5 \end{pmatrix}\]对于 $\lambda_1 = -5$,
\[\left\{\begin{matrix} \begin{pmatrix} 4 & -12\\ -12 & 11 \end{pmatrix} \begin{pmatrix} x_2\\y_2 \end{pmatrix} = -5 \begin{pmatrix} x_2\\y_2 \end{pmatrix} \\ x_2^2 + y_2^2 = 1 \end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} 4x_2 - 12y_2 = -5x_2\\ -12x_2 + 11y_2 = -5y_2\\ x_2^2 + y_2^2 = 1 \end{matrix}\right. \Leftrightarrow \left\{\begin{matrix} 3x_2 - 4y_2 = 0 \\ x_2^2 + y_2^2 = 1 \end{matrix}\right. \\ v_2 = \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = \begin{pmatrix} 4/5 \\ 3/5 \end{pmatrix}\]求得特征向量和特征值之后, 我们就可以对角化矩阵了. 假设一个 $m\times m$ 的矩阵 $A$ 有 m 个不同的特征值和特征向量, 我们以特征向量为列向量构造矩阵 $P = (v_1, v_2, …, v_m)$. 那么有
\[AP = A(v_1, v_2, ..., v_m) \\ = (Av_1, Av_2, ..., Av_m) \\ = (\lambda_1 v_1, \lambda_2 v_2, ..., \lambda_m v_m) \\ = (v_1, v_2, ..., v_m)\begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & ... & \\ & & & \lambda_m \end{pmatrix}\]我们记对角矩阵 \(\begin{pmatrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & ... & \\ & & & \lambda_m \end{pmatrix}\) 为 $B$, 所以有 $AP = PB$. 因为 $A$ 有 m 个不同的特征值, 所以这些特征值对应的特征向量是线性无关的(证明略). 因此矩阵 $P$ 的逆存在, 所以有 $A=PBP^{-1}$ 和 $B=P^{-1}AP$. 这就完成了矩阵的对角化.
我们还以 \(A = \begin{pmatrix} 4 & -12\\ -12 & 11 \end{pmatrix}\) 为例, $A$ 有两个特征值 $\lambda_1 = 20, \lambda_2 = -5$ 和与之对应的特征向量 \(v_1 = \begin{pmatrix} 3/5 \\ -4/5 \end{pmatrix}, v_2 = \begin{pmatrix} 4/5 \\ 3/5 \end{pmatrix}\). 因此 \(P = \begin{pmatrix} 3/5 & 4/5 \\ -4/5 & 3/5 \end{pmatrix}\) 和 \(B = \begin{pmatrix} 20 & 0 \\ 0 & -5 \end{pmatrix}\). 可以计算出
\[A^n = \begin{pmatrix} 3/5 & 4/5 \\ -4/5 & 3/5 \end{pmatrix} \begin{pmatrix} 20^n & 0 \\ 0 & -5^n \end{pmatrix} \begin{pmatrix} 3/5 & 4/5 \\ -4/5 & 3/5 \end{pmatrix}^{-1} \\ = \frac{1}{25} \begin{pmatrix} 9 \cdot 20^n + 12(-5)^n & -12 \cdot 20^n + 12(-5)^n \\ -12 \cdot 20^n + 12(-5)^n & -16 \cdot 20^n + 9(-5)^n \end{pmatrix}\]斐波那契数列的通项式
斐波那契数列 $F_n$ 定义 $F_1 = F_2 = 0$, 且 $F_n = F_{n-1} + F_{n-2}$. 因此我们有
\[\begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} F_{n+1} + F_n \\ F_{n+1} \end{pmatrix} \\ = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} \\ = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2 \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix} \\ ... \\ = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_2 \\ F_1 \end{pmatrix} \\ = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 1 \end{pmatrix} \tag 2\]问题转换成求矩阵 \(\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}\) 的 n 次方.
那么我们首先求解方程 $|A-\lambda I| = 0$:
\[\begin{vmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{vmatrix} = 0 \\ \lambda^2 - \lambda - 1 = 0 \\ \lambda_1 = \frac{1+\sqrt 5}{2}, \lambda_2 = \frac{1-\sqrt 5}{2}\]又根据 (1) 式, 有
\[\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} = \lambda_1 \begin{pmatrix} x_1 \\ y_1 \end{pmatrix} \\ \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = \lambda_2 \begin{pmatrix} x_2 \\ y_2 \end{pmatrix}\]可得 \(v_1 = \begin{pmatrix} \lambda_1 \\ 1 \end{pmatrix}, v_2 = \begin{pmatrix} \lambda_2 \\ 1 \end{pmatrix}\). 所以 \(P = \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix}, B = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix}\).
接下来求 $A^n$:
\[A^n = \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{pmatrix} \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix}^{-1} \\ = \begin{pmatrix} \lambda_1 & \lambda_2 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \lambda_1^n & 0 \\ 0 & \lambda_2^n \end{pmatrix} \frac{1}{\sqrt 5}\begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \\ = \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^{n+1} & \lambda_2^{n+1} \\ \lambda_1^n & \lambda_2^n \end{pmatrix} \begin{pmatrix} 1 & -\lambda_2 \\ -1 & \lambda_1 \end{pmatrix} \\ = \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^{n+1} - \lambda_2^{n+1} & \lambda_1^n - \lambda_2^n \\ \lambda_1^n - \lambda_2^n & \lambda_1^{n-1} - \lambda_2^{n-1} \end{pmatrix}\]由 (2) 式得
\[\begin{pmatrix} F_{n+2} \\ F_{n+1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 1 \end{pmatrix} = \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^{n+1} - \lambda_2^{n+1} & \lambda_1^n - \lambda_2^n \\ \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+1} - \lambda_2^{n+1} + \lambda_1^n - \lambda_2^n \\ \lambda_1^n - \lambda_2^n + \lambda_1^{n-1} - \lambda_2^{n-1} \end{pmatrix} = \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^n(\lambda_1+1) - \lambda_2^n(\lambda_2 + 1) \\ \lambda_1^{n-1}(\lambda_1+1) - \lambda_2^{n-1}(\lambda_2 + 1) \end{pmatrix} \\ = \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^n\lambda_1^2 - \lambda_2^n\lambda_2^2 \\ \lambda_1^{n-1}\lambda_1^2 - \lambda_2^{n-1}\lambda_2^2 \end{pmatrix} = \frac{1}{\sqrt 5} \begin{pmatrix} \lambda_1^{n+2} - \lambda_2^{n+2} \\ \lambda_1^{n+1} - \lambda_2^{n+1} \end{pmatrix}\]最后我们得到斐波那契数列的通项公式为
\[F_n = \frac{1}{\sqrt 5}(\lambda_1^n - \lambda_2^n) = \frac{(\frac{1+\sqrt 5}{2})^2 - (\frac{1-\sqrt 5}{2})^2}{\sqrt 5}\]参考资料