斐波那契数列的故事

《斐波那契数列的故事》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、斐波那契数列的故事·评论：0·浏览：77·RSS：0文章类型：发表于：2011/10/1318:49:25費波那西數列（FibonacciSequence），又译費波拿契數、斐波那契數列、費氏數列、黃金分割數列。在数学上，费波那西数列是以递归的方法来定义：·F0 =0·F1 =1·Fn = Fn -1 + Fn -2用文字来说，就是费波那西数列由0和1开始，之后的费波那西系数就由之前的两数相加。首几个费波那西系数是（OEISA000045）：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,

2、987,1597,2584,4181,6765,10946，………………特别指出：0不是第一项，而是第零项。斐波那契数列的源起：根据高德纳（DonaldErvinKnuth）的《计算机程序设计艺术》（TheArtofComputerProgramming），1150年印度数学家Gopala和金月在研究箱子包装物件长阔刚好为1和2的可行方法数目时，首先描述这个数列。在西方，最先研究这个数列的人是比萨的列奥那多（又名费波那西），他描述兔子生长的数目时用上了这数列。·第一个月有一对刚诞生的兔子·第二个月之后它们可以生育·每月每对可生育的兔子会诞生下一对新兔子·兔子永

3、不死去假设在n月有新生及可生育的兔子总共a对，n+1月就总共有b对。在n+2月必定总共有a+b对：因为在n+2月的时候，所有在n月就已存在的a对兔子皆已可以生育并诞下a对后代；同时在前一月(n+1月)之b对兔子中，在当月属于新诞生的兔子尚不能生育。斐波那契数列的表达式：为求得费波那西数列的一般表达式，可以借助线性代数的方法。高中的初等数学知识也能求出。初等代数解法已知·a1 =1·a2 =1·an = an −1 + an −2首先构建等比数列设an +αan −1 =β(an −1 +αan −2)化简得an =(β−α)an −1 +αβan −2比较系数

4、可得:不妨设β>0,α>0解得：所以有an +αan −1 =β(an −1 +αan −2)，即为等比数列。求出数列{an +αan −1}由以上可得：变形得： 。令求数列{bn}进而得到{an}设，解得。故数列 为等比数列即 。而 ，故有 又有 和 可得 得出 an 表达式线性代数解法构建一个矩阵方程设Jn为第n个月有生育能力的兔子数量，An为这一月份的兔子数量。上式表达了两个月之间，兔子数目之间的关系。而要求的是，An+1的表达式。求矩阵的特征值：λ行列式：-λ*(1-λ)-1*1=λ2-λ-1当行列式的值为0，解得λ1= 或 λ2=特征矢量将两个特征值

5、代入求特征矢量 得==分解首矢量第一个月的情况是兔子一对，新生0对。将它分解为用特征矢量表示。 （4）用数学归纳法证明从=可得 （5）化简矩阵方程将（4）代入（5）根据3求A的表达式现在在6的基础上，可以很快求出An+1 的表达式，将两个特征值代入6中 (7)(7)即为An+1 的表达式近似值用计算机求解可通过编程观察斐波那契数列。分为两类问题，一种已知数列中的某一项，求序数。第二种是已知序数，求该项的值。可通过递归递推的算法解决此两个问题。事实上当n相当巨大的时候，O(n)的递推/递归非常慢……这时候要用到矩阵加速这一技巧。和黄金分割的关系开普勒发现两个斐波

6、那契数的比会趋近黄金分割：斐波那契数亦可以用连分数来表示：而黄金分割数亦可以用无限连分数表示：和自然的关系许多的生物构成都和斐波那契数列有正相关。例如人体从肚脐至头顶之距离和从肚脐至脚底之距趋近于 ,向日葵的种子螺旋排列99%是Fn。恒等式证明以下的恒等式有很多方法。以下会用组合论述来证明。Fn可以表示成用多个1和多个2相加令其和等于

7、法来计算n的值。·F1 + F2 + F3 +...+ Fn = Fn +2 -1计算用多个1和多个2相加令其和等于n+1的方法的数目，同时最后一个加数是2的情况。如前所述，当n0，有Fn +2种这样的方法。因为当中只有一种方法不用使用2，就即 1+1+...+1　（n+1项），于是我们从Fn +2减去1。1.若第1个被加数是2，有Fn个方法来计算加至n-1的方法的数目；2.若第2个被加数是2、第1个被加数是1，有Fn -1个方法来计算加至n −2的方法的数目。3.重复以上动作。4.若第n +1个被加数为2，它之前的被加数均为1，就有F(0)个方法来计算加至

8、0的数目。若该数式包含2为被加数，2的