1、1、2、3、5、8、13、21……每一项等于前两项之和，这就是斐波那契数列。它的通项公式长得漂亮，还带着根号和黄金比。

F(n)=(φ^n−ψ^n)/√5，其中φ=(1+√5)/2，ψ=(1−√5)/2。n从1开始代入，算出来正好是1、1、2、3、5，和数列完全吻合。

通项公式怎么推的

标准套路是特征方程法。递推关系F(n)=F(n−1)+F(n−2)对应特征方程x²=x+1，即x²−x−1=0，解出两个根φ和ψ。通项设成A·φ^n+B·ψ^n，用F(1)=1、F(2)=1两个初始条件解出A=B=1/√5，公式到手。这套方法对所有常系数线性递推都管用，换别的递推数列照样能推。

ψ是负数且绝对值小于1，n越大ψ^n越接近0，所以有个实用近似：F(n)≈φ^n/√5，误差随n增大迅速消失。工程上算很大的项，多数直接用这个近似，精度完全够。

这个数列的出身也有意思：1202年斐波那契在算兔子繁殖问题，一对兔子每月生一对，小兔子一个月后成熟，第n个月的兔子对数正好是这个数列。向日葵种子、松果鳞片的排列里也常见相邻的斐波那契数，不过别过度神化它。

几个有意思的性质

  • 相邻两项之比F(n+1)/F(n)趋于1.618，正是黄金分割数φ，反过来F(n)/F(n+1)趋于0.618
  • 恒等式F(1)+F(2)+…+F(n)=F(n+2)−1，数学归纳法两步证完
  • 斐波那契数藏在杨辉三角的斜线上，沿斜线求和就得到

不想碰通项公式还有矩阵快速幂：把递推写成矩阵乘法，配合快速幂，O(log n)时间内算出F(n)。算法竞赛里求斐波那契数列第10^18项这种天文数字，靠的就是它。写代码时另注意，朴素递归会重复计算，F(40)就要算几百万次，加记忆化或改成循环递推，瞬间出结果。

实际判断：手算小项直接递推最快；要通项或者大数项，记住φ=(1+√5)/2这个黄金比，公式和近似都从它出发。特征方程这一套学会了，一类递推题都跟着解锁。