常用Fibonacci数性质

常用Fibonacci数性质

0.Fn−1+Fn−2=Fn，特殊的F0=1,F1=1
上述式子为定义式

1.F(0) + F(1)+ … + F(n) = F(n+2) − 1
证明：

F0+F1=F2

F1+F2=F3

F2+F3=F4

⋮

Fn+Fn+1=Fn+2

F0+2F1+2F2+…+2Fn+Fn+1=F1+F2+…+Fn+2

F0+F1+F2+…+Fn+Fn+1=Fn+2−F1=Fn+2−1

2.F(1) + F(3) + … + F(2n−1) = F(2n)
证明：

F1=F0+1

F3=F2+F1

⋮

F2n−1=F2n−2+F2n−3

F1+F3+…+F2n−1=1+F0+F1+F2+…+F2n−3+F2n−2=1+F2n−1=F2n

3.F(0) + F(2) + … + F(2n) = F(2n+1) − 1
证明：

有 F0+F1+…+Fn=Fn+2−1 和 F1+F3+…+F2n−1=F2n

F0+F2…+F2n=F2n+2−F2n−1=F2n+1−1
4.F(0)^2 + F(1)^2 + F(2)^2 + … + F(n)^2 = F(n)F(n+1)
证明：

有 F20=F0∗F1 ，假设有 F20+F21+F22+…+F2n−1=Fn−1Fn

那么 F20+F21+…+F2n−1+F2n=Fn−1Fn+F2n=FnFn+1

5 . 从第二项开始，每个偶数项的平方都比前后两项之积多1，每个奇数项的平方都比前后两项之积少1。

6.F(n+2) + F(n−2) = 3 × F(n)
证明：

Fn+2=Fn+1+Fn=(Fn+Fn−1)+Fn=(Fn+(Fn−Fn−2))+Fn=3×Fn−Fn−2

7.gcd( F(n+1) , F(n) ) = 1
证明：
根据辗转相减法则
gcd(Fn+1,Fn)=gcd(Fn+1−Fn,Fn)=gcd(Fn,Fn−1)=gcd(F2,F1)=1
8. F(m+n) = F(m−1)F(n) + F(m)F(n+1)
把Fn看做斐波那契的第1项，那么到第Fn+m项时，系数为Fm−1

把Fn+1看做斐波那契的第2项，那么到第Fn+m项时，系数为Fm

9.gcd( F(n+m) , F(n) ) = gcd( F(n) , F(m) )
证明：
gcd(Fn+m,Fn)=gcd(Fn+1Fm+FnFm−1,Fn)=gcd(Fn+1Fm,Fn)=gcd(Fm,Fn)

10.gcd( F(n) , F(m) ) = F( gcd(n,m) )
由8式得，Fibonacci数满足下标的辗转相减

gcd(Fn,Fm)=gcd(Fgcd(n,m)，Fgcd(n,m))=Fgcd(n,m)