斐波那契数

-{zh-hant:費波那契數;zh-hans:斐波那契数}-（意大利语：Successione di Fibonacci），又譯為菲波拿契數、菲波那西數、斐氏數、黃金分割數。所形成的數列稱為-{zh-hant:費波那契數列;zh-hans:斐波那契数列}-（意大利语：Successione di Fibonacci），又譯為菲波拿契數列、菲波那西數列、斐氏數列、黃金分割數列。這個數列是由意大利數學家斐波那契在他的《算盤書》中提出。

在數學上，斐波那契數是以遞歸的方法來定義：

（）

用文字來說，就是斐波那契數列由0和1開始，之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是：
987……

特別指出：0不是第一項，而是第零項。

起源
公元1150年印度數學家Gopala和金月在研究箱子包裝物件長宽剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的李奧納多（義大利人斐波那契Leonardo Fibonacci, 1175－1250），他描述兔子生長的數目時用上了這數列：

第一個月初有一對剛誕生的兔子
第二個月之後（第三個月初）牠們可以生育
每月每對可生育的兔子會誕生下一對新兔子
兔子永不死去
假設在月有兔子總共對，月總共有對。在月必定總共有對：因為在月的時候，前一月（月）的對兔子可以存留至第月（在當月屬於新誕生的兔子尚不能生育）。而新生育出的兔子對數等於所有在月就已存在的對

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

表達式
為求得斐波那契數列的一般表達式，可以藉助線性代數的方法。高中的初等數學知識也能求出。

初等代數解法
已知

（n≥3）

首先構建等比數列
設化簡得
比較係數可得：

不妨設
解得：

又因为有，
即為等比數列。

求出數列
由以上可得：

變形得：
。
令

求數列進而得到

設，解得。
故數列為等比數列
即。而，
故有
又有
和
可得

得出表達式

用數學歸納法證明表達式 
證明，其中為黃金比例，為任意整數
若為非負整數
當時，，成立
當時，，成立
設當及時皆成立，即且
當時

亦成立
若為非正整數
當時，成立
當時，，成立
設當及時皆成立，即且
當時

亦成立

因此，根據數學歸納法原理，此表達式對於任意整數皆成立

線性代數解法

構建一個矩陣方程

設為第個月有生育能力的兔子數量，為這一月份的兔子數量。

上式表達了兩個月之間，兔子數目之間的關係。而要求的是，的表達式。

求矩陣的特徵值：

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

展开行列式有：。

故當行列式的值為 0，解得  或 。

特徵向量
將兩個特徵值代入

  

求特徵向量得

=

=

分解首向量
第一個月的情況是兔子一對，新生0對。

將它分解為用特徵向量表示。

  （4）

用數學歸納法證明

從
=

可得到

  （5）

化簡矩陣方程

將（4） 代入 （5）

根據3

求A的表達式
現在在6的基礎上，可以很快求出的表達式，將兩個特徵值代入6中

（7）

（7）即為的表達式

數論解法 
實際上，如果將斐波那契數列的通項公式寫成，即可利用解二階線性齊次遞迴關係式的方法，寫出其特徵多項式（該式和表達斐波那契數列的矩陣的特徵多項式一致），然後解出=，=，即有，其中为常数。我们知道，因此，解得。

組合數解法

黃金比例恆等式解法
設為黃金比例，則有恆等式與，其中為任意整數，則

因此得到的一般式：

此一般式對任意整數成立

近似值
當為足夠大的正整數時，则

用計算機求解
可通過編程觀察斐波那契數列。分為兩類問題，一種已知數列中的某一項，求序數。第二種是已知序數，求該項的值。

可通過遞歸遞推的算法解決此兩個問題。
事實上當相當巨大的時候，O（n）的遞推/遞歸非常慢……這時候要用到矩陣快速幂這一技巧，可以使遞迴加速到O(logn)。

和黃金分割的關係
開普勒發現數列前、後兩項之比，也組成了一個數列，會趨近黃金分割：

斐波那契數亦可以用連分數來表示：

而黃金分割數亦可以用無限連分數表示：

而黃金分割數也可以用無限多重根號表示：

和自然的關係

斐氏數列見於不同的生物學現象，如樹的分枝、、菠蘿聚花果上小單果的排列、雅枝竹的花蕾、正在舒展的蕨葉、松毬的鱗的排列、蜜蜂的家族樹。开普勒曾指出斐氏數列存在於自然界，並以此解釋某些花的五邊形形態（與黄金分割率相關）。法國菊的「瓣」（舌狀花）數通常為斐氏數。1830年，K. F. Schimper和A. Braun發現植物的旋生葉序中，連續兩塊葉之間轉過的角度與周角之比，約成整數比時，常出現斐氏數，如或。

恆等式
資料來源：

證明以下的恆等式有很多方法。以下會用組合論述來證明。
 可以表示用多個1和多個2相加令其和等於的方法的數目。
不失一般性，我們假設，是計算了將1和2加到n的方法的數目。若第一個被加數是1，有種方法來完成對的計算；若第一個被加數是2，有來完成對的計算。因此，共有種方法來計算n的值。
 
計算用多個1和多個2相加令其和等於的方法的數目，同時至少一個加數是2的情況。

如前所述，當，有種這樣的方法。因為當中只有一種方法不用使用2，就即　（項），於是我們從減去1。

若第1個被加數是2，有種方法來計算加至的方法的數目；
若第2個被加數是2、第1個被加數是1，有種方法來計算加至的方法的數目。
重複以上動作。
若第個被加數為2，它之前的被加數均為1，就有種方法來計算加至0的數目。

若該數式包含2為被加數，2的首次出現位置必然在第1和的被加數之間。2在不同位置的情況都考慮到後，得出為要求的數目。

 

，其中與的序數皆不限於正整數。
特別地，當時，
更特別地，當或時，對於數列連續三項，有
另一方面，當時，對於數列連續四項，有
且，其中為黃金比例，為任意整數
藉由上述公式，又可推得以下恆等式：

特別地，當時，

數論性質

公因數和整除關係 
整除，若且唯若整除，其中。

任意連續三個菲波那契數兩兩互質，亦即，對於每一個，

斐波那契质数

在斐波那契數列中，有質數：
2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……

截至2015年，已知最大的斐波那契質數是第104911個斐波那契數，一共有21925個十進制位。不过，人们仍不知道是不是有无限个斐波那契质数。

如所述，總能被整除，故除之外，任何斐氏質數的下標必同為質數。由於存在的一列連續合数，斐氏數列中亦能找到連續任意多項全為合數。

大於的斐氏數，必不等於質數加一或減一。

與其他數列的交集 
斐波那契数列中，只有3個平方數：0、1、144。2001年，證明衹有有限多個斐氏數是完全冪。2006年，Y. Bugeaud、M. Mignotte、S. Siksek三人證明此種冪僅得0、1、8、144。

1、3、21、55為僅有的斐氏三角形數。曾猜想此結論，後來由罗明證明。

斐波那契數不能為完全数。推而廣之，除1之外，其他斐氏數皆非多重完全數，任兩個斐氏數之比亦不能是完全數。

模n的週期性 

斐波那契數列各項模的餘數構成，其最小正週期稱為皮萨诺周期，至多為。皮薩諾週期對不同值的通項公式仍是未解問題，其中一步需要求出某個整數（同餘意義下）或二次有限域元素的。不過，對固定的，求解模的皮薩諾週期是問題的特例。

推廣
斐波那西數列是斐波那西n步數列步數為2的特殊情況，也和盧卡斯數列有關。

和盧卡斯數列的關係

反費波那西數列
反費波那西數列的遞歸公式如下：

如果它以1,-1開始，之後的數是：1,-1,2,-3,5,-8, ...

即是，

亦可寫成，其中是非負整數。

反費波那西數列兩項之間的比會趨近。

證明關係式
證明，其中是非負整數
以表示黃金分割數，則有
故，因此

巴都萬數列
費波那西數列可以用一個接一個的正方形來表現，巴都萬數列則是用一個接一個的等邊三角形來表現，它有的關係。

佩爾數列

佩爾數列的遞歸公式為，前幾項為0,1,2,5,12,29,70,169,408,...

應用
1970年，尤裏·馬季亞謝維奇指出了偶角標的斐波那契函數

正是滿足Julia Robison假設的丟番圖函數，因而證明了希爾伯特第十問題是不可解的。

電腦科學 

考慮以輾轉相除法求兩個正整數的最大公因數，分析此算法的運行時間。同等輸入規模下，最壞情況（用時最長）發生於輸入為兩個相鄰斐氏數時。
归并排序算法有一多相（）版本用到斐氏數列，是將未排序的數組分為兩份，長度為相鄰的斐氏數（因此比值接近黃金比）。《计算机程序设计艺术》描述了此種的實作方法，適用於以磁带机為外存的情況。
斐波那契樹是一棵二叉树，其每個節點的左右子树高皆恰好差1。由此，斐氏樹為AVL树，且對固定高度而言，是最少節點的AVL樹。此類樹的節點數可寫成斐氏數減1。
 某些伪随机数生成器用到斐氏數列。
 斐波那契堆是一種數據結構，分析其時間複雜度時會用到斐波那契數。
斐波那契编码是以01字串表示正整數的一種方法，與之類似，還可以表示負數。

程式參考
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皮科夫.數學之戀.湖南科技出版社.

參考文獻

註釋

參見
齊肯多夫定理

外部連結
費波那契數，孫智宏（pdf）
 Periods of Fibonacci Sequences Mod m at MathPages
 Scientists find clues to the formation of Fibonacci spirals in nature 
 
 

Fibonacci