斐波那契数列规律总结

1.模除周期性

2.和的性质

$\ f_{n-1}\times f_{n+1}-f_n^2 = (-1)^n$

$\ f_1+f_3...+f_{2n-1} = f_{2n}-f_2+f_1$

$\ f_2+f_4...+f_{2n} = f_{2n+1}-f_1$

$\ f_1^2+f_2^2...+f_n^2 = f_n \times f_{n+1}$

3.两倍项关系

$\ f_{2n}/f_n=f_{n-1}+f_{n+1}$

4.尾数循环

个位数：周期60
最后两位：300
最后三位：1500

5.gcd(F[n],F[m])=F[gcd(n,m)]

证明：

我们设n<m，F[0]=0,F[1]=1,F[2]=1;F[n]=a和F[n+1]=b
F[n+2]=F[1]a+F[2]b,（1，1）
F[n+3]=F[2]a+F[3]b,（1，2）
F[n+4]=F[3]a+F[4]b,（2，3）
F[n+5]=F[4]a+F[5]b，（3，5）
…
F[n+(m-n)]=F[m−n−1]a+F[m−n]b
所以：F[m]=F[m−n−1]∗F[n]+F[m−n]∗F[n+1]

gcd(F[n],F[m])=gcd(F[n],F[m−n−1]∗F[n]+F[m−n]∗F[n+1])
gcd(a+bn,b)=gcd(b,a)=gcd(a,b);(辗转相除的思想)
所以：gcd(F[n],F[m−n−1]∗F[n]+F[m−n]∗F[n+1])=gcd(F[n],F[m−n]∗F[n+1])
因为：gcd(F[n],F[n+1])=1
gcd(F[n],F[m])=gcd(F[n],F[m−n]∗F[n+1])
gcd(F[n],F[m])=gcd(F[n],F[m−n]);（这步操作可以进行多次）
所以：gcd(F[n],F[m])=gcd(F[n],F[m mod n])
继续递归，将m1=m mod n，
则gcd(F[n],F[m])=gcd(F[n mod m1],F[m1])
不难发现，整个递归过程其实就是在求解gcd(n,m)
∴gcd(F[n],F[m])=gcd(F[gcd(n,m)],0)=F[gcd(n,m)]

ps：gcd(F[n],F[n+1])=1的证明（辗转相减法）

gcd(F[n],F[n+1])
=gcd(F[n],F[n+1]−F[n])
=gcd(F[n],F[n−1])
=gcd(F[n−2],F[n−1])
=gcd(F[1],F[2])
=1