斐波那契数

無限的斐波那契數列中的整數

斐波那契数意大利语:Successione di Fibonacci),又译为菲波拿契数菲波那西数斐氏数黄金分割数、斐波那契数列。所形成的数列称为斐波那契数列意大利语:Successione di Fibonacci),又译为菲波拿契数列菲波那西数列斐氏数列黄金分割数列、斐波那契数列。这个数列是由意大利数学家斐波那契在他的《算盘书》中提出。

以斐波那契数为边的正方形拼成的近似的黄金矩形(1:1.618)

数学上,斐波那契数是以递归的方法来定义:

用白话文来说,就是斐波那契数列由0和1开始,之后的斐波那契数就是由之前的两数相加而得出。首几个斐波那契数是:

1123581321345589144233377610、 987……(OEIS数列A000045

特别指出0 不是第一项,而是第零项()。

起源

公元1150年印度数学家Gopala金月在研究箱子包装对象长宽刚好为1和2的可行方法数目时,首先描述这个数列。在西方,最先研究这个数列的人是比萨的列奥那多(意大利人斐波那契Leonardo Fibonacci, 1175-1250),他描述兔子生长的数目时用上了这数列:

 
兔子对的数量就是斐波那契数列
  • 第一个月初有一对刚诞生的兔子
  • 第二个月之后(第三个月初)牠们可以生育
  • 每月每对可生育的兔子会诞生下一对新兔子
  • 兔子永不死去

假设在 月有兔子总共 对, 月总共有 对。在 月必定总共有 对:因为在 月的时候,前一月( 月)的 对兔子可以存留至第 月(在当月属于新诞生的兔子尚不能生育)。而新生育出的兔子对数等于所有在 月就已存在的 

 
斐波纳契数是杨辉三角的每一条红色对角线上数字的和。

斐波纳契数也是杨辉三角形(即帕斯卡三角形)的每一条红色对角线上数字的和。

表达式

为求得斐波那契数列的一般表达式,可以借助线性代数的方法。高中的初等数学知识也能求出。

初等代数解法

已知:

  •  
  •  
  •  (n≥3)

首先构建等比数列

 
化简得
 
比较系数可得:
 
不妨设 
解得:

 
又因为有 , 即 为等比数列。

求出数列 

由以上可得:
 

变形得:  。 令 

求数列 进而得到 

 
 ,解得 。 故数列 为等比数列
 。而 , 故有 
又有  
可得 

得出 表达式

 

用数学归纳法证明表达式

证明 ,其中 黄金比例  为任意整数
  •  为非负整数
 时, ,成立
 时, ,成立
设当  时皆成立,即  
 
 
亦成立
  •  为非正整数
 时,成立
 时, ,成立
设当  时皆成立,即  
 
 
亦成立

因此,根据数学归纳法原理,此表达式对于任意整数 皆成立

线性代数解法

 

 

构建一个矩阵方程

 为第 个月有生育能力的兔子数量, 为这一月份的兔子数量。

 

上式表达了两个月之间,兔子数目之间的关系。而要求的是, 的表达式。

求矩阵的特征值 

根据特征值的计算公式,我们需要算出来   所对应的解。

展开行列式有: 

故当行列式的值为 0,解得   

将两个特征值代入

 


求特征向量 

 = 

 = 

分解首向量

第一个月的情况是兔子一对,新生0对。

 

将它分解为用特征向量表示。

  (4)

数学归纳法证明

 = 

可得到

  (5)

化简矩阵方程

将(4) 代入 (5)

 

根据3

 

求A的表达式

现在在6的基础上,可以很快求出 的表达式,将两个特征值代入6中

 
 
 (7)

(7)即为 的表达式

数论解法

实际上,如果将斐波那契数列的通项公式写成 ,即可利用解二阶线性齐次递推关系式的方法,写出其特征多项式 (该式和表达斐波那契数列的矩阵的特征多项式一致),然后解出 =  = ,即有 ,其中 为常数。我们知道 ,因此 ,解得 

组合数解法

 [1]

 

黄金比例恒等式解法

 黄金比例 ,则有恒等式  ,其中 为任意整数[注 1],则

 

因此得到 的一般式:

 

此一般式对任意整数 成立

近似值

 为足够大的正整数时,则

 
 

用计算机求解

可通过编程观察斐波那契数列。分为两类问题,一种已知数列中的某一项,求序数。第二种是已知序数,求该项的值。

可通过递归递推的算法解决此两个问题。 事实上当 相当巨大的时候,O(n)的递推/递归非常慢……这时候要用到矩阵快速幂这一技巧,可以使递归加速到O(logn)。

和黄金分割的关系

开普勒发现数列前、后两项之比 ,也组成了一个数列,会趋近黄金分割

 

斐波那契数亦可以用连分数来表示:

 

 

而黄金分割数亦可以用无限连分数表示:

 

而黄金分割数也可以用无限多重根号表示:

 

和自然的关系

 
春黄菊头状花序上,小花呈螺旋状排列,从不同方向可以数出21(深蓝)和13(浅蓝)条旋臂,为相邻的斐氏数。类似的螺旋状排列见于多种植物。

斐氏数列见于不同的生物学现象[2],如树的分枝、叶在枝条上的排列英语Phyllotaxis、菠萝聚花果上小单果的排列、[3]雅枝竹的花蕾、正在舒展的蕨叶、松球的鳞的排列[4]、蜜蜂的家族树[5][6]开普勒曾指出斐氏数列存在于自然界,并以此解释某些花的五边形形态(与黄金分割率相关)。[7]法国菊的“瓣”(舌状花)数通常为斐氏数。[8]1830年,K. F. Schimper和A. Braun发现植物的旋生叶序中,连续两块叶之间转过的角度与周角之比,约成整数比时,常出现斐氏数[9],如  [10]

恒等式

资料来源:[11]

证明以下的恒等式有很多方法。以下会用组合论述来证明。

  •  可以表示用多个1和多个2相加令其和等于 的方法的数目。

不失一般性,我们假设  是计算了将1和2加到n的方法的数目。若第一个被加数是1,有 种方法来完成对 的计算;若第一个被加数是2,有 来完成对 的计算。因此,共有 种方法来计算n的值。

  •  

计算用多个1和多个2相加令其和等于 的方法的数目,同时至少一个加数是2的情况。

如前所述,当 ,有 种这样的方法。因为当中只有一种方法不用使用2,就即  ( 项),于是我们从 减去1。

  1. 若第1个被加数是2,有 种方法来计算加至 的方法的数目;
  2. 若第2个被加数是2、第1个被加数是1,有 种方法来计算加至 的方法的数目。
  3. 重复以上动作。
  4. 若第 个被加数为2,它之前的被加数均为1,就有 种方法来计算加至0的数目。

若该数式包含2为被加数,2的首次出现位置必然在第1和 的被加数之间。2在不同位置的情况都考虑到后,得出 为要求的数目。

  •  
  •  
  •  
  •  
  •  ,其中  的序数皆不限于正整数。[注 2]
    • 特别地,当 时, 
      • 更特别地,当  时,对于数列连续三项,有 
    • 另一方面,当 时,对于数列连续四项,有 [注 3]
  •   ,其中 黄金比例  为任意整数[注 1]
借由上述公式,又可推得以下恒等式[注 4]
    •  [11]
    •  [11]

      特别地,当 时, 

数论性质

公约数和整除关系

  •  整除 ,当且仅当 整除 ,其中 
  •  
  • 任意连续三个菲波那契数两两互素,亦即,对于每一个 
 

斐波那契素数

在斐波那契数列中,有素数[12] 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……

截至2015年,已知最大的斐波那契素数是第104911个斐波那契数,一共有21925个十进制位。不过,人们仍不知道是不是有无限个斐波那契素数。[13]

§ 公约数和整除关系所述, 总能被 整除,故除 之外,任何斐氏素数的下标必同为素数。由于存在任意长英语Arbitrarily large的一列连续合数,斐氏数列中亦能找到连续任意多项全为合数。

大于 的斐氏数,必不等于素数加一或减一。[14]

与其他数列的交集

斐波那契数列中,只有3个平方数01144[15][16]2001年,派特·奥蒂洛匈牙利语Pethő Attila证明只有有限多个斐氏数是完全幂。[17]2006年,Y. Bugeaud、M. Mignotte、S. Siksek三人证明此种幂仅得0、1、8、144。[18]

1、3、21、55为仅有的斐氏三角形数Vern Hoggatt英语Verner Emil Hoggatt Jr.曾猜想此结论,后来由罗明证明。[19]

斐波那契数不能为完全数[20]推而广之,除1之外,其他斐氏数皆非多重完全数[21],任两个斐氏数之比亦不能是完全数[22]

n的周期性

斐波那契数列各项模 的余数构成周期数列英语periodic sequence,其最小正周期称为皮萨诺周期[23],至多为 [24]。皮萨诺周期对不同 值的通项公式仍是未解问题,其中一步需要求出某个整数(同余意义下)或二次有限域元素的乘法阶数英语multiplicative order。不过,对固定的 ,求解模 的皮萨诺周期是周期检测英语cycle detection问题的特例。

推广

斐波那西数列是斐波那西n步数列步数为2的特殊情况,也和卢卡斯数列有关。

和卢卡斯数列的关系

 

反费波那西数列

反费波那西数列的递归公式如下:

 

如果它以1,-1开始,之后的数是:1,-1,2,-3,5,-8, ...

即是 

亦可写成 ,其中 是非负整数。

反费波那西数列两项之间的比会趋近 

证明关系式

证明 ,其中 是非负整数

 表示黄金分割数 ,则有 
 ,因此
 

巴都万数列

费波那西数列可以用一个接一个的正方形来表现,巴都万数列则是用一个接一个的等边三角形来表现,它有 的关系。

佩尔数列

佩尔数列的递归公式为 ,前几项为0,1,2,5,12,29,70,169,408,...

应用

1970年,尤里·马季亚谢维奇指出了偶角标的斐波那契函数

 

正是满足Julia Robison假设的丢番图函数,因而证明了希尔伯特第十问题是不可解的。

电脑科学

 
高为6的斐波那契树。平衡因子以绿色标记,节点的高度则为红色。

最左一条路径上的键值全为斐氏数。

延伸阅读

  • KNUTH, D. E. 1997. The Art of Computer ProgrammingArt of Computer Programming, Volume 1: Fundamental Algorithms, Third Edition. Addison-Wesley. Chapter 1.2.8.
  • Arakelian, Hrant (2014). Mathematics and History of the Golden Section. Logos, 404 p. ISBN 978-5-98704-663-0, (rus.)
  • 克里福德A皮科夫.数学之恋.湖南科技出版社.

参考文献

  1. ^ 斐波那契数列与组合数的一个关系及推广. [2014-01-04]. (原始内容存档于2019-05-02). 
  2. ^ Douady, S; Couder, Y. Phyllotaxis as a Dynamical Self Organizing Process (PDF). Journal of Theoretical Biology. 1996, 178 (3): 255–74. ISSN 0022-5193. doi:10.1006/jtbi.1996.0026. (原始内容 (PDF)存档于2006-05-26). 
  3. ^ Jones, Judy; Wilson, William. Science. An Incomplete Education. Ballantine Books. 2006: 544. ISBN 978-0-7394-7582-9. 
  4. ^ Brousseau, A. Fibonacci Statistics in Conifers. Fibonacci Quarterly英语Fibonacci Quarterly. 1969, (7): 525–32. 
  5. ^ Marks for the da Vinci Code: B–, Maths (Computer Science For Fun: CS4FN), [2022-10-30], (原始内容存档于2009-05-31) 
  6. ^ Scott, T.C.; Marketos, P., On the Origin of the Fibonacci Sequence (PDF), MacTutor History of Mathematics archive, University of St Andrews, 2014-03 [2022-10-30], (原始内容存档 (PDF)于2019-09-18) 
  7. ^ Livio 2003,第110页.
  8. ^ Livio 2003,第112–13页.
  9. ^ Varenne, Franck. Formaliser le vivant - Lois, Théories, Modèles. Hermann. 2010-11-16: 28 [2022-10-30]. ISBN 9782705678128. (原始内容存档于2022-10-30). 
  10. ^ The Secret of the Fibonacci Sequence in Trees. 美国自然史博物馆. 2011 [2019-02-04]. (原始内容存档于2013-05-04). 
  11. ^ 11.0 11.1 11.2 李晨滔、冯劲敏. 費氏數列的性質整理 (PDF). 桃园县立大园国际高中. [2018-01-28]. (原始内容存档 (PDF)于2019-06-25). 
  12. ^ Sloane, N.J.A. (编). Sequence A005478. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. 
  13. ^ Weisstein, Eric W. (编). Fibonacci Prime. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英语). 
  14. ^ Honsberger, Ross. Mathematical Gems III. AMS Dolciani Mathematical Expositions. 1985, (9): 133. ISBN 978-0-88385-318-4. 
  15. ^ JOHN H. E. COHN. Square Fibonacci Numbers, Etc.. Bedford College, University of London, London, N.W.1. [2019-05-12]. (原始内容存档于2012-06-30). Theorem 3. If Fn = x2, then n = 0, ±1, 2 or 12. 
  16. ^ Cohn, J. H. E., On square Fibonacci numbers, The Journal of the London Mathematical Society, 1964, 39: 537–540, MR 0163867, doi:10.1112/jlms/s1-39.1.537 
  17. ^ Pethő, Attila. Diophantine properties of linear recursive sequences II. Acta Mathematica Academiae Paedagogicae Nyíregyháziensis. 2001, 17: 81–96. MR 1887650. 
  18. ^ Bugeaud, Y; Mignotte, M; Siksek, S. Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. Math. 2006, 2 (163): 969–1018. Bibcode:2004math......3046B. MR 2215137. S2CID 10266596. arXiv:math/0403046 . doi:10.4007/annals.2006.163.969. 
  19. ^ Luo, Ming. On triangular Fibonacci numbers (PDF). Fibonacci Quart. 1989, 27 (2): 98–108 [2022-10-29]. MR 0995557. (原始内容存档 (PDF)于2022-10-29). 
  20. ^ Luca, Florian. Perfect Fibonacci and Lucas numbers. Rendiconti del Circolo Matematico di Palermo. 2000, 49 (2): 313–18. ISSN 1973-4409. MR 1765401. S2CID 121789033. doi:10.1007/BF02904236. 
  21. ^ Broughan, Kevin A.; González, Marcos J.; Lewis, Ryan H.; Luca, Florian; Mejía Huguet, V. Janitzio; Togbé, Alain. There are no multiply-perfect Fibonacci numbers. Integers. 2011, 11a: A7 [2022-10-29]. MR 2988067. (原始内容存档于2022-01-23). 
  22. ^ Luca, Florian; Mejía Huguet, V. Janitzio. On Perfect numbers which are ratios of two Fibonacci numbers. Annales Mathematicae at Informaticae. 2010, 37: 107–24. ISSN 1787-6117. MR 2753031. 
  23. ^ Sloane, N.J.A. (编). Sequence A001175. The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. 
  24. ^ Freyd, Peter; Brown, Kevin S. Problems and Solutions: Solutions: E3410. The American Mathematical Monthly. 1993, 99 (3): 278–79. JSTOR 2325076. doi:10.2307/2325076. 
  25. ^ Knuth, Donald E. The Art of Computer Programming. 1: Fundamental Algorithms 3rd. Addison–Wesley. 1997: 343. ISBN 978-0-201-89683-1. 
  26. ^ Adelson-Velsky, Georgy; Landis, Evgenii. An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences英语Proceedings of the USSR Academy of Sciences. 1962, 146: 263–266 (俄语).  Myron J. Ricci 的英文翻译页面存档备份,存于互联网档案馆)载于 Soviet Mathematics - Doklady, 3:1259–1263, 1962.

注释

  1. ^ 1.0 1.1 这可以透过   此三个等式,以及斐波那契数列的递归定义,以数学归纳法证明。
  2. ^ 例如当 时, 
  3. ^ 亦即“头尾两项乘积”与“中间两项乘积”恒相差1
  4. ^ 利用指数律 、性质 ,以及“若 是有理数, 是无理数,且满足 ,则 ”证明。

参见

外部链接