斐波那契数列










以費波那契數為邊的正方形拼成的近似的黃金矩形(1:1.618)


斐波那契数列(意大利语:Successione di Fibonacci),又譯為菲波拿契數列菲波那西數列費氏數列黃金分割數列


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



  • F0=0{displaystyle F_{0}=0}F_{0}=0

  • F1=1{displaystyle F_{1}=1}F_{1}=1


  • Fn=Fn−1+Fn−2{displaystyle F_{n}=F_{n-1}+F_{n-2}}F_{n}=F_{{n-1}}+F_{{n-2}}(n≧2)


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


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


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




目录






  • 1 源起


  • 2 表達式


    • 2.1 初等代數解法


      • 2.1.1 首先構建等比數列


      • 2.1.2 求出數列{an+αan−1{displaystyle a_{n}+alpha a_{n-1}}a_{n}+alpha a_{{n-1}}}


      • 2.1.3 求數列{bn{displaystyle b_{n}}b_{n}}進而得到{an{displaystyle a_{n}}a_{n}}




    • 2.2 線性代數解法


      • 2.2.1 構建一個矩陣方程


      • 2.2.2 求矩陣的特徵值:λ{displaystyle lambda } lambda


      • 2.2.3 特徵向量


      • 2.2.4 分解首向量


      • 2.2.5 用數學歸納法證明


      • 2.2.6 化簡矩陣方程


      • 2.2.7 求A的表達式




    • 2.3 數論解法


    • 2.4 組合數解法


    • 2.5 近似值


    • 2.6 用計算機求解




  • 3 和黃金分割的關係


  • 4 和自然的關係


  • 5 恆等式


  • 6 定理


  • 7 相關的數列


    • 7.1 和盧卡斯數列的關係


    • 7.2 反費波那西數列


    • 7.3 巴都萬數列




  • 8 應用


  • 9 相關猜想


  • 10 程式參考


  • 11 參考文獻


  • 12 參見


  • 13 外部連結





源起


根據高德納(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對




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


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



表達式


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



初等代數解法


已知



  • a1=1{displaystyle a_{1}=1}a_{1}=1

  • a2=1{displaystyle a_{2}=1}a_{2}=1

  • an=an−1+an−2{displaystyle a_{n}=a_{n-1}+a_{n-2}}a_{n}=a_{{n-1}}+a_{{n-2}}



首先構建等比數列


an+αan−1=β(an−1+αan−2){displaystyle a_{n}+alpha a_{n-1}=beta (a_{n-1}+alpha a_{n-2})}a_{n}+alpha a_{{n-1}}=beta (a_{{n-1}}+alpha a_{{n-2}})
化簡得
an=(βα)an−1+αβan−2{displaystyle a_{n}=(beta -alpha )a_{n-1}+alpha beta a_{n-2}}a_{n}=(beta -alpha )a_{{n-1}}+alpha beta a_{{n-2}}

比較係數可得:
α=1αβ=1{displaystyle {begin{cases}beta -alpha =1\alpha beta =1end{cases}}}{begin{cases}beta -alpha =1\alpha beta =1end{cases}}

不妨設β>0,α>0{displaystyle beta >0,alpha >0}beta >0,alpha >0

解得:


=5−12β=5+12{displaystyle {begin{cases}alpha ={dfrac {{sqrt {5}}-1}{2}}\beta ={dfrac {{sqrt {5}}+1}{2}}end{cases}}}{begin{cases}alpha ={dfrac  {{sqrt  {5}}-1}{2}}\beta ={dfrac  {{sqrt  {5}}+1}{2}}end{cases}}


又因为有an+αan−1=β(an−1+αan−2){displaystyle a_{n}+alpha a_{n-1}=beta (a_{n-1}+alpha a_{n-2})}a_{n}+alpha a_{{n-1}}=beta (a_{{n-1}}+alpha a_{{n-2}})
{an+αan−1}{displaystyle left{a_{n}+alpha a_{n-1}right}}left{a_{n}+alpha a_{{n-1}}right}為等比數列。



求出數列{an+αan−1{displaystyle a_{n}+alpha a_{n-1}}a_{n}+alpha a_{{n-1}}}


由以上可得:
an+1+αan=(a2+αa1)βn−1=(1+αn−1=βn{displaystyle {begin{aligned}a_{n+1}+alpha a_{n}&=(a_{2}+alpha a_{1})beta ^{n-1}\&=(1+alpha )beta ^{n-1}\&=beta ^{n}\end{aligned}}}{begin{aligned}a_{{n+1}}+alpha a_{{n}}&=(a_{2}+alpha a_{1})beta ^{{n-1}}\&=(1+alpha )beta ^{{n-1}}\&=beta ^{n}\end{aligned}}


變形得:
an+1βn+1+αβanβn=1β{displaystyle {frac {a_{n+1}}{beta ^{n+1}}}+{frac {alpha }{beta }}{frac {a_{n}}{beta ^{n}}}={frac {1}{beta }}}{frac  {a_{{n+1}}}{beta ^{{n+1}}}}+{frac  {alpha }{beta }}{frac  {a_{{n}}}{beta ^{{n}}}}={frac  {1}{beta }}
bn=anβn{displaystyle b_{n}={frac {a_{n}}{beta ^{n}}}}b_{n}={frac  {a_{n}}{beta ^{n}}}



求數列{bn{displaystyle b_{n}}b_{n}}進而得到{an{displaystyle a_{n}}a_{n}}


bn+1+αβbn=1β{displaystyle b_{n+1}+{frac {alpha }{beta }}b_{n}={frac {1}{beta }}}b_{{n+1}}+{frac  {alpha }{beta }}b_{{n}}={frac  {1}{beta }}

bn+1+λ=−αβ(bn+λ){displaystyle b_{n+1}+lambda =-{frac {alpha }{beta }}(b_{n}+lambda )}b_{{n+1}}+lambda =-{frac  {alpha }{beta }}(b_{{n}}+lambda ),解得λ=−{displaystyle lambda =-{frac {1}{alpha +beta }}}lambda =-{frac  {1}{alpha +beta }}
故數列{bn+λ}{displaystyle left{b_{n}+lambda right}}left{b_{n}+lambda right}為等比數列

bn+λ=(−αβ)n−1(b1+λ){displaystyle b_{n}+lambda =left(-{frac {alpha }{beta }}right)^{n-1}left(b_{1}+lambda right)}b_{n}+lambda =left(-{frac  {alpha }{beta }}right)^{{n-1}}left(b_{1}+lambda right)。而b1=a1β=1β{displaystyle b_{1}={frac {a_{1}}{beta }}={frac {1}{beta }}}b_{1}={frac  {a_{1}}{beta }}={frac  {1}{beta }}
故有bn+λ=(−αβ)n−1(1β){displaystyle b_{n}+lambda =left(-{frac {alpha }{beta }}right)^{n-1}left({frac {1}{beta }}+lambda right)}b_{n}+lambda =left(-{frac  {alpha }{beta }}right)^{{n-1}}left({frac  {1}{beta }}+lambda right)

又有=5−12β=5+12{displaystyle {begin{cases}alpha ={dfrac {{sqrt {5}}-1}{2}}\beta ={dfrac {{sqrt {5}}+1}{2}}end{cases}}}{begin{cases}alpha ={dfrac  {{sqrt  {5}}-1}{2}}\beta ={dfrac  {{sqrt  {5}}+1}{2}}end{cases}}
bn=anβn{displaystyle b_{n}={frac {a_{n}}{beta ^{n}}}}b_{n}={frac  {a_{n}}{beta ^{n}}}

可得an=55⋅[(1+52)n−(1−52)n]{displaystyle a_{n}={frac {sqrt {5}}{5}}cdot left[left({frac {1+{sqrt {5}}}{2}}right)^{n}-left({frac {1-{sqrt {5}}}{2}}right)^{n}right]}a_{{n}}={frac  {{sqrt  {5}}}{5}}cdot left[left({frac  {1+{sqrt  {5}}}{2}}right)^{{n}}-left({frac  {1-{sqrt  {5}}}{2}}right)^{{n}}right]


得出an{displaystyle {a_{n}}}{a_{n}}表達式


an=55⋅[(1+52)n−(1−52)n]{displaystyle a_{n}={frac {sqrt {5}}{5}}cdot left[left({frac {1+{sqrt {5}}}{2}}right)^{n}-left({frac {1-{sqrt {5}}}{2}}right)^{n}right]}a_{{n}}={frac  {{sqrt  {5}}}{5}}cdot left[left({frac  {1+{sqrt  {5}}}{2}}right)^{{n}}-left({frac  {1-{sqrt  {5}}}{2}}right)^{{n}}right]



線性代數解法


(Fn+2Fn+1)=(1110)⋅(Fn+1Fn){displaystyle {begin{pmatrix}F_{n+2}\F_{n+1}end{pmatrix}}={begin{pmatrix}1&1\1&0end{pmatrix}}cdot {begin{pmatrix}F_{n+1}\F_{n}end{pmatrix}}}{begin{pmatrix}F_{{n+2}}\F_{{n+1}}end{pmatrix}}={begin{pmatrix}1&1\1&0end{pmatrix}}cdot {begin{pmatrix}F_{{n+1}}\F_{{n}}end{pmatrix}}


(Fn+2Fn+1Fn+1Fn)=(1110)n+1{displaystyle {begin{pmatrix}F_{n+2}&F_{n+1}\F_{n+1}&F_{n}end{pmatrix}}={begin{pmatrix}1&1\1&0end{pmatrix}}^{n+1}}{begin{pmatrix}F_{{n+2}}&F_{{n+1}}\F_{{n+1}}&F_{{n}}end{pmatrix}}={begin{pmatrix}1&1\1&0end{pmatrix}}^{{n+1}}



構建一個矩陣方程


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


(Jn+1An+1)=(0111)⋅(JnAn),{displaystyle {J_{n+1} choose A_{n+1}}={begin{pmatrix}0&1\1&1end{pmatrix}}cdot {J_{n} choose A_{n}},}{J_{{n+1}} choose A_{{n+1}}}={begin{pmatrix}0&1\1&1end{pmatrix}}cdot {J_{n} choose A_{{n}}},

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



求矩陣的特徵值:λ{displaystyle lambda } lambda


行列式:λ(1−λ)−1=λ2−λ1{displaystyle -lambda (1-lambda )-1times 1=lambda ^{2}-lambda -1}{displaystyle -lambda (1-lambda )-1times 1=lambda ^{2}-lambda -1}


當行列式的值為0,解得λ1{displaystyle lambda _{1}}lambda _{1}=12(1+5){displaystyle {frac {1}{2}}(1+{sqrt {5}})}{frac  {1}{2}}(1+{sqrt  {5}})λ2{displaystyle lambda _{2}}lambda _{2}=12(1−5){displaystyle {frac {1}{2}}(1-{sqrt {5}})}{frac  {1}{2}}(1-{sqrt  {5}})



特徵向量


將兩個特徵值代入


((0111)−λE)⋅x→=0{displaystyle ({begin{pmatrix}0&1\1&1end{pmatrix}}-lambda cdot E)cdot {vec {x}}=0}{displaystyle ({begin{pmatrix}0&1\1&1end{pmatrix}}-lambda cdot E)cdot {vec {x}}=0}



求特徵向量x→{displaystyle {vec {x}}}{vec  x}


x→1{displaystyle {vec {x}}_{1}}{vec  x}_{1}=(112(1+5)){displaystyle {begin{pmatrix}1\{frac {1}{2}}(1+{sqrt {5}})end{pmatrix}}}{begin{pmatrix}1\{frac  {1}{2}}(1+{sqrt  {5}})end{pmatrix}}


x→2{displaystyle {vec {x}}_{2}}{vec  x}_{2}=(112(1−5)){displaystyle {begin{pmatrix}1\{frac {1}{2}}(1-{sqrt {5}})end{pmatrix}}}{begin{pmatrix}1\{frac  {1}{2}}(1-{sqrt  {5}})end{pmatrix}}



分解首向量


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


(J1A1)=(01){displaystyle {J_{1} choose A_{1}}={begin{pmatrix}0\1end{pmatrix}}}{J_{{1}} choose A_{{1}}}={begin{pmatrix}0\1end{pmatrix}}

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



(01)=15⋅(112(1+5))−15⋅(112(1−5)){displaystyle {begin{pmatrix}0\1end{pmatrix}}={frac {1}{sqrt {5}}}cdot {begin{pmatrix}1\{frac {1}{2}}(1+{sqrt {5}})end{pmatrix}}-{frac {1}{sqrt {5}}}cdot {begin{pmatrix}1\{frac {1}{2}}(1-{sqrt {5}})end{pmatrix}}}{begin{pmatrix}0\1end{pmatrix}}={frac  {1}{{sqrt  {5}}}}cdot {begin{pmatrix}1\{frac  {1}{2}}(1+{sqrt  {5}})end{pmatrix}}-{frac  {1}{{sqrt  {5}}}}cdot {begin{pmatrix}1\{frac  {1}{2}}(1-{sqrt  {5}})end{pmatrix}} (4)


用數學歸納法證明





(Jn+1An+1)=(0111)⋅(JnAn){displaystyle {J_{n+1} choose A_{n+1}}={begin{pmatrix}0&1\1&1end{pmatrix}}cdot {J_{n} choose A_{n}}}{displaystyle {J_{n+1} choose A_{n+1}}={begin{pmatrix}0&1\1&1end{pmatrix}}cdot {J_{n} choose A_{n}}}=λ(JnAn){displaystyle lambda cdot {J_{n} choose A_{n}}}lambda cdot {J_{n} choose A_{{n}}}

可得到



(Jn+1An+1)=(0111)n⋅(J1A1)=λn⋅(J1A1){displaystyle {J_{n+1} choose A_{n+1}}={begin{pmatrix}0&1\1&1end{pmatrix}}^{n}cdot {J_{1} choose A_{1}}=lambda ^{n}cdot {J_{1} choose A_{1}}}{J_{{n+1}} choose A_{{n+1}}}={begin{pmatrix}0&1\1&1end{pmatrix}}^{n}cdot {J_{{1}} choose A_{{1}}}=lambda ^{n}cdot {J_{{1}} choose A_{{1}}} (5)


化簡矩陣方程


將(4) 代入 (5)


(Jn+1An+1)=λn⋅[15⋅(112(1+5))−15⋅(112(1−5))]{displaystyle {J_{n+1} choose A_{n+1}}=lambda ^{n}cdot left[{frac {1}{sqrt {5}}}cdot {begin{pmatrix}1\{frac {1}{2}}(1+{sqrt {5}})end{pmatrix}}-{frac {1}{sqrt {5}}}cdot {begin{pmatrix}1\{frac {1}{2}}(1-{sqrt {5}})end{pmatrix}}right]}{J_{{n+1}} choose A_{{n+1}}}=lambda ^{n}cdot left[{frac  {1}{{sqrt  {5}}}}cdot {begin{pmatrix}1\{frac  {1}{2}}(1+{sqrt  {5}})end{pmatrix}}-{frac  {1}{{sqrt  {5}}}}cdot {begin{pmatrix}1\{frac  {1}{2}}(1-{sqrt  {5}})end{pmatrix}}right]

根據3


(Jn+1An+1)=15⋅λ1n⋅(112(1+5))−15⋅λ2n⋅(112(1−5)){displaystyle {J_{n+1} choose A_{n+1}}={frac {1}{sqrt {5}}}cdot lambda _{1}^{n}cdot {begin{pmatrix}1\{frac {1}{2}}(1+{sqrt {5}})end{pmatrix}}-{frac {1}{sqrt {5}}}cdot lambda _{2}^{n}cdot {begin{pmatrix}1\{frac {1}{2}}(1-{sqrt {5}})end{pmatrix}}}{J_{{n+1}} choose A_{{n+1}}}={frac  {1}{{sqrt  {5}}}}cdot lambda _{1}^{n}cdot {begin{pmatrix}1\{frac  {1}{2}}(1+{sqrt  {5}})end{pmatrix}}-{frac  {1}{{sqrt  {5}}}}cdot lambda _{2}^{n}cdot {begin{pmatrix}1\{frac  {1}{2}}(1-{sqrt  {5}})end{pmatrix}}


求A的表達式


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


An+1=15⋅λ1n+1−15⋅λ2n+1{displaystyle A_{n+1}={frac {1}{sqrt {5}}}cdot lambda _{1}^{n+1}-{frac {1}{sqrt {5}}}cdot lambda _{2}^{n+1}}A_{{n+1}}={frac  {1}{{sqrt  {5}}}}cdot lambda _{1}^{{n+1}}-{frac  {1}{{sqrt  {5}}}}cdot lambda _{2}^{{n+1}}

An+1=15⋅1n+1−λ2n+1){displaystyle A_{n+1}={frac {1}{sqrt {5}}}cdot (lambda _{1}^{n+1}-lambda _{2}^{n+1})}A_{{n+1}}={frac  {1}{{sqrt  {5}}}}cdot (lambda _{1}^{{n+1}}-lambda _{2}^{{n+1}})


An+1=15⋅{[12(1+5)]n+1−[12(1−5)]n+1}{displaystyle A_{n+1}={frac {1}{sqrt {5}}}cdot left{left[{frac {1}{2}}left(1+{sqrt {5}}right)right]^{n+1}-left[{frac {1}{2}}(1-{sqrt {5}})right]^{n+1}right}}{displaystyle A_{n+1}={frac {1}{sqrt {5}}}cdot left{left[{frac {1}{2}}left(1+{sqrt {5}}right)right]^{n+1}-left[{frac {1}{2}}(1-{sqrt {5}})right]^{n+1}right}}(7)

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



數論解法


實際上,如果將斐波那契數列的通項公式寫成an−an−1−an−2=0{displaystyle a_{n}-a_{n-1}-a_{n-2}=0}{displaystyle a_{n}-a_{n-1}-a_{n-2}=0},即可利用解二階線性齊次遞迴關係式的方法,寫出其特徵多項式λ2−λ1=0{displaystyle lambda ^{2}-lambda -1=0}{displaystyle lambda ^{2}-lambda -1=0}(該式和表達斐波那契數列的矩陣的特徵多項式一致),然後解出λ1{displaystyle lambda _{1}}lambda _{1}=12(1+5){displaystyle {frac {1}{2}}(1+{sqrt {5}})}{frac  {1}{2}}(1+{sqrt  {5}})λ2{displaystyle lambda _{2}}lambda _{2}=12(1−5){displaystyle {frac {1}{2}}(1-{sqrt {5}})}{frac  {1}{2}}(1-{sqrt  {5}}),即有an=c1λ1n+c2λ2n{displaystyle a_{n}=c_{1}lambda _{1}^{n}+c_{2}lambda _{2}^{n}}{displaystyle a_{n}=c_{1}lambda _{1}^{n}+c_{2}lambda _{2}^{n}},其中c1,c2{displaystyle c_{1},c_{2}}{displaystyle c_{1},c_{2}}为常数。我们知道a0=0,a1=1{displaystyle a_{0}=0,a_{1}=1}{displaystyle a_{0}=0,a_{1}=1},因此{c1+c2=0c1(1+5)2+c2(1−5)2=1{displaystyle {begin{cases}c_{1}+c_{2}=0\{frac {c_{1}(1+{sqrt {5}})}{2}}+{frac {c_{2}(1-{sqrt {5}})}{2}}=1end{cases}}}{displaystyle {begin{cases}c_{1}+c_{2}=0\{frac {c_{1}(1+{sqrt {5}})}{2}}+{frac {c_{2}(1-{sqrt {5}})}{2}}=1end{cases}}},解得c1=15,c2=−15{displaystyle c_{1}={frac {1}{sqrt {5}}},c_{2}=-{frac {1}{sqrt {5}}}}{displaystyle c_{1}={frac {1}{sqrt {5}}},c_{2}=-{frac {1}{sqrt {5}}}}



組合數解法


Fn=∑i=0∞(n−ii){displaystyle F_{n}=sum _{i=0}^{infty }{binom {n-i}{i}}} F_n=sum_{i=0}^{infty} binom {n-i}{i}[1]


Fn−1+Fn=∑i=0∞(n−1−ii)+∑i=0∞(n−ii)=1+∑i=1∞(n−ii−1)+∑i=1∞(n−ii)=1+∑i=1∞(n+1−ii)=∑i=0∞(n+1−ii)=Fn+1{displaystyle F_{n-1}+F_{n}=sum _{i=0}^{infty }{binom {n-1-i}{i}}+sum _{i=0}^{infty }{binom {n-i}{i}}=1+sum _{i=1}^{infty }{binom {n-i}{i-1}}+sum _{i=1}^{infty }{binom {n-i}{i}}=1+sum _{i=1}^{infty }{binom {n+1-i}{i}}=sum _{i=0}^{infty }{binom {n+1-i}{i}}=F_{n+1}} F_{n-1}+F_n=sum_{i=0}^{infty} binom {n-1-i}{i}+sum_{i=0}^{infty} binom {n-i}{i}=1+sum_{i=1}^{infty} binom {n-i}{i-1}+sum_{i=1}^{infty} binom {n-i}{i}=1+sum_{i=1}^{infty} binom {n+1-i}{i}=sum_{i=0}^{infty} binom {n+1-i}{i}=F_{n+1}


近似值


Fn≈15an=15⋅[12(1+5)]n≈0.4472135955⋅1.618033988745n{displaystyle F_{n}approx {frac {1}{sqrt {5}}}a^{n}={frac {1}{sqrt {5}}}cdot left[{frac {1}{2}}left(1+{sqrt {5}}right)right]^{n}approx 0.4472135955cdot 1.618033988745^{n}}F_{n}approx {frac  {1}{{sqrt  {5}}}}a^{n}={frac  {1}{{sqrt  {5}}}}cdot left[{frac  {1}{2}}left(1+{sqrt  {5}}right)right]^{n}approx 0.4472135955cdot 1.618033988745^{n}


用計算機求解


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


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



和黃金分割的關係


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


fn+1fn≈a=12(1+5)=φ1.618...{displaystyle {frac {f_{n+1}}{f_{n}}}approx a={frac {1}{2}}(1+{sqrt {5}})=varphi approx 1{.}618{...}}{frac  {f_{{n+1}}}{f_{n}}}approx a={frac  {1}{2}}(1+{sqrt  {5}})=varphi approx 1{.}618{...}

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


11=121=1+1132=1+11+1153=1+11+11+1185=1+11+11+11+11{displaystyle {frac {1}{1}}=1qquad {frac {2}{1}}=1+{frac {1}{1}}qquad {frac {3}{2}}=1+{frac {1}{1+{frac {1}{1}}}}qquad {frac {5}{3}}=1+{frac {1}{1+{frac {1}{1+{frac {1}{1}}}}}}qquad {frac {8}{5}}=1+{frac {1}{1+{frac {1}{1+{frac {1}{1+{frac {1}{1}}}}}}}}}{frac  {1}{1}}=1qquad {frac  {2}{1}}=1+{frac  {1}{1}}qquad {frac  {3}{2}}=1+{frac  {1}{1+{frac  {1}{1}}}}qquad {frac  {5}{3}}=1+{frac  {1}{1+{frac  {1}{1+{frac  {1}{1}}}}}}qquad {frac  {8}{5}}=1+{frac  {1}{1+{frac  {1}{1+{frac  {1}{1+{frac  {1}{1}}}}}}}}


Fn=15[(1+52)n−(1−52)n]=φn5−(1−φ)n5{displaystyle F_{n}={frac {1}{sqrt {5}}}left[left({frac {1+{sqrt {5}}}{2}}right)^{n}-left({frac {1-{sqrt {5}}}{2}}right)^{n}right]={varphi ^{n} over {sqrt {5}}}-{(1-varphi )^{n} over {sqrt {5}}}}F_{n}={frac  {1}{{sqrt  {5}}}}left[left({frac  {1+{sqrt  {5}}}{2}}right)^{n}-left({frac  {1-{sqrt  {5}}}{2}}right)^{n}right]={varphi ^{n} over {sqrt  {5}}}-{(1-varphi )^{n} over {sqrt  {5}}}


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


φ=1+11+11+11+11+...{displaystyle varphi =1+{frac {1}{1+{frac {1}{1+{frac {1}{1+{frac {1}{1+...}}}}}}}}}varphi =1+{frac  {1}{1+{frac  {1}{1+{frac  {1}{1+{frac  {1}{1+...}}}}}}}}

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


φ=1+1+1+1+...{displaystyle varphi ={sqrt {1+{sqrt {1+{sqrt {1+{sqrt {1+...}}}}}}}}}varphi ={sqrt  {1+{sqrt  {1+{sqrt  {1+{sqrt  {1+...}}}}}}}}


和自然的關係


許多的生物構成都和斐波那契數列有正相關。例如人體從脚底至頭頂之距離和從肚臍至腳底之距趨近於limn→FnF(n−1){displaystyle lim _{nto infty }{frac {F_{n}}{F_{(n-1)}}}}lim _{{nto infty }}{frac  {F_{n}}{F_{{(n-1)}}}}
,向日葵的種子螺旋排列有99%是Fn{displaystyle F_{n}}F_n



恆等式


資料來源:[2]


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



  • Fn{displaystyle F_{n}}F_n可以表示用多個1和多個2相加令其和等於n{displaystyle n}n的方法的數目。

不失一般性,我們假設n≥1{displaystyle ngeq 1}{displaystyle ngeq 1}Fn+1{displaystyle F_{n+1}}F_{{n+1}}是計算了將1和2加到n的方法的數目。若第一個被加數是1,有Fn{displaystyle F_{n}}F_n種方法來完成對n−1{displaystyle n-1}n-1的計算;若第一個被加數是2,有Fn−1{displaystyle F_{n-1}}F_{{n-1}}來完成對n−2{displaystyle n-2}n-2的計算。因此,共有Fn+Fn−1{displaystyle F_{n}+F_{n-1}}F_{n}+F_{{n-1}}種方法來計算n的值。


  • F0+F1+F2+F3+...+Fn=Fn+2−1{displaystyle F_{0}+F_{1}+F_{2}+F_{3}+...+F_{n}=F_{n+2}-1}F_{0}+F_{1}+F_{2}+F_{3}+...+F_{n}=F_{{n+2}}-1

計算用多個1和多個2相加令其和等於n+1{displaystyle n+1}n+1的方法的數目,同時至少一個加數是2的情況。


如前所述,當n>0{displaystyle n>0}n>0,有Fn+2{displaystyle F_{n+2}}F_{{n+2}}種這樣的方法。因為當中只有一種方法不用使用2,就即1+1+...+1{displaystyle 1+1+...+1}1+1+...+1 (n+1{displaystyle n+1}n+1項),於是我們從Fn+2{displaystyle F_{n+2}}F_{{n+2}}減去1。



  1. 若第1個被加數是2,有Fn{displaystyle F_{n}}F_n種方法來計算加至n−1{displaystyle n-1}n-1的方法的數目;

  2. 若第2個被加數是2、第1個被加數是1,有Fn−1{displaystyle F_{n-1}}F_{{n-1}}種方法來計算加至n−2{displaystyle n-2}n-2的方法的數目。

  3. 重複以上動作。

  4. 若第n+1{displaystyle n+1}n+1個被加數為2,它之前的被加數均為1,就有F0{displaystyle F_{0}}{displaystyle F_{0}}種方法來計算加至0的數目。


若該數式包含2為被加數,2的首次出現位置必然在第1和n+1{displaystyle n+1}n+1的被加數之間。2在不同位置的情況都考慮到後,得出Fn+Fn−1+...+F0{displaystyle F_{n}+F_{n-1}+...+F_{0}}F_{n}+F_{{n-1}}+...+F_{0}為要求的數目。


  • F1+2F2+3F3+...+nFn=nFn+2−Fn+3+2{displaystyle F_{1}+2F_{2}+3F_{3}+...+nF_{n}=nF_{n+2}-F_{n+3}+2}F_{1}+2F_{2}+3F_{3}+...+nF_{n}=nF_{{n+2}}-F_{{n+3}}+2


  • F1+F3+F5+...+F2n−1=F2n{displaystyle F_{1}+F_{3}+F_{5}+...+F_{2n-1}=F_{2n}}F_{1}+F_{3}+F_{5}+...+F_{{2n-1}}=F_{{2n}}

  • F2+F4+F6+...+F2n=F2n+1−1{displaystyle F_{2}+F_{4}+F_{6}+...+F_{2n}=F_{2n+1}-1}F_{2}+F_{4}+F_{6}+...+F_{{2n}}=F_{{2n+1}}-1

  • F12+F22+F32+...+Fn2=FnFn+1{displaystyle {F_{1}}^{2}+{F_{2}}^{2}+{F_{3}}^{2}+...+{F_{n}}^{2}=F_{n}F_{n+1}}{F_{1}}^{2}+{F_{2}}^{2}+{F_{3}}^{2}+...+{F_{n}}^{2}=F_{n}F_{{n+1}}

  • Fn−1Fn+1−Fn2=(−1)n{displaystyle F_{n-1}F_{n+1}-{F_{n}}^{2}=(-1)^{n}}F_{{n-1}}F_{{n+1}}-{F_{n}}^{2}=(-1)^{n}



定理


資料來源:[2]


FmFn+Fm−1Fn−1=Fm+n−1FmFn+1+Fm−1Fn=Fm+n{displaystyle {begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1}\F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}end{aligned}}}{begin{aligned}{F_{m}}{F_{n}}+{F_{{m-1}}}{F_{{n-1}}}&=F_{{m+n-1}}\F_{{m}}F_{{n+1}}+F_{{m-1}}F_{n}&=F_{{m+n}}end{aligned}}

特別地,當m = n時,


F2n−1=Fn2+Fn−12F2n=(Fn−1+Fn+1)Fn=(2Fn−1+Fn)Fn{displaystyle {begin{aligned}F_{2n-1}&=F_{n}^{2}+F_{n-1}^{2}\F_{2n}&=(F_{n-1}+F_{n+1})F_{n}\&=(2F_{n-1}+F_{n})F_{n}end{aligned}}}{begin{aligned}F_{{2n-1}}&=F_{n}^{2}+F_{{n-1}}^{2}\F_{{2n}}&=(F_{{n-1}}+F_{{n+1}})F_{n}\&=(2F_{{n-1}}+F_{n})F_{n}end{aligned}}



  • Fn{displaystyle F_{n}}F_n整除Fm{displaystyle F_{m}}F_{m},若且唯若n整除m,其中n≧3。

  • gcd(Fm,Fn)=Fgcd(m,n){displaystyle gcd(F_{m},F_{n})=F_{gcd(m,n)}}gcd(F_{m},F_{n})=F_{{gcd(m,n)}}

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



gcd(Fn, Fn+1) = gcd(Fn, Fn+2) = gcd(Fn+1, Fn+2) = 1


相關的數列


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



和盧卡斯數列的關係



反費波那西數列


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


Gn+2=Gn−Gn+1{displaystyle G_{n+2}=G_{n}-G_{n+1}}G_{{n+2}}=G_{{n}}-G_{{n+1}}

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


即是F2n+1=G2n+1,F2n=−G2n{displaystyle F_{2n+1}=G_{2n+1},F_{2n}=-G_{2n}}F_{{2n+1}}=G_{{2n+1}},F_{{2n}}=-G_{{2n}}


反費波那西數列兩項之間的比會趨近=−0.618{displaystyle -{frac {1}{varphi }}=-0.618}-{frac  {1}{varphi }}=-0.618



巴都萬數列


費波那西數列可以用一個接一個的正方形來表現,巴都萬數列則是用一個接一個的等邊三角形來表現,它有Pn=Pn−2+Pn−3{displaystyle P_{n}=P_{n-2}+P_{n-3}}P_{{n}}=P_{{n-2}}+P_{{n-3}}的關係。



應用


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


y=F2x{displaystyle y=F_{2x}}y=F_{{2x}}

正是滿足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语言通项公式版


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


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 = 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语言通项公式版:


package main

import "fmt"

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

func main() {
var i int
for i = 0; i < 10; i++ {
fmt.Printf("%dt", fibonacci(i))
}
}

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];
}
}


參考文獻




  • 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. ^ 斐波那契数列与组合数的一个关系及推广. 


  2. ^ 2.02.1 李晨滔、馮勁敏. 費氏數列的性質整理 (PDF). 桃園縣立大園國際高中. 



參見


  • 齊肯多夫定理


外部連結


  • 費波那契數,孫智宏(pdf)




Popular posts from this blog

Y

Mount Tamalpais

Indian Forest Service