#斐波那契数列（Fibonacci）性质及拓展

斐波那契数列，一个简单而神秘的序列。

斐波那契数列（Fibonacci）相信大家一定很熟悉了，下面简单介绍一下斐波那契数列的一些内容。

#定义

这样的序列称为斐波那契数列：

F[0]=0
F[1]=1
F[n]=F[n-1]+F[n-2]

斐波那契数列还有一个通项公式：

$a_n= \frac{1}{\sqrt{5}}\left [ {\left ( {\frac{1+\sqrt{5}}{2}} \right )^n-{}\left ( {\frac{1-\sqrt{5}}{2}} \right )^n} \right ]$

最初斐波那契数列是由兔子的繁殖问题转化而来的，表示的是在理想状态下第n个月兔子的数目。当然这不是本文讨论的重点。

#Fibonacci数列的性质

1. gcd(fib(n),fib(m))=fib(gcd(n,m))

证明： 可以通过反证法先证fibonacci数列的恣意相邻两项一定互素，然后可证n>m时gcd(fib(n),fib(m))=gcd(fib(n-m),fib(m))，递归即可 求gcd(fib(n),fib(m))=gcd(fib(k),fib(l))，最后k=l，不然继承递归。K是通过展转相减法求出，易证k=gcd(n,m)，所以gcd(fib(n),fib(m))=fib(gcd(n,m))。

2. 如果fib(k)能被x整除，则fib(k * i)都可以被x整除。
3. f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1
4. f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)
5. f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1
6. [f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)
7. f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1
8. f(m+n)=f(m-1)·f(n-1)+f(m)·f(n)
9. [f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)
10. f(2n-1)=[f(n)]^2-[f(n-2)]^2
11. 3f(n)=f(n+2)+f(n-2)
12. f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]

#斐波那契素数（Fibonacci Prime）

斐波那契素数是指：若某Fibonacci数与任何与它小的Fibonacci数互质，那么就称这个数为Fibonacci素数。

哪些数才是斐波那契数列素数呢？

1. F(3)和F(4)是Fibonacci素数；从F(5)开始，某项为Fibonacci质数当且仅当它的项数为质数
2. 第k小的Fibonacci素数是以素数数列中的第k个数为项数的Fibonacci数( 除F(3)和F(4)之外 )
3. 反例：F(2)=1，不是Fibonacci素数；F(4)=3不满足第二条，但是它是Fibonacci素数

最终结论：Fibonacci序列中的第3,4,5,7,11,13,17,19,23,29,...为Fibonacci素数。

ps:证明神马的大家可以看参考资料。

#与杨辉三角的关系

将杨辉三角左对齐，将同一斜行的数加起来，即得一数列1、1、2、3、5、8、……

#参考内容

• 证明nullfibonacci数列的性质(ZOJ3707) - xinyuyuanm
• fibonacci数列的性质(ZOJ3707) - ACdreamers
• 【原】斐波那契质数(Fibonacci Prime)详解 - Allen Sun
• 斐波那契数列_百度百科