Fib 数列的性质

### 通项公式 $$ f(n)=\frac{1}{\sqrt 5}\left((\frac{1+\sqrt 5}{2})^n-(\frac{1-\sqrt 5}{2})^n\right) $$ ### 常用恒等式 $$ f(1)+f(2)+f(3)+...+f(n)=f(n+2)-1 $$ $$ f(1)^2+f(2)^2+f(3)^2+...+f(n)^2=f(n)f(n+1) $$ $$ f(1)+f(3)+f(5)+...+f(2n-1)=f(2n) $$ $$ f(2)+f(4)+f(6)+...+f(2n)=f(2n+1)-1 $$ $$ f(m)f(n-m+1)+f(m-1)f(n-m)=f(n) $$ $$ f(n-1)f(n+1)=f(n)^2+(-1)^n $$ 其中，对于第 $5$ 个恒等式，可以通过不断展开的方式得到。 ### 常用性质 **性质 $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))$，于是可以推出 $\gcd(f(n),f(m))=f(\gcd(n,m))$。 于是有引理，$f$ 相邻两项互质。因为 $\gcd(f(n),f(n-1))=f(\gcd(n,n-1))=f(1)=1,\forall n\in N^+$。 **性质 $2$**：$n|m \Leftrightarrow f(n)|f(m)$ 对于 $n|m \Rightarrow f(n)|f(m)$，因为有 $\gcd(f(n),f(m))=f(\gcd(n,m))=f(n)$。 对于 $f(n)|f(m) \Rightarrow n|m$，说明 $\gcd(f(n),f(m))=f(n)$，而又有 $\gcd(f(n),f(m))=f(\gcd(n,m))$，故 $\gcd(n,m)=n$，定有 $n|m$。 **性质 $3$**：对于 $F(0)=a,F(1)=b,F(n)=F(n-1)+F(n-2)$，有 $F(n)=bf(n)+af(n-1)$。 需要用到一个扩展恒等式：$F(n)=f(m)F(n-m+1)+f(m-1)F(n-m)$，令 $n-m=0$，则有 $F(n)=f(n)F(1)+f(n-1)F(0)=bf(n)+af(n-1)$，有些时候也被写作 $F(n)=f(n-2)F(1)+f(n-1)F(2)=af(n-2)+bf(n-1)$