方法一：利用特征方程（线性代数解法）
斐波那契 f(n+1) = f(n)+f(n-1)
线性递推数列的特征方程为：
X^2=X+1
解得
X1=(1+√5)/2, X2=(1-√5)/2.
则F(n)=C1*X1^n + C2*X2^n
∵F(1)=F(2)=1
∴C1*X1 + C2*X2=C1*X1^2 + C2*X2^2=1
解得C1=1/√5，C2=-1/√5
∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5】
X^2=X+1
解得
X1=(1+√5)/2, X2=(1-√5)/2.
则F(n)=C1*X1^n + C2*X2^n
∵F(1)=F(2)=1
∴C1*X1 + C2*X2=C1*X1^2 + C2*X2^2=1
解得C1=1/√5，C2=-1/√5
∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}【√5表示根号5】
缺点是计算机中浮点数不准确
方法二：矩阵
(f_n,f_n-1) = (f_n-1,f_n-2)*A
1 1
A ={ } 这个矩阵太丑了。。。
1 0
所以 (f_n,f_n-1) = (f_1,f_0) * A^n-1
然后就是矩阵的幂乘法，，，利用快速幂可求
如果是f(k) = f(k-1)+f(k-2)+f(k-3)
那么
1 1 0
A = { 1 0 1 }
1 0 0
这种注意观察就可以了。