斐波那契数列具有如下的形式:
F(n)=F(n−1)+F(n−2) (n≥2,n∈N∗,F(0)=1,F(1)=1)
后一项等于它的前两项之和。如果需要求解第n项,则需要n-1和n-2项,层层递进,如果在编程中,则会因为递归的深度有限无法完全很好的使用。
写成矩阵形式可以表示为如下的形式:
[F(n)F(n−1)]=[1110][F(n−1)F(n−2)]
矩阵形式很方便进行程序的递推计算,可以使用矩阵快速幂的形式进行计算。
通项公式如下,我认为一般不用记,更多的情况是初值不会从1开始。
an=51[(21+5)n−(21−5)n]
[F(n)F(n−1)]=[1110]n−1[10]