斐波那契数列通项公式推导

数学课摸鱼石锤

这是我们幼儿园大班就认识的兔子数列：

这应该很显然吧：

不认识矩阵的话建议看看 3b1b 的《线性代数的本质》.

其实现在就可以用快速幂在 O(log n) 时间内求出 fn 了，快去试试叭~

设 ，现在求. 首先求出它的两个特征值：

然后求两个线性无关的特征向量：

然后：

我们知道：

于是：

就这？就这. 也就一面 A4 草稿纸的计算量而已

附： Python 代码：

懒得写高精度就去用 Python 的屑

凑字数凑字数凑字数凑字数凑字数