斐波那契数列

  1. 云栖社区>
  2. 博客>
  3. 正文

斐波那契数列

技术小甜 2017-11-16 17:50:00 浏览727
展开阅读全文

斐波那契数列的发明者,是意大利数学家列昂纳多·斐波那契(Leonardo Fibonacci,生于公元1170年,卒于1240年,籍贯大概是比萨)。他被人称作“比萨的列昂纳多”。1202年,他撰写了《珠算原理》(Liber Abacci)一书。他是第一个研究了印度阿拉伯数学理论的欧洲人。他的父亲被比萨的一家商业团体聘任为外交领事,派驻地点相当于今日的阿尔及利亚地区,列昂纳多因此得以在一个阿拉伯老师的指导下研究数学。他还曾在埃及叙利亚希腊西西里普罗旺斯研究数学

  

  

斐波那契数列通项公式

斐波那契数列指的是这样一个数列:1、1、2、3、5、8、13、21、……

  这个数列从第三项开始,每一项都等于前两项之和。

  它的通项公式为:(见图)(又叫“比内公式”,是用无理数表示有理数的一个范例。)

  有趣的是:这样一个完全是自然数的数列,通项公式居然是用无理数来表达的。而且当n无穷大时an-1/an越来越逼近黄金分割

  0.618

  证明:

  a[n+2]=a[n+1]+a[n]

  两边同时除以a[n+1]得到:

  a[n+2]/a[n+1]=1+a[n]/a[n+1]

  若a[n+1]/a[n]的极限存在,设其极限为x,

  则lim[n->∞](a[n+2]/a[n+1])=lim[n->∞](a[n+1]/a[n])=x

  所以x=1+1/x

  即x²=x+1

  所以极限是黄金分割比 .

奇妙的属性

  随着数列项数的增加,前一项与后一项之比越来越逼近黄金分割的数值0.6180339887……

  从第二项开始,每个奇数项的平方都比前后两项之积多1,每个偶数项的平方都比前后两项之积少1。(注:奇数项和偶数项是指项数的奇偶,而并不是指数列的数字本身的奇偶,比如第四项3是奇数,但它是偶数项,第五项5是奇数,它是奇数项,如果认为数字3和5都是奇数项,那就误解题意,怎么都说不通)

   如果你看到有这样一个题目:

  某人把一个8*8的方格切成四块,拼成一个5*13的长方形,故

  作惊讶地问你:为什么64=65?其实就是利用了斐波那契数列的这个性质:5、8、13正是数列中相邻的三项,事实上前后两块的面积

  确实差1,只不过后面那个图中有一条细长的狭缝,一般人不容易注意到。

  斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数子集个数。

  斐波那契数列(f(n),f(0)=0,f(1)=1,f(2)=1,f(3)=2……)的其他性质:

  1.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1

  2.f(1)+f(3)+f(5)+…+f(2n-1)=f(2n)

  3.f(2)+f(4)+f(6)+…+f(2n) =f(2n+1)-1

  4.[f(0)]^2+[f(1)]^2+…+[f(n)]^2=f(n)·f(n+1)

  5.f(0)-f(1)+f(2)-…+(-1)^n·f(n)=(-1)^n·[f(n+1)-f(n)]+1

  6.f(m+n-1)=f(m-1)·f(n-1)+f(m)·f(n)

  利用这一点,可以用程序编出时间复杂度仅为O(log n)的程序。

  怎样实现呢?伪代码描述一下?

  7.[f(n)]^2=(-1)^(n-1)+f(n-1)·f(n+1)

  8.f(2n-1)=[f(n)]^2-[f(n-2)]^2

  9.3f(n)=f(n+2)+f(n-2)

  10.f(2n-2m-2)[f(2n)+f(2n+2)]=f(2m+2)+f(4n-2m) [ n〉m≥-1,且n≥1]

11.f(2n+1)=[f(n)]^2+[f(n+1)]^2

在杨辉三角中隐藏着斐波那契数列

  

将杨辉三角依次下降,成如图所示排列,将同一行的数加起来,即得一数列1、1、2、3、5、8、……

  公式表示如下:

  f(1)=C(0,0)=1

  f(2)=C(1,0)=1

  f(3)=C(2,0)+C(1,1)=1+1=2

  f(4)=C(3,0)+C(2,1)=1+2=3

  f(5)=C(4,0)+C(3,1)+C(2,2)=1+3+1=5

  f(6)=C(5,0)+C(4,1)+C(3,2)=1+4+3=8

  F(7)=C(6,0)+C(5,1)+C(4,2)+C(3,3)=1+5+6+1=13

  ……

  F(n)=C(n-1,0)+C(n-2,1)+…+C(n-1-m,m) (m<=n-1-m)

斐波那契数列的整除性与素数生成性

  每3个数有且只有一个被2整除,

  每4个数有且只有一个被3整除,

  每5个数有且只有一个被5整除,

  每6个数有且只有一个被8整除,

  每7个数有且只有一个被13整除,

  每8个数有且只有一个被21整除,

  每9个数有且只有一个被34整除,

  .......

  我们看到第5、7、11、13、17、23位分别是素数:5,13,89,233,1597,28657(第19位不是)

  斐波那契数列的素数无限多吗?

斐波那契数列的个位数:一个60步的循环

  11235,83145,94370,77415,61785.38190,

  99875,27965,16730,33695,49325,72910…

斐波那契数与植物花瓣

  3………………………百合和蝴蝶花

  5………………………蓝花耧斗菜、金凤花、飞燕草、毛茛花

  8………………………翠雀花

  13………………………金盏

和玫瑰

  21………………………紫宛

  34、55、89……………雏菊

  斐波那契数还可以在植物的叶、枝、茎等排列中发现。例如,在树木的枝干上选一片叶子,记其为数0,然后依序点数叶子(假定没有折损),直到到达与那息叶子正对的位置,则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中叶子数与叶子旋转圈数的比称为叶序(源自希腊词,意即叶子的排列)比。多数的叶序比呈现为斐波那契数的比。

斐波那契—卢卡斯数列与广义斐波那契数列

斐波那契—卢卡斯数列

  卢卡斯数列1、3、4、7、11、18…,也具有斐波那契数列同样的性质。(我们可称之为斐波那契—卢卡斯递推:从第三项开始,每一项都等于前两项之和f(n) = f(n-1)+ f(n-2))。

  这两个数列还有一种特殊的联系(如下表所示),F(n)*L(n)=F(2n),及L(n)=F(n-1)+F(n+1)

  

n 1 2 3 4 5 6 7 8 9 10
斐波那契数列F(n) 1 1 2 3 5 8 13 21 34 55
卢卡斯数列L(n) 1 3 4 7 11 18 29 47 76 123
F(n)*L(n) 1 3 8 21 55 144 377 987 2584 6765

类似的数列还有无限多个,我们称之为斐波那契—卢卡斯数列。

  如1,4,5,9,14,23…,因为1,4开头,可记作F[1,4],斐波那契数列就是F[1,1],卢卡斯数列就是F[1,3],斐波那契—卢卡斯数列就是F[a,b]。

斐波那契—卢卡斯数列之间的广泛联系

  ①任意两个或两个以上斐波那契—卢卡斯数列之和或差仍然是斐波那契—卢卡斯数列。

  如:F[1,4]n+F[1,3]n=F[2,7]n,F[1,4]n-F[1,3]n=F[0,1]n=F[1,1](n-1),

  

n 1 2 3 4 5 6 7 8 9 10
F[1,4]n 1 4 5 9 14 23 37 60 97 157
F[1,3]n 1 3 4 7 11 18 29 47 76 123
F[1,4]n-F[1,3]n 0 1 1 2 3 5 8 13 21 34
F[1,4]n+F[1,3]n 2 7 9 16 25 41 66 107 173 280

②任何一个斐波那契—卢卡斯数列都可以由斐波那契数列的有限项之和获得,如

  

n 1 2 3 4 5 6 7 8 9 10
F[1,1](n) 1 1 2 3 5 8 13 21 34 55
F[1,1](n-1) 0 1 1 2 3 5 8 13 21 34
F[1,1](n-1) 0 1 1 2 3 5 8 13 21 34
F[1,3]n 1 3 4 7 11 18 29 47 76 123

黄金特征与孪生斐波那契—卢卡斯数列

  斐波那契—卢卡斯数列的另一个共同性质:中间项的平方数与前后两项之积的差的绝对值是一个恒值,

  斐波那契数列:|1*1-1*2|=|2*2-1*3|=|3*3-2*5|=|5*5-3*8|=|8*8-5*13|=…=1

  卢卡斯数列:|3*3-1*4|=|4*4-3*7|=…=5

  F[1,4]数列:|4*4-1*5|=11

  F[2,5]数列:|5*5-2*7|=11

  F[2,7]数列:|7*7-2*9|=31

  斐波那契数列这个值是1最小,也就是前后项之比接近黄金比例最快,我们称为黄金特征,黄金特征1的数列只有斐波那契数列,是独生数列。卢卡斯数列的黄金特征是5,也是独生数列。前两项互质的独生数列只有斐波那契数列和卢卡斯数列这两个数列。

  而F[1,4]与F[2,5]的黄金特征都是11,是孪生数列。F[2,7]也有孪生数列:F[3,8]。其他前两项互质的斐波那契—卢卡斯数列都是孪生数列,称为孪生斐波那契—卢卡斯数列。

广义斐波那契数列

  斐波那契数列的黄金特征1,还让我们联想到佩儿数列:1,2,5,12,29,…,也有|2*2-1*5|=|5*5-2*12|=…=1(该类数列的这种特征值称为勾股特征)。

  佩尔数列Pn的递推规则:P1=1,P2=2,Pn=P(n-2)+2P(n-1).

  据此类推到所有根据前两项导出第三项的通用规则:f(n) = f(n-1) * p + f(n-2) * q,称为广义斐波那契数列。

  当p=1,q=1时,我们得到斐波那契—卢卡斯数列。

  当p=1,q=2时,我们得到佩尔—勾股弦数(跟边长为整数的直角三角形有关的数列集合)。

  当p=-1,q=2时,我们得到等差数列。其中f1=1,f2=2时,我们得到自然数列1,2,3,4…。自然数列的特征就是每个数的平方与前后两数之积的差为1(等差数列的这种差值称为自然特征)。

  具有类似黄金特征、勾股特征、自然特征的广义斐波那契数列p=±1。

  当f1=1,f2=2,p=2,q=1时,我们得到等比数列1,2,4,8,16……

斐波那契数列与黄金比

  1÷1=1,2÷1=2,3÷2=1.5,5÷3=1.666...,8÷5=1.6,…………,89÷55=1.6181818…,…………233÷144=1.618055…75025÷46368=1.6180339889…。..

  越到后面,这些比值越接近黄金比

相关的数学问题

1.排列组合

  有一段楼梯有10级台阶,规定每一步只能跨一级或两级,要登上第10级台阶有几种不同的走法?

  这就是一个斐波那契数列:登上第一级台阶有一种登法;登上两级台阶,有两种登法;登上三级台阶,有三种登法;登上四级台阶,有五种登法……

  1,2,3,5,8,13……所以,登上十级,有89种走法。

2.数列中相邻两项的前项比后项的极限

  当n趋于无穷大时,F(n)/F(n+1)的极限是多少?

  这个可由它的通项公式直接得到,极限是(-1+√5)/2,这个就是黄金分割的数值,也是代表大自然的和谐的一个数字。

  3.求递推数列a(1)=1,a(n+1)=1+1/a(n)的通项公式

  由数学归纳法可以得到:a(n)=F(n+1)/F(n),将斐波那契数列的通项式代入,化简就得结果。

斐波那契数列别名

  斐波那契数列又因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”。

  一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔都不死,那么一年以后可以繁殖多少对兔子?

  我们不妨拿新出生的一对小兔子分析一下:

  第一个月小兔子没有繁殖能力,所以还是一对

  两个月后,生下一对小兔民数共有两对

  三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对

  ------

  依次类推可以列出下表:

  

经过月数 0 1 2 3 4 5 6 7 8 9 10 11 12
幼仔对数 0 0 1 1 2 3 5 8 13 21 34 55 89
成兔对数 0 1 1 2 3 5 8 13 21 34 55 89 144
总体对数 1 1 2 3 5 8 13 21 34 55 89 144 233

幼仔对数=前月成兔对数

  成兔对数=前月成兔对数+前月幼仔对数

  总体对数=本月成兔对数+本月幼仔对数

  可以看出幼仔对数、成兔对数、总体对数都构成了一个数列。这个数列有关十分明显的特点,那是:前面相邻两项之和,构成了后一项。

  这个数列是意大利中世纪数学家斐波那契在<算盘全书>中提出的,这个级数的通项公式,除了具有a(n+2)=an+a(n+1)的性质外,还可以证明通项公式为:an=(1/√5)*{[(1+√5)/2]^n-[(1-√5)/2]^n}(n=1,2,3.....)

斐波那契数列公式的推导

  斐波那契数列:1、1、2、3、5、8、13、21、……

  如果设F(n)为该数列的第n项(n∈N+)。那么这句话可以写成如下形式:

  F(0) = 0,F(1)=1,F(n)=F(n-1)+F(n-2) (n≥2),

  显然这是一个线性递推数列。

  通项公式的推导方法一:利用特征方程

  线性递推数列的特征方程为:

  X^2=X+1

  解得

  X1=(1+√5)/2,,X2=(1-√5)/2

  则F(n)=C1*X1^n + C2*X2^n

  ∵F(1)=F(2)=1

  ∴C1*X1 + C2*X2

  C1*X1^2 + C2*X2^2

  解得C1=1/√5,C2=-1/√5

  ∴F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}(√5表示根号5)

  通项公式的推导方法二:普通方法

  设常数r,s

  使得F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]

  则r+s=1, -rs=1

  n≥3时,有

  F(n)-r*F(n-1)=s*[F(n-1)-r*F(n-2)]

  F(n-1)-r*F(n-2)=s*[F(n-2)-r*F(n-3)]

  F(n-2)-r*F(n-3)=s*[F(n-3)-r*F(n-4)]

  ……

  F(3)-r*F(2)=s*[F(2)-r*F(1)]

  将以上n-2个式子相乘,得:

  F(n)-r*F(n-1)=[s^(n-2)]*[F(2)-r*F(1)]

  ∵s=1-r,F(1)=F(2)=1

  上式可化简得:

  F(n)=s^(n-1)+r*F(n-1)

  那么:

  F(n)=s^(n-1)+r*F(n-1)

  = s^(n-1) + r*s^(n-2) + r^2*F(n-2)

  = s^(n-1) + r*s^(n-2) + r^2*s^(n-3) + r^3*F(n-3)

  ……

  = s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)*F(1)

  = s^(n-1) + r*s^(n-2) + r^2*s^(n-3) +……+ r^(n-2)*s + r^(n-1)

  (这是一个以s^(n-1)为首项、以r^(n-1)为末项、r/s为公比的等比数列的各项的和)

  =[s^(n-1)-r^(n-1)*r/s]/(1-r/s)

  =(s^n - r^n)/(s-r)

  r+s=1, -rs=1的一解为 s=(1+√5)/2,r=(1-√5)/2

  则F(n)=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}

  迭代法

  已知a1=1,a2=1,an=a(n-1)+a(n-2)(n>=3),求数列{an}的通项公式

  解 :设an-αa(n-1)=β(a(n-1)-αa(n-2))

  得α+β=1

  αβ=-1

  构造方程x&sup2;-x-1=0,解得α=(1-√5)/2,β=(1+√5)/2或α=(1+√5)/2,β=(1-√5)/2

  所以

  an-(1-√5)/2*a(n-1)=(1+√5)/2*(a(n-1)-(1-√5)/2*a(n-2))=[(1+√5)/2]^(n-2)*(a2-(1-√5)/2*a1)`````````1

  an-(1+√5)/2*a(n-1)=(1-√5)/2*(a(n-1)-(1+√5)/2*a(n-2))=[(1-√5)/2]^(n-2)*(a2-(1+√5)/2*a1)`````````2

  由式1,式2,可得

  an=[(1+√5)/2]^(n-2)*(a2-(1-√5)/2*a1)``````````````3

  an=[(1-√5)/2]^(n-2)*(a2-(1+√5)/2*a1)``````````````4

  将式3*(1+√5)/2-式4*(1-√5)/2,化简得an=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}

  `````










本文转自NewPanderKing51CTO博客,原文链接:http://www.cnblogs.com/newpanderking/archive/2011/07/26/2117328.html ,如需转载请自行联系原作者

网友评论

登录后评论
0/500
评论
技术小甜
+ 关注