接头霸王
众所周知，斐波那契数列的通项公式为：
\[f_n=\frac{1}{\sqrt 5}\left[\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n\right]
\]
但各位先放下手中的 OGF，通过线代也可以推出来这个结果
先来几个概念（在这里假设您知道线代基础知识）：
- 线性算子
- 即为将向量空间映射为它本身的线性映射
- 特征值与特征向量
- 设 \(\mathrm T\) 为定义在 \(V\rightarrow V\) 上的算子，特征值则为满足 \(\mathrm Tv=\lambda v,v\in V,\lambda\in \mathbf{C}\) 的 \(\lambda\)，特征向量 \(v\) 则为满足上式的向量
- 容易得出，如果一个特征值 \(\lambda\) 有一个对应的特征向量 \(v\)，则 \(u\in \operatorname{span}(v)\) 也是 \(\lambda\) 所对应的特征向量
- 特征值 \(\lambda\) 与它所对应的特征向量 \(v\) 显然还有这个性质：\(\mathrm T^nv=\lambda^nv\)
- 不显然的一点是不同的特征值所对应的特征向量线性无关，在这里不做出证明
设 \(\mathbf R^2\to \mathbf R^2\) 的算子 \(\mathrm T\) 定义如下：
\[\mathrm T(x,y)=(y,x+y)
\]
则容易得出 \(\mathrm T^n(0,1)=(f_n,f_{n+1})\)
求出算子的两个特征值分别为 \(\lambda_1=\frac{1+\sqrt5}{2}\)，\(\lambda_2=\frac{1-\sqrt5}{2}\)
然后求出相对应的一个特征向量分别为 \(v_1=(1,\frac{1+\sqrt5}{2})\)，\(v_2=\frac{1-\sqrt5}{2}\)
所以：
\[\begin{aligned}
\mathrm T^n(0,1)&=\frac{1}{\sqrt5}\mathrm T^n\left(v_1+v_2\right)\\
&=\frac{1}{\sqrt5}\left(\lambda_1^nv_1+\lambda_2^nv_2\right)
\end{aligned}
\]
然后就导出了斐波那契通项公式
显然这个是可扩展的，但这个东西的缺点显而易见：
- 非整数甚至非实数的特征值不适合数值计算
- 可能特征向量并不组成向量空间的基
- 特征值不好算，对于复杂情况只能求近似解
但这个东西还是相当 educational 的，所以写出来发一下