費氏數列

以費波那契數為邊的正方形拼成的近似的黃金矩形

費波那契數列義大利語:Successione di Fibonacci),又譯為費波拿契數斐波那契數列費氏數列黃金分割數列

數學上,費波那契數列是以遞迴的方法來定義:

  • (n≧2)

用文字來說,就是費波那契數列由0和1開始,之後的費波那契系數就是由之前的兩數相加而得出。首幾個費波那契系數是:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……(OEIS中的數列A000045

特別指出:0不是第一項,而是第零項。

源起

根據高德納(Donald Ervin Knuth)的《計算機程式設計藝術》(The Art of Computer Programming),1150年印度數學家Gopala和金月在研究箱子包裝物件長寬剛好為1和2的可行方法數目時,首先描述這個數列。在西方,最先研究這個數列的人是比薩的李奧納多(義大利人斐波那契Leonardo Fibonacci),他描述兔子生長的數目時用上了這數列:

  • 第一個月初有一對剛誕生的兔子
  • 第二個月之後(第三個月初)牠們可以生育
  • 每月每對可生育的兔子會誕生下一對新兔子
  • 兔子永不死去

假設在n月有兔子總共a對,n+1月總共有b對。在n+2月必定總共有a+b對:因為在n+2月的時候,前一月(n+1月)的b對兔子可以存留至第n+2月(在當月屬於新誕生的兔子尚不能生育)。而新生育出的兔子對數等於所有在n月就已存在的a對

表達式

為求得費氏數列的一般表達式,可以藉助線性代數的方法。高中的初等數學知識也能求出。

初等代數解法

已知

  •  
  •  
  •  

首先構建等比數列

 
化簡得
 
比較係數可得:
 
不妨設 
解得:

 
所以有 , 即 為等比數列。

求出數列{ }

由以上可得:
 

變形得:  。 令 

求數列{ }進而得到{ }

 
 ,解得 。 故數列 為等比數列
 。而 , 故有 
又有  
可得 

得出 表達式

 

線性代數解法

 

 

構建一個矩陣方程

設Jn為第n個月有生育能力的兔子數量,An為這一月份的兔子數量。

 

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

求矩陣的特徵值: 

行列式: 

當行列式的值為0,解得 =  = 

特徵向量

將兩個特徵值代入

 


求特徵向量 

 = 

 = 

分解首向量

第一個月的情況是兔子一對,新生0對。

 

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

  (4)

數學歸納法證明

 = 

可得到

  (5)

化簡矩陣方程

將(4) 代入 (5)

 

根據3

 

求A的表達式

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

 
 
 (7)

(7)即為An+1的表達式

組合數解法

 [1]

 

近似值

 

用計算機求解

可通過編程觀察費氏數列。分為兩類問題,一種已知數列中的某一項,求序數。第二種是已知序數,求該項的值。

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

和黃金分割的關係

克卜勒發現數列前、後兩項之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,...... ,也組成了一個數列,會趨近黃金分割:

 

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

 

 

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

 

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

 

和自然的關係

許多的生物構成都和費氏數列有正相關。例如人體從腳底至頭頂之距離和從肚臍至腳底之距趨近於  ,向日葵種子螺旋排列有99%是 

恆等式

證明以下的恆等式有很多方法。以下會用組合論述來證明。

  •  可以表示用多個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在不同位置的情況都考慮到後,得出 為要求的數目。

  •  
  •  
  •  
  •  
  •  

定理

 

特別地,當m = n時,

 
  •  整除 ,若且唯若n整除m,其中n≧3。
  •  
  • 任意連續三個菲波那契數兩兩互質,亦即,對於每一個n
gcd(Fn, Fn+1) = gcd(Fn, Fn+2) = gcd(Fn+1, Fn+2) = 1

相關的數列

費波那西數列是費波那西n步數列步數為2的特殊情況,也和盧卡斯數列有關。

和盧卡斯數列的關係

反費波那西數列

反費波那西數列的遞迴公式如下:

 

如果它以1,-1,之後的數是:1,-1,2,-3,5,-8, ...

即是 

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

巴都萬數列

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

應用

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

 

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

相關猜想

費氏數列中是否存在無窮多個質數?

在費氏數列中,有質數: 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917…… 目前已知最大質數是第81839個斐波那契數,一共有17103位數。

程式參考

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語言通項公式版

int fib(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;
    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
", value_2);
        }
        return 0;
    }
    else
    {
        return -1;
    }
}

C++語言

#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
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;
    cin >> 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);
            cout << value_2 << endl;
        }
        return 0;
    }
    else
    {
        return -1;
    }
}

Python語言通項公式版

 1 # Fibonacci numbers module
 2 
 3 def fib(n):    # write Fibonacci series up to n
 4     a, b = 0, 1
 5     while b < n:
 6         print(b, end=' ')
 7         a, b = b, a+b
 8     print()
 9 
10 def fib2(n):   # return Fibonacci series up to n
11     result = []
12     a, b = 0, 1
13     while b < n:
14         result.append(b)
15         a, b = b, a+b
16     return result
fibs = [0, 1]
numZS = 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)))

參考文獻

  • 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. ^ 斐波那契數列與組合數的一個關係及推廣. 

參見

外部連結