一、构造递推矩阵

将递推公式写为矩阵形式：

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

设递推矩阵为：

$A = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$

则有：

$\begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = A^{n-1} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix} = A^{n-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix}$

二、对角化矩阵 ( A )

1. 求特征值

解特征方程：

$\det(A - \lambda I) = \begin{vmatrix} 1 - \lambda & 1 \\ 1 & -\lambda \end{vmatrix} = (1 - \lambda)(-\lambda) - 1 = \lambda^2 - \lambda - 1 = 0$

求得：

$\lambda_1 = \phi = \frac{1 + \sqrt{5}}{2},\quad \lambda_2 = \bar{\phi} = \frac{1 - \sqrt{5}}{2}$

2. 求特征向量

对于 $\lambda_1 = \phi$ ，解：

$(A - \phi I)\vec{v} = 0 \Rightarrow \vec{v}_1 = \begin{bmatrix} \phi \\ 1 \end{bmatrix}$

对于 $\lambda_2 = \bar{\phi}$ ，解：

$\vec{v}_2 = \begin{bmatrix} \bar{\phi} \\ 1 \end{bmatrix}$

3. 构造对角化形式

定义：

$P = \begin{bmatrix} \phi & \bar{\phi} \\ 1 & 1 \end{bmatrix},\quad D = \begin{bmatrix} \phi & 0 \\ 0 & \bar{\phi} \end{bmatrix}$

可得：

$A = P D P^{-1} \quad \Rightarrow \quad A^{n-1} = P D^{n-1} P^{-1}$

三、计算斐波那契通项

代入：

$\begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = A^{n-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = P D^{n-1} P^{-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix}$

我们只关心第一项 $F_n$ 。

Step 1: 计算 $P^{-1}$

因为：

$\phi - \bar{\phi} = \sqrt{5}$

所以：

$P^{-1} = \frac{1}{\sqrt{5}} \begin{bmatrix} 1 & -\bar{\phi} \\ -1 & \phi \end{bmatrix}$

Step 2: 计算乘积

依次计算：

$P^{-1} \begin{bmatrix} 1 \\ 0 \end{bmatrix} = \frac{1}{\sqrt{5}} \begin{bmatrix} 1 \\ -1 \end{bmatrix}$

$D^{n-1} \cdot \left( \frac{1}{\sqrt{5}} \begin{bmatrix} 1 \\ -1 \end{bmatrix} \right) = \frac{1}{\sqrt{5}} \begin{bmatrix} \phi^{n-1} \\ -\bar{\phi}^{n-1} \end{bmatrix}$

$P \cdot \left( \frac{1}{\sqrt{5}} \begin{bmatrix} \phi^{n-1} \\ -\bar{\phi}^{n-1} \end{bmatrix} \right) = \frac{1}{\sqrt{5}} \left( \phi \cdot \phi^{n-1} - \bar{\phi} \cdot \bar{\phi}^{n-1} \right) = \frac{1}{\sqrt{5}} \left( \phi^n - \bar{\phi}^n \right)$