斐波那契 —— 矩阵形式推导

https://blog.csdn.net/lanchunhui/article/details/50569311

1. 矩阵形式的通项

(Fn+2Fn+1)=(1,1,10)⋅(Fn+1Fn) ( F n + 2 F n + 1 ) = ( 1 , 1 1 , 0 ) ⋅ ( F n + 1 F n )

不妨令： A=(1,1,10),F1=1,F0=0 A = ( 1 , 1 1 , 0 ) , F 1 = 1 , F 0 = 0 ，证明， An=(Fn+1,Fn,FnFn−1) A n = ( F n + 1 , F n F n , F n − 1 ) ，采用数学归纳法进行证明， A1=(F2,F1,F1F0) A 1 = ( F 2 , F 1 F 1 , F 0 ) ，显然成立，

An+1=An⋅A=(Fn+1,Fn,FnFn−1)⋅(1,1,10)=(Fn+2,Fn+1,Fn+1Fn) A n + 1 = A n ⋅ A = ( F n + 1 , F n F n , F n − 1 ) ⋅ ( 1 , 1 1 , 0 ) = ( F n + 2 , F n + 1 F n + 1 , F n )

2. 偶数项和奇数项

因为 An=(Fn+1,Fn,FnFn−1) A n = ( F n + 1 , F n F n , F n − 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) A 2 m = ( F 2 m + 1 , F 2 m F 2 m , F 2 m − 1 ) = A m ⋅ A m = ( F m + 1 , F m F m , F m − 1 ) ⋅ ( F m + 1 , F m F m , F m − 1 ) = ( F m + 1 2 + F m 2 , F m ( F m + 2 F m − 1 ) F m ( F m + 2 F m − 1 ) , F m 2 + F m − 1 2 )

所以有：

F2m+1=F2m+1+F2mF2m=Fm(Fm+2Fm−1) F 2 m + 1 = F m + 1 2 + F m 2 F 2 m = F m ( F m + 2 F m − 1 )

3. 矩形形式求解 Fib(n)

因为涉及到矩阵幂次，考虑到数的幂次的递归解法：

n 为奇数： n=2k+1 n = 2 k + 1 Fn=F2k+1=F2k+1+F2k F n = F 2 k + 1 = F k + 1 2 + F k 2 Fn+1=F2k+2=Fk+1(Fk+1+2Fk) F n + 1 = F 2 k + 2 = F k + 1 ( F k + 1 + 2 F k ) n 为偶数： n=2k n = 2 k Fn=F2k=Fk(Fk+2Fk−1)=Fk(Fk+2(Fk+1−Fk)) F n = F 2 k = F k ( F k + 2 F k − 1 ) = F k ( F k + 2 ( F k + 1 − F k ) ) Fn+1=F2k+1=F2k+1+F2k F n + 1 = F 2 k + 1 = F k + 1 2 + F k 2

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)])