斐波那契数列

今天在B站看到一个视频《斐波那契数列，全网最优解》，UP主给出了求解斐波那契数列通项公式的推导思路。

因为我早年也对这种数列有过研究，而且记得一个更简单的解法，所以记录一下。

斐波那契数列是这样一种数列：

a(1) = a(2) = 1

a(n) = a(n-1) + a(n-2), n>=2

上面是通过递推公式的形式给出的定义，我们注意到递推公式是前两项的线性组合。而线性变换可以通过矩阵表示，我们不妨转换思路来求向量

$$(a_n, a_{n+1})$$

的通项公式

我们写出根据a(n-1), a(n)推得a(n), a(n+1)的递推公式

$$\begin{cases} a_n = a_n \\ a_{n+1} = a_{n-1} + a_n \end{cases}$$

写成矩阵的形式

$$\begin{pmatrix}a_n & a_{n+1} \\ \end{pmatrix} = \begin{pmatrix}a_{n-1} & a_n \\ \end{pmatrix} \begin{bmatrix}0 & 1 \\ 1 & 1\\ \end{bmatrix}$$

我们可以看到这就类似等比数列的递推公式，只不过公比q是个矩阵，等比数列通项公式是

$$a_n = a_1 * q^{n-1}$$

类比得到，上面递推公式的通项公式

$$\begin{pmatrix}a_n & a_{n+1} \\ \end{pmatrix} = \begin{pmatrix}a_1 & a_2 \\ \end{pmatrix} \begin{bmatrix}0 & 1 \\ 1 & 1\\ \end{bmatrix}^{n-1} = \begin{pmatrix}1 & 1 \\ \end{pmatrix} \begin{bmatrix}0 & 1 \\ 1 & 1\\ \end{bmatrix}^{n-1}$$

BTW: 其实这里矩阵和数还是有点区别的，要利用矩阵乘法有结合律（本来是先做向量和矩阵乘法的，通项公式是先做了后面的矩阵乘法最后再让向量左乘矩阵），而且是方阵才能求幂，而这里都是满足的。

对于斐波那契数列的变形也特别容易推导，无论是改变首项还是改变递推关系，包括把两项和变成前n项的线性组合，只要还是线性的，就可以这么推导。