斐波那契数列

1、斐波那契数列一、简介斐波那契数列（Fibonacci ），又称黄金分割数列，由数学家斐波那契最早以“兔子繁殖问题”引入，推动了数学的发展。故斐波那契数列又称“兔子数列”。斐波那契数列指这样的数列：1,1,2,3,5,8,13,，前两个数的和等于后面一个数字。这样我们可以得到一个递推式，记斐波那契数列的第i 项为 Fi ，则 Fi =Fi-1 +Fi-2 .兔子繁殖问题指设有一对新生的兔子，从第三个月开始他们每个月都生一对兔子，新生的兔子从第三个月开始又每个月生一对兔子。按此规律，并假定兔子没有死亡，10 个月后共有多少个兔子这道题目通过找规律发现答案就是斐波那契数列，第n 个月兔子的数量是斐波

2、那契数列的第 n 项。二、性质如果要了解斐波那契数列的性质，必然要先知道它的通项公式才能更简单的推导出一些定理。那么下面我们就通过初等代数的待定系数法计算出通项公式。令常数 p,q 满足 Fn-pFn-1 =q(Fn-1 -pFn-2 ) 。则可得：Fn-pF n-1=q(F n-1 -pFn-2 )=q2(F n-2-pF n-3 )=qn-2 (F 2-pF 1)又 Fn-pF n-1 =q(Fn-1 -pF n-2 ) Fn-pF n-1 =qFn-1 -pqF n-2Fn-1 +Fn-2 -pFn-1 -qFn-1 +pqFn-2 =0(1-p-q)F n-1 +(1+pq)F n-2

3、 =0 p+q=1,pq=-1 是其中的一种方程组 Fn-pF n-1 = q n-2 (F 2-pF1)=qn-2 (1-p)=q n-1Fn=qn-1 +pFn-1 =qn-1 +p(qn-2 +p(qn-3 +)=q n-1 +pqn-2+p2qn-3+pn-1不难看出，上式是一个以p/q 为公比的等比数列。将它用求和公式求和可以得到：而上面出现了方程组p+q=1,pq=-1 ，可以得到p(1-p)=-1,p2-p-1=0 ，这样就得到了一个标准的一元二次方程，配方得p2-p+=, 2=,p= ±+。随意取出一组解即可：这就是著名的斐波那契数列通项公式。有了它，斐波那契数列的一

4、些性质也不难得出了。比如斐波那契数列相邻两项的比值趋向于黄金分割比，即：根据斐波那契数列通项公式，可以得到因为 n 是趋向于正无限的，因此我们可以知道：那么我们就可以把分子和分母的第二项同时省略掉，即这就是斐波那契数列的魅力之一它和黄金分割比有密切的关系。下面将给出斐波那契数列的几个性质及其证明。1)F 1+F2+F3+.+F n=Fn+2- 1证明：原式 =( F3-F 2)+(F 4-F 3)+.+(Fn+2-Fn+1)=Fn+2- 1.2)F 1+F3+F5+.+F 2n+1=F2n+2证明：原式=2 4 264)+.+(F2n+22n2n+2F +(F -F)+(F -F-F )=F2

5、223)F +F +.+F=F F12nnn+1证明：利用数学归纳法，显然1 时满足，下面证明若n=k时满足，1 时也满足 .n=n=k+已知2222222n+2，因此1 后仍12nn n+112n+1n n+1n+1=(Fn+1nn+1n+1F +F +.+F=FF ,F+F +.+F=FF+F+F )F=F Fn+然满足 . 上述公式成立 .4)F 1F2+F2F3+.+F nFn+ 1=(Fn+22-F nFn+1- 1)/2证明：数学归纳法，n=1 时满足 . 已知 F1F2+F2F3+.+F nFn+1 满足，那么2F1F2+F2F3+.+F nFn+1+Fn+1Fn+2=(Fn+2

6、 -F nFn+1 - 1)/2+F n+1Fn+2=(F2-FF +2F F -)/2=(F22)- FF-F2/2n+21n+2+2F F+Fn+ 1-nn+ 1n+ 1n+2n+1 n+2n+ 1n n+11=(F2-F1)/2，因此上式成立 .n+3n+ 1 n+2F -5)F2n+1n=F F +(-1)n- 1n+ 1证明：数学归纳法，n=2 时满足 . 已知前面的n 都满足，那么n2n-2n-22n-2 n-n-2n-3 n-1+(- 1)n- 1n-2 n-n-nn-2n- 1F =F1 +F+2F F1=F1+F F+2F F1=F1F +F1 +(- 1)=Fn- 1Fn+

7、1+(- 1) n+1，因此上式成立.6)F n+m=Fm-1 Fn +FmFn+ 1(n>m>1)证明：利用通项公式，设=, =1- =注意到 1/ +=sqrt(5)=1/ +,1/ +=0=1/ +,上式就变成了这就是上述公式的证明.三、斐波那契数列与自然斐波那契数列中的斐波那契数会经常出现在我们的眼前比如松果、凤梨、树叶的排列、某些花朵的花瓣数（典型的有向日葵花瓣），蜂巢，蜻蜓翅膀， 超越数 e（可以推出更多） ，黄金矩形、黄金分割、等角螺线，十二平均律等。斐波那契数还可以在植物的叶、枝、茎等排列中发现。例如，在树木的枝干上选一片叶子，记其为数0，然后依序点数叶子（假定没有

8、折损），直到到达与那些叶子正对的位置，则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中叶子数与叶子旋转圈数的比称为叶序（源自希腊词，意即叶子的排列）比。多数的叶序比呈现为斐波那契数的比。图为斐波那契弧线。关于递推式的拓展研究一、错位排列问题有 n 个数，求有多少种排列使这n 个数都不在原来的位置上。比如 n=2 时，有一种排列。设f() 表示n个数的错位排列数量，分两种情况讨论：n1.第n个数在第 () 个数的位置上，第p个数在第n个数的位置上，则此时共有p pnf ( n-2) 种选择。由于p 有 ( n-

9、1) 种值，则总共有 ( n-1)f ( n-2) 种排列方法；2. 否则，共有 ( n-1) f ( n-1) 种排列方法。综上所述， f ( n)=( n-1)( f ( n-1)+ f ( n-2) ， f (1)=0, f (2)=1 。那这个数列的通项公式是什么呢直接对这个数列不好进行操作，可以转化一下。设错位排列的概率函数为g( n) ，其中g(1)=0,g(2)=。在f ( n)的递推式两边同时除以n!即可得到。两边同时乘n 得到ng( n)=( n-1) g( n-1)+ g( n-2)n( g( n)- g( n-1)= g( n-2)- g( n-1)注意到 e-1 的泰勒

10、展开式跟它好像有点像，是因此有如下的等式：同时，我们也可以得到了函数f 的通项公式为：这就是一些关于错位排序的性质。二、类斐波那契数列的研究我们知道斐波那契数列递推式为f ( n)= f ( n-1)+f ( n-2) ，那么假如有更多项呢假设f( )=( -1)+f( -2)+f( -3) ，其中f(1)=f(2)=f(3)=1. 我们暂时称这个数列为类斐n fnnn波那契数列，那么它的通项公式又如何呢令 a, b, c 满足 f ( n)+ af ( n-1)+ bf ( n-2)= c( f ( n-1)+ af ( n-2)+ bf ( n-3)则得到 c- a=1, ac- b=1,

11、 bc=1，消元得 c3- c2- c-1=0 ，利用牛顿迭代可以计算出c=，则a=,b=所以f( )+(n-1)+bf( -2)=cn-3 (1+ + ) ，记=1+ + ，两边同时除以n构造更多的常数n afna bta bc项：为了方便，我们记，则：令 p, q, r 满足 g( n)- pg( n-1)- q=r ( g( n-1)- pg( n-2)- q) ，则得到：这个方程会发现没有实数解，于是我们只能使用复数了：p= iq= + ir = + i继续上面的递推式，则有g( n)- pg( n-1)- q=r n-2 ( g(2)- pg(1)- q) 。记 T= g(2)- p

12、g(1)- q，则：g( n)= pg( n-1)+ r n-2 T+q=p( pg( n-2)+ r n-3 T+q)+ r n-2 T+q=pn-1 g(1)+ pn-2 T+pn-3 rT +r n-2 T+q+pq+pn -2 q因此也就可以得到f 的递推式了：不难得到， t =， T= +i 。递推式中的c, p, q, t , T 都是常数，但除了c 以外都是复数，因此计算上会比较困难。在附录中附上C+的程序，附复数计算的模板和使用递推式计算类斐波那契数列的程序。三、递推式和矩阵如果对于每个线性递推式都要先计算它的通项公式才能够快速地得到某一项，那这个方法太过于复杂了。于是我们可以

13、使用矩阵来加速递推。比如斐波那契数列的递推式也可以写成：因此就有如下结果：其中矩阵的幂次方可以使用快速幂算法在O(logn) 的时间内解决，因此我们就可以在O(logn) 的时间内计算出斐波那契数列的第n 项（排除高精度的时间），且精度要比虚数和小数精确的多。附录利用通项公式计算类斐波那契数列的代码：#include<>#include<>#include<algorithm>#include<>#include<vector>#include<>#include<queue>#include<set&g

14、t;#include<functional>#include<>usingnamespace std;constdouble EPS = 1E-15;structComplexdouble a, b;4lf+%.14lfin", a, b); ;Complex csqrt(constComplex& c )Complex r =Complex(1, 1), t =while (r != t)t = r;r = r - (r * r -c) / 2 / r;Complex();returnr;Complex cpow( Complex c,inte)Co

15、mplex res =Complex(1, 0);for (;e;e >>= 1)if( e & 1) res = res *c =c *c;c;returnres;intmain()double c = 2, t = 0;t = c;c -= (c * c * c - c * c - c - 1) / (3 * c * c - 2 * c - 1);double a = c - 1, b = 1 / c;printf("%.14lfn", 1 + a + b);t = 1 + a + b;Complex r = (csqrt(Complex(a * a / c / c - 4 * b / c / c) - a / c) / 2;();Complex p =Complex(-a / c) - r, q =Complex(t / c / c / c) / (Complex(1) - r);(), ();Complex T =Complex(1 / c / c) -Complex(1 / c