https://blog.csdn.net/lanchunhui/article/details/50569311
1. 矩阵形式的通项
(Fn+2Fn+1)=(1,1,10)⋅(Fn+1Fn)
不妨令：A=(1,1,10),F1=1,F0=0，证明，An=(Fn+1,Fn,FnFn−1)，采用数学归纳法进行证明，A1=(F2,F1,F1F0)，显然成立，
An+1=An⋅A=(Fn+1,Fn,FnFn−1)⋅(1,1,10)=(Fn+2,Fn+1,Fn+1Fn)
2. 偶数项和奇数项
因为 An=(Fn+1,Fn,FnFn−1)，则有：
A2m====(F2m+1,F2m,F2mF2m−1)Am⋅Am(Fm+1,Fm,FmFm−1)⋅(Fm+1,Fm,FmFm−1)(F2m+1+F2m,Fm(Fm+2Fm−1),Fm(Fm+2Fm−1)F2m+F2m−1)
所以有：
F2m+1=F2m+1+F2mF2m=Fm(Fm+2Fm−1)
3. 矩形形式求解 Fib(n)
因为涉及到矩阵幂次，考虑到数的幂次的递归解法：
- n 为奇数：n=2k+1
- Fn=F2k+1=F2k+1+F2k
- Fn+1=F2k+2=Fk+1(Fk+1+2Fk)
- n 为偶数：n=2k
- Fn=F2k=Fk(Fk+2Fk−1)=Fk(Fk+2(Fk+1−Fk))
- Fn+1=F2k+1=F2k+1+F2k
4. Python
def fib(n):
if n > 0:
f0, f1 = fib(n // 2)
if n % 2 == 1:
return f0**2+f1**2, f1*(f1+2*f0)
return f0*(f0+2*(f1-f0)), f0**2+f1**2
return 0, 1
if __name__ == '__main__':
print([fib(i)[0] for i in range(10)])