檢視費波若契數的原始碼

'''費波若契數'''（義大利語：Successione di Fibonacci）， 閣譯做'''菲波提契數'''、'''菲波若西數'''、'''斐氏數'''、'''黃金分割數'''。所形成的數列號做'''費波彼契數列'''（義大利語：Successione di Fibonacci）， 閣譯做'''菲波提契數列'''、'''菲波若西數列'''、'''斐氏數列'''、'''黃金分割數列'''。這个數列是由義大利數學家費波若契佇伊的《算盤冊》中提出。

佇咧數學上，'''費波若契數'''是以遞迴的方法來定義：

* $ F _ { 零 }=零 $
* $ F _ { 一 }=一 $
* $ F _ { n }=F _ { n 影一 } + F _ { n 鋪二 } $（$ n \ geqq 二 $）

用文字來講，就是費氏數列由零佮一開始，了後的費波彼契數就是對進前的兩數相加就是對。首幾个費波彼契數是：


: 一、一、二、三、五、八、十三、二十一、三十四、五十五、八十九、一百四十四、兩百三十三、三百七十七、六百十一、九百八十七……（OEIS 數列 A 四十五）

'''特別指出講'''：零毋是頭一項，是第零項。

==起源==

公元一一五空年印度數學家 Gopala 佮金月咧研究箱仔包裝東西長闊拄仔好為一佮二的可行方法數目時，首先欲描述這个數列。佇西方，頭先研究這个數列的人是比薩的李奧納濟（義大利人費波那契 Leonardo Fibonacci , 一千一百七十五－千二五）， 伊講兔仔生長的數目的時陣用這數列：

* 頭一個月初有一對拄誕生的兔仔
* 第二個月了後（第三個月了後）𪜶會當生育
* 逐月逐對會當生育的兔仔會誕生落一對新兔仔
* 兔仔永遠袂死去假使佇 $ n $ 月有兔仔攏總 $ a $ 著，$ n + 一 $ 月攏總有 $ b $ 著。佇咧 $ n + 二 $ 月必定攏總有 $ a + b $ 著：因為佇咧 $ n + 二 $ 月娘的時陣，前一月（$ n + 一 $ 月）的 $ b $ 對兔仔會當存留到第 $ n + 二 $ 月（佇咧做月屬於新誕生的兔仔猶袂當生育）。 啊若新生育出的兔仔對數等於所有咧 $ n $ 月就已經存在的 $ a $ 著費波納契數嘛是楊輝三角的每一條紅色對角線頂頭數字的佮。

==表達式==

為著費氏數列的一般表達式，會當藉助線性代數的方法。高中的初等數學智識也通好求出。

===初等代數解法===

已知

* $ a _ { 一 }=一 $
* $ a _ { 二 }=一 $
* $ a _ { n }=a _ { n 影一 } + a _ { n 鋪二 } $（n≥ 三）

====頭起先構建等比數列====

設 $ a _ { n } + \ alpha a _ { n 影一 }=\ beta ( a _ { n 影一 } + \ alpha a _ { n 鋪二 } ) $
化予簡得
$ a _ { n }=( \ beta-\ alpha ) a _ { n 影一 } + \ alpha \ beta a _ { n 鋪二 } $
較係數會當講：
$ { \ begin { cases } \ beta-\ alpha=一 \ \ \ alpha \ beta=一 \ end { cases } } $

不妨設 $ \ beta > 零 , \ alpha > 零 $
解甲：

$ { \ begin { cases } \ alpha={ \ dfrac { { \ sqrt { 五 } } 影一 } { 二 } } \ \ \ beta={ \ dfrac { { \ sqrt { 五 } } + 一 } { 二 } } \ end { cases } } $

閣因為有 $ a _ { n } + \ alpha a _ { n 影一 }=\ beta ( a _ { n 影一 } + \ alpha a _ { n 鋪二 } ) $，
即 $ \ left \ { a _ { n } + \ alpha a _ { n 影一 } \ right \ } $ 為等比數列。

====求出數列 $ \ left \ { a _ { n } + \ alpha a _ { n 影一 } \ right \ } $====

由以上會使得：
$ { \ begin { aligned } a _ { n + 一 } + \ alpha a _ { n } &=( a _ { 二 } + \ alpha a _ { 一 } ) \ beta ^ { n 影一 } \ \ &=( 一 + \ alpha ) \ beta ^ { n 影一 } \ \ &=\ beta ^ { n } \ \ \ end { aligned } } $

變形得：$ { \ frac { a _ { n + 一 } } { \ beta ^ { n + 一 } } } + { \ frac { \ alpha } { \ beta } } \ cdot { \ frac { a _ { n } } { \ beta ^ { n } } }={ \ frac { 一 } { \ beta } } $。
令 $ b _ { n }={ \ frac { a _ { n } } { \ beta ^ { n } } } $

====求數列 $ \ left \ { { b _ { n } } \ right \ } $ 會得著這个 $ \ left \ { a _ { n } \ right \ } $====

$ b _ { n + 一 } + { \ frac { \ alpha } { \ beta } } b _ { n }={ \ frac { 一 } { \ beta } } $
設 $ b _ { n + 一 } + \ lambda=-{ \ frac { \ alpha } { \ beta } } ( b _ { n } + \ lambda ) $，解甲 $ \ lambda=-{ \ frac { 一 } { \ alpha + \ beta } } $。
故數列 $ \ left \ { b _ { n } + \ lambda \ right \ } $ 為等比數列即 $ b _ { n } + \ lambda=\ left (-{ \ frac { \ alpha } { \ beta } } \ right ) ^ { n 影一 } \ left ( b _ { 一 } + \ lambda \ right ) $。而且 $ b _ { 一 }={ \ frac { a _ { 一 } } { \ beta } }={ \ frac { 一 } { \ beta } } $，
故有 $ b _ { n } + \ lambda=\ left (-{ \ frac { \ alpha } { \ beta } } \ right ) ^ { n 影一 } \ left ( { \ frac { 一 } { \ beta } } + \ lambda \ right ) $
閣有 $ { \ begin { cases } \ alpha={ \ dfrac { { \ sqrt { 五 } } 影一 } { 二 } } \ \ \ beta={ \ dfrac { { \ sqrt { 五 } } + 一 } { 二 } } \ end { cases } } $ 和 $ b _ { n }={ \ frac { a _ { n } } { \ beta ^ { n } } } $
可得 $ a _ { n }={ \ frac { \ sqrt { 五 } } { 五 } } \ cdot \ left [\ left ( { \ frac { 一 + { \ sqrt { 五 } } } { 二 } } \ right ) ^ { n }-\ left ( { \ frac { 一-{ \ sqrt { 五 } } } { 二 } } \ right ) ^ { n } \ right] $

會出得 $ { a _ { n } } $ 表達式

$ $
a _ { n }={ \ frac { \ sqrt { 五 } } { 五 } } \ cdot \ left [\ left ( { \ frac { 一 + { \ sqrt { 五 } } } { 二 } } \ right ) ^ { n }-\ left ( { \ frac { 一-{ \ sqrt { 五 } } } { 二 } } \ right ) ^ { n } \ right]
$ $

====用數學歸納法證明表達式====

'''證明 $ F _ { n }={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { n }-( 一-\ varphi ) ^ { n }] $，其中 $ \ varphi $ 為黃金比例 $ { \ frac { 一 + { \ sqrt { 五 } } } { 二 } } $，$ n $ 為任意整數'''

* 若是 $ n $ 為非負整數


: 當 $ n=零 $ 時，$ { \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { 零 }-( 一-\ varphi ) ^ { 零 }]={ \ frac { 一 } { \ sqrt { 五 } } } [一孵一]=零=F _ { 零 } $，成立


: 當 $ n=一 $ 時，$ { \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { 一 }-( 一-\ varphi ) ^ { 一 }]={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi 影一 + \ varphi]={ \ frac { 一 } { \ sqrt { 五 } } } [二 \ varphi 影一]={ \ frac { 一 } { \ sqrt { 五 } } } \ times { \ sqrt { 五 } }=一=F _ { 一 } $，成立


: 設當 $ n=k $ 佮 $ n=k + 一 $ 時攏成立，即 $ F _ { k }={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { k }-( 一-\ varphi ) ^ { k }] $ 而且 $ F _ { k + 一 }={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { k + 一 }-( 一-\ varphi ) ^ { k + 一 }] $


: 當 $ n=k + 二 $ 時


: $ { \ begin { aligned } F _ { k + 二 } &=F _ { k + 一 } + F _ { k } \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { k + 一 }-( 一-\ varphi ) ^ { k + 一 }] + { \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { k }-( 一-\ varphi ) ^ { k }] \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { k + 一 } + \ varphi ^ { k }-( 一-\ varphi ) ^ { k + 一 }-( 一-\ varphi ) ^ { k }] \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } \ left \ { \ varphi ^ { k } ( { \ color { brown } \ varphi + 一 } )-( 一-\ varphi ) ^ { k } [{ \ color { green } ( 一-\ varphi ) + 一 }] \ right \ } \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } \ left \ { \ varphi ^ { k } ( { \ color { brown } \ varphi ^ { 二 } } )-( 一-\ varphi ) ^ { k } [{ \ color { green } ( 一-\ varphi ) ^ { 二 } }] \ right \ } \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } \ left \ { \ varphi ^ { k + 二 }-( 一-\ varphi ) ^ { k + 二 } \ right \ } \ \ \ end { aligned } } $


: 亦成立

* 若是 $ n $ 為非正整數


: 當 $ n=零 $ 時，成立


: 當 $ n=影一 $ 時，$ { \ frac { 一 } { \ sqrt { 五 } } } [{ \ color { brown } \ varphi ^ { 影一 } }-{ \ color { green } ( 一-\ varphi ) ^ { 影一 } }]={ \ frac { 一 } { \ sqrt { 五 } } } [( { \ color { brown } \ varphi 影一 } )-( { \ color { green }-\ varphi } )]={ \ frac { 一 } { \ sqrt { 五 } } } [二 \ varphi 影一]={ \ frac { 一 } { \ sqrt { 五 } } } \ times { \ sqrt { 五 } }=一=F _ { 影一 } $，成立


: 設當 $ n=-k $ 佮 $ n=-k 影一 $ 時攏成立，即 $ F _ {-k }={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ {-k }-( 一-\ varphi ) ^ {-k }] $ 而且 $ F _ {-k 影一 }={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ {-k 影一 }-( 一-\ varphi ) ^ {-k 影一 }] $


: 當 $ n=-k 鋪二 $ 時


: $ { \ begin { aligned } F _ {-k 鋪二 } &=F _ {-k }-F _ {-k 影一 } \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ {-k }-( 一-\ varphi ) ^ {-k }]-{ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ {-k 影一 }-( 一-\ varphi ) ^ {-k 影一 }] \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ {-k }-\ varphi ^ {-k 影一 }-( 一-\ varphi ) ^ {-k } + ( 一-\ varphi ) ^ {-k 影一 }] \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } \ left \ { \ varphi ^ {-k 影一 } ( { \ color { brown } \ varphi 影一 } )-( 一-\ varphi ) ^ {-k 影一 } [{ \ color { green } ( 一-\ varphi ) 影一 }]\ right \ } \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } \ left \ { \ varphi ^ {-k 影一 } ( { \ color { brown } \ varphi ^ { 影一 } } )-( 一-\ varphi ) ^ {-k 影一 } [{ \ color { green } ( 一-\ varphi ) ^ { 影一 } }] \ right \ } \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } \ left \ { \ varphi ^ {-k 鋪二 }-( 一-\ varphi ) ^ {-k 鋪二 } \ right \ } \ \ \ end { aligned } } $


: 抑是講成立所以，根據數學歸納法原理，此表達式對任意整數 $ n $ 攏成立

===線性代數解法===

$ $
{ \ begin { pmatrix } F _ { n + 二 } \ \ F _ { n + 一 } \ end { pmatrix } }={ \ begin { pmatrix } 一 & 一 \ \ 一 & 零 \ end { pmatrix } } \ cdot { \ begin { pmatrix } F _ { n + 一 } \ \ F _ { n } \ end { pmatrix } }
$ $

$ $
{ \ begin { pmatrix } F _ { n + 二 } & F _ { n + 一 } \ \ F _ { n + 一 } & F _ { n } \ end { pmatrix } }={ \ begin { pmatrix } 一 & 一 \ \ 一 & 零 \ end { pmatrix } } ^ { n + 一 }
$ $

====構建一个矩陣方程式====

設 $ J _ { n } $ 為第 $ n $ 個月有生育能力的兔仔數量，$ A _ { n } $ 為這月份的兔仔數量。


: $ { J _ { n + 一 } \ choose A _ { n + 一 } }={ \ begin { pmatrix } 零 & 一 \ \ 一 & 一 \ end { pmatrix } } \ cdot { J _ { n } \ choose A _ { n } } , $

上式去表達兩個月之間，兔仔數目之間的關係。若要求的是，$ A _ { n + 一 } $ 的表達式。

====求矩陣的特徵值：$ \ lambda $====

根據特徵值的計算公式，咱需要算出來 $ { \ begin { vmatrix }-\ lambda & 一 \ \ 一 & 一-\ lambda \ \ \ end { vmatrix } }=零 $ 所做對應的解。

展開行列式有：$-\ lambda ( 一-\ lambda ) 影一 \ times 一=\ lambda ^ { 二 }-\ lambda 影一 $。

故當行列式的值為零，解甲 $ \ lambda _ { 一 }={ \ frac { 一 } { 二 } } ( 一 + { \ sqrt { 五 } } ) $ 抑是 $ \ lambda _ { 二 }={ \ frac { 一 } { 二 } } ( 一-{ \ sqrt { 五 } } ) $。

====特徵向量====

共兩个特徵值代入


: $ \ left ( { \ begin { pmatrix } 零 & 一 \ \ 一 & 一 \ end { pmatrix } }-\ lambda \ cdot E \ right ) \ cdot { \ vec { x } }=零 $


求特徵向量 $ { \ vec { x } } $ 得

$ $
{ \ vec { x } } _ { 一 } $=$ { \ begin { pmatrix } 一 \ \ { \ frac { 一 } { 二 } } ( 一 + { \ sqrt { 五 } } ) \ end { pmatrix } }
$ $

$ $
{ \ vec { x } } _ { 二 } $=$ { \ begin { pmatrix } 一 \ \ { \ frac { 一 } { 二 } } ( 一-{ \ sqrt { 五 } } ) \ end { pmatrix } }
$ $

====分解首向量====

第一個月的情形是兔仔一對，新生零著。


: $ { J _ { 一 } \ choose A _ { 一 } }={ \ begin { pmatrix } 零 \ \ 一 \ end { pmatrix } } $

會伊分解做用特徵向量表示。


: $ { \ begin { pmatrix } 零 \ \ 一 \ end { pmatrix } }={ \ frac { 一 } { \ sqrt { 五 } } } \ cdot { \ begin { pmatrix } 一 \ \ { \ frac { 一 } { 二 } } ( 一 + { \ sqrt { 五 } } ) \ end { pmatrix } }-{ \ frac { 一 } { \ sqrt { 五 } } } \ cdot { \ begin { pmatrix } 一 \ \ { \ frac { 一 } { 二 } } ( 一-{ \ sqrt { 五 } } ) \ end { pmatrix } } $（四）

====用數學歸納法證明====

對


: $ { J _ { n + 一 } \ choose A _ { n + 一 } }={ \ begin { pmatrix } 零 & 一 \ \ 一 & 一 \ end { pmatrix } } \ cdot { J _ { n } \ choose A _ { n } } $=$ \ lambda \ cdot { J _ { n } \ choose A _ { n } } $

有得著


: $ { J _ { n + 一 } \ choose A _ { n + 一 } }={ \ begin { pmatrix } 零 & 一 \ \ 一 & 一 \ end { pmatrix } } ^ { n } \ cdot { J _ { 一 } \ choose A _ { 一 } }=\ lambda ^ { n } \ cdot { J _ { 一 } \ choose A _ { 一 } } $（五）

====化簡矩陣方程式====

將（四）代入（五）


: $ { J _ { n + 一 } \ choose A _ { n + 一 } }=\ lambda ^ { n } \ cdot \ left [{ \ frac { 一 } { \ sqrt { 五 } } } \ cdot { \ begin { pmatrix } 一 \ \ { \ frac { 一 } { 二 } } ( 一 + { \ sqrt { 五 } } ) \ end { pmatrix } }-{ \ frac { 一 } { \ sqrt { 五 } } } \ cdot { \ begin { pmatrix } 一 \ \ { \ frac { 一 } { 二 } } ( 一-{ \ sqrt { 五 } } ) \ end { pmatrix } } \ right] $

根據三


: $ { J _ { n + 一 } \ choose A _ { n + 一 } }={ \ frac { 一 } { \ sqrt { 五 } } } \ cdot \ lambda _ { 一 } ^ { n } \ cdot { \ begin { pmatrix } 一 \ \ { \ frac { 一 } { 二 } } ( 一 + { \ sqrt { 五 } } ) \ end { pmatrix } }-{ \ frac { 一 } { \ sqrt { 五 } } } \ cdot \ lambda _ { 二 } ^ { n } \ cdot { \ begin { pmatrix } 一 \ \ { \ frac { 一 } { 二 } } ( 一-{ \ sqrt { 五 } } ) \ end { pmatrix } } $

====求 A 的表達式====

這馬佇六的基礎頂懸，會當誠緊求出 $ A _ { n + 一 } $ 的表達式，共兩个特徵值代入六中


: $ A _ { n + 一 }={ \ frac { 一 } { \ sqrt { 五 } } } \ cdot \ lambda _ { 一 } ^ { n + 一 }-{ \ frac { 一 } { \ sqrt { 五 } } } \ cdot \ lambda _ { 二 } ^ { n + 一 } $


: $ A _ { n + 一 }={ \ frac { 一 } { \ sqrt { 五 } } } \ cdot ( \ lambda _ { 一 } ^ { n + 一 }-\ lambda _ { 二 } ^ { n + 一 } ) $


: $ A _ { n + 一 }={ \ frac { 一 } { \ sqrt { 五 } } } \ cdot \ left \ { \ left [{ \ frac { 一 } { 二 } } \ left ( 一 + { \ sqrt { 五 } } \ right ) \ right] ^ { n + 一 }-\ left [{ \ frac { 一 } { 二 } } ( 一-{ \ sqrt { 五 } } ) \ right] ^ { n + 一 } \ right \ } $（七）

（ 七）即為 $ A _ { n + 一 } $ 的表達式

===數論解法===

實際上，若將費氏數列的通項公式來寫 $ a _ { n }-a _ { n 影一 }-a _ { n 鋪二 }=零 $，就會當利用解二階線性齊次交迴關係式的方法，寫出其實特徵多項式 $ \ lambda ^ { 二 }-\ lambda 影一=零 $（該式佮表達費氏數列的矩陣的特徵多項式一致）， 閣解出講 $ \ lambda _ { 一 } $=$ { \ frac { 一 } { 二 } } ( 一 + { \ sqrt { 五 } } ) $，$ \ lambda _ { 二 } $=$ { \ frac { 一 } { 二 } } ( 一-{ \ sqrt { 五 } } ) $，即有 $ a _ { n }=c _ { 一 } \ lambda _ { 一 } ^ { n } + c _ { 二 } \ lambda _ { 二 } ^ { n } $，其中 $ c _ { 一 } , c _ { 二 } $ 為常數。咱知影 $ a _ { 零 }=零 , a _ { 一 }=一 $，所以 $ { \ begin { cases } c _ { 一 } + c _ { 二 }=零 \ \ { \ frac { c _ { 一 } ( 一 + { \ sqrt { 五 } } ) } { 二 } } + { \ frac { c _ { 二 } ( 一-{ \ sqrt { 五 } } ) } { 二 } }=一 \ end { cases } } $，解甲 $ c _ { 一 }={ \ frac { 一 } { \ sqrt { 五 } } } , c _ { 二 }=-{ \ frac { 一 } { \ sqrt { 五 } } } $。

===組合數解法===

$ $
F _ { n }=\ sum _ { i=零 } ^ { \ infty } { \ binom { n-i } { i } }
$ $


: $ F _ { n 影一 } + F _ { n }=\ sum _ { i=零 } ^ { \ infty } { \ binom { n 影一-i } { i } } + \ sum _ { i=零 } ^ { \ infty } { \ binom { n-i } { i } }=一 + \ sum _ { i=一 } ^ { \ infty } { \ binom { n-i } { i 影一 } } + \ sum _ { i=一 } ^ { \ infty } { \ binom { n-i } { i } }=一 + \ sum _ { i=一 } ^ { \ infty } { \ binom { n + 一-i } { i } }=\ sum _ { i=零 } ^ { \ infty } { \ binom { n + 一-i } { i } }=F _ { n + 一 } $

===黃金比例恆等式解法===

設 $ \ varphi $ 為黃金比例 $ { \ frac { 一 + { \ sqrt { 五 } } } { 二 } } $，有恆等式 $ \ varphi ^ { n }=F _ { n 影一 } + \ varphi F _ { n } $ 佮 $ ( 一-\ varphi ) ^ { n }=F _ { n + 一 }-\ varphi F _ { n } $，其中 $ n $ 為任意整數，著

$ $
{ \ begin { aligned } \ varphi ^ { n }-( 一-\ varphi ) ^ { n } &=( F _ { n 影一 } + \ varphi F _ { n } )-( F _ { n + 一 }-\ varphi F _ { n } ) \ \ &=( F _ { n 影一 }-F _ { n + 一 } ) + 二 \ varphi F _ { n } \ \ &=-F _ { n } + 二 \ varphi F _ { n } \ \ &=F _ { n } ( 二 \ varphi 影一 ) \ \ &=F _ { n } \ times { \ sqrt { 五 } } \ \ \ end { aligned } }
$ $

所以得著 $ F _ { n } $ 的一般式：

$ $
{ \ begin { aligned } F _ { n } &={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { n }-( 一-\ varphi ) ^ { n }] \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } \ left [( { \ frac { 一 + { \ sqrt { 五 } } } { 二 } } ) ^ { n }-( { \ frac { 一-{ \ sqrt { 五 } } } { 二 } } ) ^ { n } \ right] \ \ \ end { aligned } }
$ $

此一般式對任意整數 $ n $ 成立

===近來親像值===

當 $ n $ 為夠大的整數時候，著


: $ F _ { n } \ approx { \ frac { 一 } { \ sqrt { 五 } } } \ varphi ^ { n }={ \ frac { 一 } { \ sqrt { 五 } } } \ cdot \ left [{ \ frac { 一 } { 二 } } \ left ( 一 + { \ sqrt { 五 } } \ right ) \ right] ^ { n } \ approx 空九四四七二一三五九五五 \ cdot 一孵六一八空三三九八八七五 ^ { n } $


: $ F _ {-n } \ approx-{ \ frac { 一 } { \ sqrt { 五 } } } ( 一-\ varphi ) ^ {-n }=-{ \ frac { 一 } { \ sqrt { 五 } } } \ cdot \ left [{ \ frac { 一 } { 二 } } \ left ( 一-{ \ sqrt { 五 } } \ right ) \ right] ^ {-n } \ approx 抹空抹四四七二一三五九五五 \ cdot ( 鋪空七六一八空三三九八八七五 ) ^ {-n } $

===用計算機求解===

會當通過編程觀察費氏數列。分做兩類問題按呢，一款已知數列中的某一項，求序數。第二項是已經知序，求該項的值。

會通過遞迴遞推的算法解決這兩个問題。
事實上當 $ n $ 相當大摸的時陣，O（n）的遞推 / 遞迴非常慢…… 這个時陣愛用著矩陣快速冪這一个技巧，會當共交迴加速到 O ( logn )。

==和黃金分割的關係==

克卜勒發現數列前、後兩項比 $ { \ frac { 一 } { 二 } } , { \ frac { 二 } { 三 } } , { \ frac { 三 } { 五 } } , { \ frac { 五 } { 八 } } , { \ frac { 八 } { 十三 } } , { \ frac { 十三 } { 二十一 } } , { \ frac { 二十一 } { 三十四 } } , \ cdots $，嘛組成一个數列，會元近黃金分割：


: $ { \ frac { f _ { n + 一 } } { f _ { n } } } \ approx a={ \ frac { 一 } { 二 } } ( 一 + { \ sqrt { 五 } } )=\ varphi \ approx 一 { . } 六百十八 { . . . } $

費波彼契數亦會當用連分數來表示：

$ $
{ \ frac { 一 } { 一 } }=一 \ qquad { \ frac { 二 } { 一 } }=一 + { \ frac { 一 } { 一 } } \ qquad { \ frac { 三 } { 二 } }=一 + { \ frac { 一 } { 一 + { \ frac { 一 } { 一 } } } } \ qquad { \ frac { 五 } { 三 } }=一 + { \ frac { 一 } { 一 + { \ frac { 一 } { 一 + { \ frac { 一 } { 一 } } } } } } \ qquad { \ frac { 八 } { 五 } }=一 + { \ frac { 一 } { 一 + { \ frac { 一 } { 一 + { \ frac { 一 } { 一 + { \ frac { 一 } { 一 } } } } } } } }
$ $

$ $
F _ { n }={ \ frac { 一 } { \ sqrt { 五 } } } \ left [\ left ( { \ frac { 一 + { \ sqrt { 五 } } } { 二 } } \ right ) ^ { n }-\ left ( { \ frac { 一-{ \ sqrt { 五 } } } { 二 } } \ right ) ^ { n } \ right]={ \ varphi ^ { n } \ over { \ sqrt { 五 } } }-{ ( 一-\ varphi ) ^ { n } \ over { \ sqrt { 五 } } }
$ $

抑若黃金分割數亦會當用無限連分數表示：


: $ \ varphi=一 + { \ frac { 一 } { 一 + { \ frac { 一 } { 一 + { \ frac { 一 } { 一 + { \ frac { 一 } { 一 + . . . } } } } } } } } $

黃金分割數也會當用無限偌重根號表示：


: $ \ varphi={ \ sqrt { 一 + { \ sqrt { 一 + { \ sqrt { 一 + { \ sqrt { 一 + . . . } } } } } } } } $

==佮自然的關係==

斐氏數列看著無仝款的生物學現象，如樹的分枝、葉佇枝條頂懸的排列、菠薐仔聚花果上小單果的排列、雅枝竹的花莓、當咧四展的蕨葉、松曉鱗的排列、蜂的家族樹。克卜勒捌指出斐氏數列存在佇咧自然界，而且解說某寡花的五邊形態（佮黃金分割率相關）。 法國菊的「瓣」（舌狀花）數通常是斐氏數。一八三空年，K . F . Schimper 和 A . Braun 發現植物的旋生葉仔序中，連紲兩塊葉之間轉過的角度佮周角之比，約做整數比的時陣，定出現斐氏數，如 $ 五分之二 $ 抑是 $ 十三分之五 $。

==恆等式==

資料來源：

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

* $ F _ { n } $ 會當表示用多個一佮多個二相加令其佮等於 $ n $ 的方法的數目。

無去一般性，阮假使講 $ n \ geq 一 $，$ F _ { n + 一 } $ 是計算了共一佮二加到 n 的方法的數目。若第一个被加數是一，有 $ F _ { n } $ 種方法來完成著 $ n 影一 $ 的計算；若第一个被加數是二，有 $ F _ { n 影一 } $ 來完成著 $ n 鋪二 $ 的計算。所以，共有 $ F _ { n } + F _ { n 影一 } $ 種方法來計算 n 的值。

* $ F _ { 零 } + F _ { 一 } + F _ { 二 } + F _ { 三 } + . . . + F _ { n }=F _ { n + 二 } 影一 $

計算用濟个偌个加一粒二相加令其佮等於 $ n + 一 $ 的方法的數目，同時上無一个加數是兩的狀況。

如前咧講，當 $ n > 零 $，有 $ F _ { n + 二 } $ 種按呢的方法。因為中央干焦一種方法無咧使用二，就即 $ 一 + 一 + . . . + 一 $　（$ n + 一 $ 項）， 所以咱對按呢 $ F _ { n + 二 } $ 減去一。

一 . 若第一个被加數是二，有 $ F _ { n } $ 種方法來算加至講 $ n 影一 $ 的方法的數目；
二 . 若第二个被加數是二、第一个被加數是一，有 $ F _ { n 影一 } $ 種方法來算加至講 $ n 鋪二 $ 的方法的數目。
三 . 重複以上動作。
四 . 你若第 $ n + 一 $ 個被加數為二，伊進前的予人加數攏總為一，就有 $ F _ { 零 } $ 種方法來計算加到零的數目。

若這个數式包括二為被加數，字的頭一擺出現位置必然佇第一和 $ n + 一 $ 的被加數之間。二在無仝位置的情況攏考慮著了後，會出得 $ F _ { n } + F _ { n 影一 } + . . . + F _ { 零 } $ 為要求的數目。

* $ F _ { 一 } + 二 F _ { 二 } + 三 F _ { 三 } + . . . + nF _ { n }=nF _ { n + 二 }-F _ { n + 三 } + 二 $
* $ F _ { 一 } + F _ { 三 } + F _ { 五 } + . . . + F _ { 二 n 影一 }=F _ { 二 n } $
* $ F _ { 二 } + F _ { 四 } + F _ { 六 } + . . . + F _ { 二 n }=F _ { 二 n + 一 } 影一 $
* $ { F _ { 一 } } ^ { 二 } + { F _ { 二 } } ^ { 二 } + { F _ { 三 } } ^ { 二 } + . . . + { F _ { n } } ^ { 二 }=F _ { n } F _ { n + 一 } $
* $ F _ { n } F _ { m-k }-F _ { m } F _ { n-k }=( 影一 ) ^ { n-k } F _ { m-n } F _ { k } $，其中 $ m , n , k $ 佮 $ F $ 的序數攏無限制正整數。
* 特別地，當 $ n=m-k $ 時，$ { F _ { n } } ^ { 二 }-F _ { n + k } F _ { n-k }=( 影一 ) ^ { n-k } { F _ { k } } ^ { 二 } $
* 閣較特別，當 $ k=一 $ 抑是 $ k=影一 $ 時，對數列連紲三項，有 $ { F _ { n } } ^ { 二 }-F _ { n 影一 } F _ { n + 一 }=( 影一 ) ^ { n 影一 } $
* 另外一方面，當 $ ( m , n , k )=( n + 一 , n , 鋪二 ) $ 時，對數列連紲四項，有 $ F _ { n } F _ { n + 三 }-F _ { n + 一 } F _ { n + 二 }=( 影一 ) ^ { n + 一 } $
* $ \ varphi ^ { n }=F _ { n 影一 } + \ varphi F _ { n } $ 而且 $ ( 一-\ varphi ) ^ { n }=F _ { n + 一 }-\ varphi F _ { n } $，其中 $ \ varphi $ 為黃金比例 $ { \ frac { 一 + { \ sqrt { 五 } } } { 二 } } $，$ n $ 為任意整數


: : 藉著公式，閣會當捒伊的下跤恆等式的：

* * $ { F _ { m } } { F _ { n } } + { F _ { m 影一 } } { F _ { n 影一 } }=F _ { m + n 影一 } $
* $ F _ { m } F _ { n + 一 } + F _ { m 影一 } F _ { n }=F _ { m + n } $ 特別地，當 $ m=n $ 時，$ { \ begin { aligned } F _ { 二 n 影一 } &=F _ { n } ^ { 二 } + F _ { n 影一 } ^ { 二 } \ \ F _ { 二 n } &=( F _ { n 影一 } + F _ { n + 一 } ) F _ { n } \ \ &=( 二 F _ { n 影一 } + F _ { n } ) F _ { n } \ end { aligned } } $

==數論性質==

===公因數佮整除關係===

* $ F _ { n } $ 整除 $ F _ { m } $，若是唯一 $ n $ 整除 $ m $，其中 $ n \ geqq 三 $。
* $ \ gcd ( F _ { m } , F _ { n } )=F _ { \ gcd ( m , n ) } $
* 任意連紲三个菲波彼契數兩兩互質，亦即，對著每一个 $ n $，


: $ \ mathrm { gcd } ( F _ { n } , F _ { n + 一 } )=\ mathrm { gcd } ( F _ { n } , F _ { n + 二 } )=\ mathrm { gcd } ( F _ { n + 一 } , F _ { n + 二 } )=一 $

===費波那契質數===

佇費氏數列中間，有質數：
二 , 三 , 五 , 十三 , 八十九 , 兩百三十三 , 一千五百九十七 , 二鋪八千六百五十七 , 五十一孵四千兩百二十九 , 四四五三千三百四十九九九五四千四百三十七 , 二十九石七千一百二十一石五千空七十三 , 99194853094755497 , 1066340417491710595814572169 , 19134702400093278081449423917……

節甲二空一五年，已知上大的費波彼契質數是第十尺尺四千九百十一个費波彼契數，攏總有二石一千九百二十五个十進制位。猶毋過，猶原毋知影是毋是有限一个費波彼契質數。

如 §  公因數佮整除關係所講，$ F _ { kn } $ 總會去予 $ F _ { n } $ 整除，故除 $ F _ { 四 }=三 $ 以外，任何斐氏質數的下標必同為質數。因為存在任意長的一列連紲合數，斐氏數列中亦能揣著連續任意濟項攏為合數。

大於 $ F _ { 六 }=八 $ 斐氏數，必不等於質數加一抑是減一。

===佮其他的數列的交集===

費氏數列中，干焦三个平方數：零、一、一百四十四。二空空一年，派特 ・ 奧蒂洛證明交有限濟个斐氏數是完全冪。二空空六年，Y . Bugeaud、M . Mignotte、S . Siksek 三人證明此種冪干焦得零、一、八、一百四十四。

一、三、二十一、五十五是干焦有的斐氏三角形數。Vern Hoggatt 捌猜想此結論，後來由羅明證明。

費波若契數袂當為完全數。推捒了後，除一以外，其他斐氏數攏非常濟重完全數，任兩个斐氏數之比嘛袂用是完全數。

===模 _ n _ 的週期性===

費氏數列各項模 $ n $ 的餘數構成週期數列，其上細正禮拜號做皮薩諾週期，至濟為 $ 六 n $。皮薩諾週期著無仝 $ n $ 值的通項公式猶原無解問題，其中一步需要求出某一个整數（同餘意義下）或者是二改有限體元素的乘法階數。猶毋過，嘿固定的 $ n $，求解模 $ n $ 的皮薩諾週期是週期檢測問題的特例。

==推廣==

斐波彼西數列是斐波彼西 n 步數列步數為而且的特殊情況，嘛佮盧卡斯數列有關係。

===佮盧卡斯數列的關係===


: $ F _ { n } L _ { n }=F _ { 二 n } $

===反費波若西數列===

反費波若西數列的遞迴公式如下：


: $ G _ { n + 二 }=G _ { n }-G _ { n + 一 } $

若是講伊以一 , 孵一開始，尾仔的數是：一 , 影一 , 二 , ma三 , 五 , ma八 , . . .

即是 $ F _ { 二 n + 一 }=G _ { 二 n + 一 }=F _ {-( 二 n + 一 ) } , F _ { 二 n }=-G _ { 二 n }=-F _ { 鋪二 n } $，

亦可寫 $ F _ { m }=( 影一 ) ^ { m + 一 } G _ { m }=( 影一 ) ^ { m + 一 } F _ {-m } $，其中 $ m $ 是非負整數。

反費波若西數列兩項之間的比會較近 $-{ \ frac { 一 } { \ varphi } } \ approx 鋪空芳一八 $。

====證明關係式====

證明 $ F _ { m }=( 影一 ) ^ { m + 一 } F _ {-m } $，其中 $ m $ 是非負整數


: 以 $ \ varphi $ 表示黃金分割數 $ { \ frac { 一 + { \ sqrt { 五 } } } { 二 } } $，則有 $ \ varphi ( 一-\ varphi )=影一 $


: 故 $ ( 影一 ) ^ { m }=[\ varphi ( 一-\ varphi )] ^ { m }=\ varphi ^ { m } ( 一-\ varphi ) ^ { m } $，所以


: $ { \ begin { aligned } ( 影一 ) ^ { m + 一 } F _ {-m } &=( 影一 ) ^ { m + 一 } \ times { \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ {-m }-( 一-\ varphi ) ^ {-m }] \ \ &=( 影一 ) \ times { \ color { brown } ( 影一 ) ^ { m } } \ times { \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ {-m }-( 一-\ varphi ) ^ {-m }] \ \ &=( 影一 ) \ times { \ color { brown } \ varphi ^ { m } ( 一-\ varphi ) ^ { m } } \ times { \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ {-m }-( 一-\ varphi ) ^ {-m }] \ \ &=( 影一 ) \ times { \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ {-m + m } ( 一-\ varphi ) ^ { m }-( 一-\ varphi ) ^ {-m + m } \ varphi ^ { m }] \ \ &=( 影一 ) \ times { \ frac { 一 } { \ sqrt { 五 } } } [( 一-\ varphi ) ^ { m }-\ varphi ^ { m }] \ \ &={ \ frac { 一 } { \ sqrt { 五 } } } [\ varphi ^ { m }-( 一-\ varphi ) ^ { m }] \ \ &=F _ { m } \ \ \ end { aligned } } $

===巴都萬數列===

費波若西數列會當用一个接一个的正四角形來表現，巴都萬數列則是用一个接一个的等邊三角形來表現，伊有 $ P _ { n }=P _ { n 鋪二 } + P _ { n ma三 } $ 的關係。

===佩爾數列===

佩爾數列的遞迴公式為 $ P _ { n }=二 P _ { n 影一 } + P _ { n 鋪二 } $，前幾項為零 , 一 , 二 , 五 , 十二 , 二十九 , 七十 , 百六九 , 四百空八 , . . .

==應用==

一九七空年，尤內 ・ 馬季亞謝維奇指出了雙角標的費波彼契函數


: $ y=F _ { 二 x } $

真的是滿足 Julia Robison 設的擲番圖函數，因為證明矣希爾伯特第十問題是袂當解的。

===電腦科學===

* 考慮以碖轉相除法求兩个正整數的最大公因數，分析這算法的運行時間。同等輸入規模下，上歹看（用的時陣上長）發生佇輸入做兩个相鄰斐氏數時。
* 歸併排序算法有一寡相（polyphase）版本用到斐氏欲數列，是共排序無排序的數組分做兩份，長度是相鄰的斐氏數（因此比值接近黃金比）。《電腦程式設計藝術》描述這款濟相合併排序的實作方法，適用佇磁帶機做外存的狀況。
* 費波彼契樹仔是一欉兩箍樹仔，其實每一个節點的左右樹懸攏拄好差一。由此，斐氏樹為 AVL 樹，而且對固定懸度而言，是上少節點的 AVL 樹。這類樹仔的節點數通寫做斐氏數減一。
* 某寡假隨機數生成器用著斐氏數列。
* 費波彼契堆是一種數據結構，分析其時間複雜度時間會用著費波那契數。
* 費波彼契編碼是用一字串表示正整數的一種方法，負費波彼契編碼佮之類似，猶閣會當表示負數。

==程式來參考==

JavaScript 迵天代版

C 語言通項公式版

c + + 二變數求某項版

c + + 通項公式版

Python 語言通項公式版

Common Lisp

Go

遞迴版，時間複雜度做 O ( 二 ^ n )：

通用版，時間複雜度做 O ( n )：

Java 語言遞迴版：

Java 語言快捷版：

C 語言陣列版：

Python Lambda 遞迴版 :

==延伸閱讀==

* KNUTH , D . E . 一千九百九十七 . The Art of Computer ProgrammingArt of Computer Programming , Volume 一 : Fundamental Algorithms , Third Edition . Addison-Wesley . Chapter 一孵二 . 八 .
* Arakelian , Hrant ( 二千空一十四 ) . _ Mathematics and History of the Golden Section _ . Logos , 四百空四 p . ISBN 九百七十八追五鋪九九九八千七百空四淋六百六十三孵空 , ( rus . )
* 克內福德 A 皮科夫。數學之戀。湖南科技出版社 .

==參考文獻==

* Livio , Mario . The Golden Ratio : The Story of Phi , the World's Most Astonishing Number First trade paperback . New York City : Broadway Books . 兩千空三 [兩千空二] . ISBN  空九五七千六百七十九九分八百一十六分三 .

==註解==

==參見==

* 較有肯濟夫定理

==外部連結==

* 費波若契數，孫智宏（pdf）
* Periods of Fibonacci Sequences Mod m at MathPages
* Scientists find clues to the formation of Fibonacci spirals in nature
* * Fibonacci Sequence，In Our Time ( BBC Radio 四 ) 的《In Our Time》節目。( 這馬聆聽 )
* Hazewinkel , Michiel ( 編 ) , Fibonacci numbers , 被鋪百科全鋪排，Springer , 兩千空一 , ISBN  九百七十八孵一一鋪五千六百空八鋪十跡四

[[分類: 待校正]]