斐波那契数列

斐波那契数列递推

$$F(1)=1,F(0)=0$$
$$F(n)=F(n-1)+F(n-2)$$

斐波那契数列的通项公式

F(n)=15[(1+52)n−(1−52)n]F(n)=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n]F(n)=5​1​[(21+5​​)n−(21−5​​)n]

斐波那契数列的一些恒等式子

$$1:F(1)+F(2)+F(3)+...+F(n)=F(n+2)-1$$
2:F(1)2+F(2)2+F(3)2+..+F(n)2=F(n)∗F(n+1)2:F(1)^2+F(2)^2+F(3)^2+..+F(n)^2=F(n)*F(n+1)2:F(1)2+F(2)2+F(3)2+..+F(n)2=F(n)∗F(n+1)
$$3:F(1)+F(3)+F(5)+..F(2n-1)=F(2n)$$
$$4:F(2)+F(4)+F(6)+..+F(2n)=F(2n+1)-1$$
$$5:F(n=F(m)F(n-m+1)+F(m-1)F(n-m)ps:n>=m$$
6:F(n−1)F(n+1)=F(n)2+(−1)n6:F(n-1)F(n + 1)=F(n)^2+(-1)^n6:F(n−1)F(n+1)=F(n)2+(−1)n

斐波那契相关性质

$$性质1：gcd(F(n),F(m))=F(gcd(n,m))$$
$$gcd(F(n),F(m))=gcd(F(m)F(n-m+1)+F(m-1)F(n-m),F(m))=gcd(F(n-m),F(m))$$
$$性质2:n|m<=>F(n)|F(m)$$