斐波那契数

無限的斐波那契數列中的整數
(重定向自斐波那契数列

斐波那契数意大利语: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的斐波那契樹。平衡因子以綠色標記,節點的高度則為紅色。

最左一條路徑上的鍵值全為斐氏數。

程式參考编辑

JavaScript迭代

function fib(n) {
    var fib_n = function(curr, next, n) {
        if (n == 0) {
            return curr;
        }
        else {
            return fib_n(next, curr+next, n-1);
        }
    }
    return fib_n(0, 1, n);
}
alert(fib(40));

C语言通项公式

#include <stdio.h>
#include <math.h>

int main()
{
    int n;
    double constant_a = (1 + sqrt(5)) / 2;
    double constant_b = (1 - sqrt(5)) / 2;
    double constant_c = sqrt(5) / 5;
    double value_1 = 0;
    int value_2 = 0;
    scanf("%d", &n);
    if(n > 0)
    {
        for (int i = 0; i < n; i++)
        {
             value_1 = constant_c * (pow(constant_a, i) - pow(constant_b, i));
             value_2 = (int)value_1;
             printf("%d\n", value_2);
        }
        return 0;
    }
    else
    {
        return -1;
    }
}

c++二變數求某項版

#include <iostream>
using namespace std;
int main () {
	int x,y,n;
    x=1;y=0;
	cin >> n;
	for (int i=0;i<n;i=i+1) {
	    x=x+y;
		y=x-y;
	}
	cout << y;
	return 0;
}

c++通项公式版

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    unsigned long long n;
    double ca = (1 + sqrt(5)) / 2;
    double cb = (1 - sqrt(5)) / 2;
    double cc = sqrt(5) / 5;
    double v1 = 0;
    double v2 = 0;
    cout <<" ";
    cin>>n;
    if(n > 0)
    {
        for (unsigned long long i = 0; i < n; i++)
    {
            v1 = cc * (pow(ca, i) - pow(cb, i));
        v2 = (int)v1;
        cout <<v2<<endl;
    }
    return 0;
    }
    else
    {
        return -1;
    }
        cout <<'/b';
}

Python语言通项公式

# Fibonacci numbers module

def fib(n):    # write Fibonacci series up to n
    a, b = 0, 1
    while b < n:
        print(b, end=' ')
        a, b = b, a+b
    print()

def fib2(n):   # return Fibonacci series up to n
    result = []
    a, b = 0, 1
    while b < n:
        result.append(b)
        a, b = b, a+b
    return result
fibs = [0, 1]
numZS = int(input('How many Fibonacci numbers do you want? '))
for i in range(numZS-2):
    fibs.append(fibs[-2] + fibs[-1])
print fibs

Common Lisp

(defun fibs (x)
  (cond ((equal x 0) 1)
        ((equal x 1) 1)
        (t (+ (fibs (- x 1))
              (fibs (- x 2))))))

(defun fibs (x)
  (do ((n 0 (+ n 1))
       (i 1 j)
       (j 1 (+ i j)))
      ((equal n x) i)))

Go

遞迴版,時間複雜度為 O(2^n):

func fibonacci(n int) int {
	if n < 2 {
		return n
	}

	return fibonacci(n-2) + fibonacci(n-1)
}

通用版,時間複雜度為 O(n):

func fibonacci(n int) int {
	a, b := n%2, 1

	for i := 0; i < n/2; i++ {
		a += b
		b += a
	}

	return a
}

Java语言递归版:

public int fibonacci(int n){
    if(n<2){
     return n;
    }else {
      return fibonacci(n-1)+fibonacci(n-2);
    }
}

Java语言快捷版:

public int fibonacci(int n){
    if(n<2){
     return n;
    }else {
      int[] ans = new int[n];
          ans[0] = 1;
          ans[1] = 2;
          for(int i=2;i<n;i++) {
              ans[i]=ans[i-1]+ans[i-2];
          }
          return ans[n-1];
    }
}

C语言陣列版:

#include <stdio.h>
#include <stdlib.h> 
int main()
{   
     int n,s,L;
     printf("輸入長度");
     scanf("%d",&L);
     while(L<0)
     {
     	printf("錯誤"); 
     	return 0;
	 }
     int a[L]; 
     int x=1,y=2;
     a[0]=x;
     a[1]=x;
     a[2]=y;
	 for(n=3;n<L;n++)
	 {  
		 a[n]=a[n-1]+a[n-2];  	
	 }
       for(n=0;n<L;n++)
     {
         printf("%d ",a[n]);
     }
     system("pause");
     return 0;
}

Python Lambda 遞迴版:

fib = lambda n: n if n<2 else fib(n-1) + fib(n-2)

延伸閱讀编辑

  • 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. 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) 
  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 
  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. 
  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. MR 0995557. 
  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. MR 2988067. 
  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. ^ 利用指數律 、性質 ,以及「若 是有理數, 是無理數,且滿足 ,則 」證明。

參見编辑

外部連結编辑