斐波那契数列.docx

《斐波那契数列.docx》由会员分享，可在线阅读，更多相关《斐波那契数列.docx（11页珍藏版）》请在第壹文秘上搜索。

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

2、数列的性质,必然要先知道它的通项公式才能更简单的推导出一些定理.那么下面我们就通过初等代数的待定系数法计算出通项公式.令常数P,q满足FfI-PFaFq(Fz-pFQ.那么可得：Fn-PF*q(FM-PFZ)二q2(FipFz)=*=Cn-2(Fz-pF)又Fn-PFriLki-PFn-)F-pF_qF-PqFfnni*111n2FF-pF-QFpqF=0n-1n-2n-1n-1n-2(I-P-q)F+(1+pq)Fg=O,p+q=1,pq=-1是其中的一种方程组1. F-pF-q11-2(F-pF)=q-2(1-p)=q-11-21F=q11-+pF=q11-+p(qn-2+p(qn-3+)

3、=Cn-1+pqn-2+p2q11-3+pn-1不难看出,上式是一个以p/q为公比的等比数列.将它用求和公式求和可以得到:而上面出现了方程组p+q=1,pq=T,可以得到P1-P=T,P-P-1=0,这样就得到了一个标准的一元二次方程,配方得PLP+=,2=.P=J+-随意取出一组解即可:V-H1I-书P=q=丁这就是著名的斐波那契数列通项公式.有了它,斐波那契数列的一些性质也不难得出了.比方斐波那契数列相邻两项的比值趋向于黄金分割比,即:1I3七161839087,?rugn根据斐波那契数列通项公式,可以得到由于n是趋向于正无限的,因此我们可以知道:那么我们就可以把分子和分母的第二项同时省略

4、掉,即I21这就是斐波那契数列的魅力之-它和黄金分割比有密切的关系下面将给出斐波那契数列的几个性质及其证实.1F1+F2+F3+.+Fi=FW证实：原式二月子尸？干尸丑口七/二匕I2)fiVs+-%证实：原式二号午二+丁4+.+1摩避3) F12+F22+.+Fz=FF证实：利用数学归纳法,显然n=1时满足,下面证实假设n=k时满足,n=k+1时也满足.F2+F2+.+F2=FF,F2+F2+.+F2=FF+F2=(F+F)F=FF,因此n+1后仍12然满足.上述公式成立.4) FF2+F2F3+.+F,F”(Fw-FeFiI)/2证实：数学归纳法,n=1时满足+口IX满足,那么Tzw2F;.

5、产；Jn2=(Fm产/2FeFft+2=(F=(篇*%+口)-凡工T2二J2M02,因此上式成立.5) Fn2=FlbFm+(T)n证实：数学归纳法,2时满足.前面的n都满足,那么m，3:丁产匚，)二匚二二).明因此上式成立.6)F/+FG(nm1)1 +1证实：利用通项公式,设a=J,B=1-a=.F-正门+F.F1(ci1一二一0n)I(Ln,一0喷口+1-Jr*J-55小ilBL一七一+二-拼,-晨三匚二二a仁1一仁+日仁+B)注意到1/a+a=sqrt(5)=B+B,1/a+B=0=1B+a,上式就变成了卜+0.)=F.这就是上述公式的证实.斐波那契数列与自然斐波那契数列中的斐波那契数

6、会经常出现在我们的眼前一比方松果、凤梨、树叶的排歹Ik某些花朵的花瓣数(典型的有向日葵花瓣)，蜂巢,蜻蜓翅膀,超越数e(可以推出更多)，黄金矩形、黄金分割等角螺线,十二平均律等.斐波那契数还可以在植物的叶、枝、茎等排列中发现.例如,在树木的枝干上选一片叶子,记其为数Of然后依序点数叶子(假定没有折损)，直到到达与那些叶子正对的位置,那么其间的叶子数多半是斐波那契数.叶子从一个位置到达下一个正对的位置称为一个循回.叶子在一个循回中旋转的圈数也是斐波那契数.在一个循回中叶子数与叶子旋转圈数的比称为叶序(源自希腊词,意即叶子的排列)比.多数的叶序比呈现为斐波那契数的比.关于递推式的拓展研究错位排列问

7、题有n个数,求有多少种排列使这n个数都不在原来的位置上.比方n=2时,有一种排列.设f(n)表示n个数的错位排列数量,分两种情况讨论：1 .第n个数在第P(P+n)个数的位置上,第P个数在第n个数的位置上,那么此时共有f(n-2)种选择.由于P有ST)种值,那么总共有(n-1)f(n-2)种排列方法；2 .否那么,共有(nT)f(nT)种排列方法.综上所述,f(n)=(n-1)(f(n-1)+f(n-2),f(1)=0,f(2)=1.那这个数列的通项公式是什么呢直接对这个数列不好进行操作,可以转化一下设错位排列的概率函数为g(n),其中g二Og二.在f(n)的递推式两边同时除以n!即可得到.斗

8、川211，.昌川两边同时乘n得到ng(n)=(n-1)g(n-1)+g(n-2)n(g(n)-g(n-1)=g(n-2)-g(n-1)虱n)-2-1)1.即可得到或O二X-=X-q!Mai2I=O注意到e-的泰勒展开式跟它好似有点像,是1.(-?二21-+-IC-因此有如下的等式：Iitg()-e-1C367BAnT+fl同时,我们也可以得到了函数f的通项公式为：31-1)1f(n)三114.(11)NIll乙一I=:,这就是一些关于错位排序的性质.类斐波那契数列的研究我们知道斐波那契数列递推式为f(n)=f(n-1)+f(n-2),那么假设有更多项呢假设千(n)=f(n-1)+f(n-2)+

9、f(n-3),其中f(1)=f(2)=f(3)=1.我们暂时称这个数列为类斐波那契数列,那么它的通项公式又如何呢令a,b,c满足f(n)+af(n-1)+bf(n-2)=c(f(11-1)+af(n-2)+bf(n-3)那么得到c-a=1,ac-b=1,bc=1,消元得C3-C2-cT=0,利用牛顿迭代可以计算出C=.那么a=b=.所以f(n)+af(n-1)+bf(n-2)=C11-3(1+a+b),记t=1+a+b,两边同时除以Cn构造更多的常数项：t(u;af(n-Uhr(n-2)_：为了方便,我们记6m二那么：UbL虱U)+(ri-1)+gCn-2)*GG令p.q,r满足g(n)-pg

10、(nT)-q=r(g(n-1)-pg(n-2)-q),那么得到:hLPls.p-(1-r)q-J写CC这个方程会发现没有实数解,于是我们只能使用复数了：继续上面的递推式,那么有g(n)-pg(n-1)-q二rn(g-Pg(I)-q).记T=g(2)-pg(1)-q,那么：g(n)=pg(n-1)+r11-2T+q=p(pg(n-2)+r11-3T+q)+r11-2T+q=p11-g(1)+p11-2T+p11-3rT+rn-2T+q+pq+p11-2qPrPTqpq二+因此也就可以得到f的递藉式了：不难得到,t=,T=+i.递推式中的C,P,q,t,T都是常数,但除了c以外都是复数,因此计算上

11、会比拟困难.在附录中附上C+的程序,附复数计算的模板和使用递推式计算类斐波那契数列的程序.三、递推式和矩阵如果对于每个线性递推式都要先计算它的通项公式才能够快速地得到某一项,那这个方法太过于复杂了.于是我们可以使用矩阵来加速递推.比方斐波那契数列的递推式也可以写成:1-D1.卜因此就有如下结果：f:n:I(2).(0)其中矩阵的幕次方可以使用快速器算法在O(Iogn)的时间内解决,因此我们就可以在O(Iogn)的时间内计算出斐波那契数列的第n项(排除高精度的时间)，且精度要比虚数和小数精确的多.附录利用通项公式计算类斐波那契数列的代码：# includeO# includeO# incIude

12、(algorithm)# includeO# incIude(vector)# includeO# include# include# include(functional)# incIudeOusingnamespacestd;constdoubIeEPS=1E15;structCompIexdoubIea,b;4lf+%.14lfin,a,b);CompIexcsqrt(constCompIex&c)CompIexr=Complex。，1),t=Complex.；while(r!=t)r；r-(r*r-c)/2/r;returnr;Complexcpow(CompIexc,inte)Com

13、pIexres=Complex(1,O);for(;e;e=1)if(e&1)res=res*c;returnres;intmainO(doubIec=2,t=0;while(fabs(c-t)EPS)=c;-=(c*c*c-c*c-c-1)/(3*c*c-2*c-1);doubIea=c-1,b=1/c;printf(%.14lfn,1+a+b)：b;Complex(esqrt(Complex(a*a/c/c-4*bcc)-a/c)/2;0；Comp lexCompIex(a/c)-r,q=CompIex(t/c/c/c)/(CompIex(1)-r);O.O;CompIexT=CompIex(1/c/c)-CompIex(1/c)*p-q;O;intn=7;SCanf(%c,&n);CompIexres=cpow(CompIex(c),n)*(cpow(p,n-1)/CompIex(c)+T*(cpow(rln-1)-cpow(p,n-1)/(r-p)+(q*cpow(p,n-1)-q)/(p-Complex(1);O;system(pause);returnO;