Fib 数列的性质
tommymio
·
·
个人记录
通项公式
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)