斐波那契数

斐波那契数（意大利语：Numero di Fibonacci），又譯為菲波拿契數、菲波那西數、斐氏數、黃金分割數、費氏數列。所形成的數列稱為斐波那契数列（意大利语：Successione di Fibonacci），又譯為菲波拿契數列、菲波那西數列、斐氏數列、黃金分割數列、費氏數列。這個數列是由意大利數學家斐波那契在他的《算盤書》中提出。
在數學上，斐波那契數是以遞歸的方法來定義：
用白話文來說，就是斐波那契數列由0和1開始，之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是：
特別指出：0不是第一項，而是第零項（F0{\displaystyle F_{0}}）。
公元1150年印度數學家Gopala和金月在研究箱子包裝物件長宽剛好為1和2的可行方法數目時，首先描述這個數列。在西方，最先研究這個數列的人是比薩的李奧納多（意大利人斐波那契Leonardo Fibonacci, 1175－1250），他描述兔子生長的數目時用上了這數列：
假設在n{\displaystyle n}月有兔子總共a{\displaystyle a}對，n+1{\displaystyle n+1}月總共有b{\displaystyle b}對。在n+2{\displaystyle n+2}月必定總共有a+b{\displaystyle a+b}對：因為在n+2{\displaystyle n+2}月的時候，前一月（n+1{\displaystyle n+1}月）的b{\displaystyle b}對兔子可以存留至第n+2{\displaystyle n+2}月（在當月屬於新誕生的兔子尚不能生育）。而新生育出的兔子對數等於所有在n{\displaystyle n}月就已存在的a{\displaystyle a}對
斐波纳契数也是杨辉三角形（即帕斯卡三角形）的每一条红色对角线上数字的和。
為求得斐波那契數列的一般表達式，可以藉助線性代數的方法。高中的初等數學知識也能求出。
已知：
設an+αan−1=β(an−1+αan−2){\displaystyle 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}}比較係數可得：{β−α=1αβ=1{\displaystyle {\begin{cases}\beta -\alpha =1\\\alpha \beta =1\end{cases}}}不妨設β>0,α>0{\displaystyle \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}}}又因为有an+αan−1=β(an−1+αan−2){\displaystyle 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\}}為等比數列。
由以上可得：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}}}
變形得：an+1βn+1+αβ⋅anβn=1β{\displaystyle {\frac {a_{n+1}}{\beta ^{n+1}}}+{\frac {\alpha }{\beta }}\cdot {\frac {a_{n}}{\beta ^{n}}}={\frac {1}{\beta }}}。
令bn=anβn{\displaystyle b_{n}={\frac {a_{n}}{\beta ^{n}}}}
bn+1+αβbn=1β{\displaystyle 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 )}，解得λ=−1α+β{\displaystyle \lambda =-{\frac {1}{\alpha +\beta }}}。
故數列{bn+λ}{\displaystyle \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)}。而b1=a1β=1β{\displaystyle 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)}又有{α=5−12β=5+12{\displaystyle {\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}}}}可得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]}
得出an{\displaystyle {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]}
因此，根據數學歸納法原理，此表達式對於任意整數n{\displaystyle n}皆成立
(Fn+2Fn+1)=(1110)⋅(Fn+1Fn){\displaystyle {\begin{pmatrix}F_{n+2}\\F_{n+1}\end{pmatrix}}={\begin{pmatrix}1&1\\1&0\end{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&0\end{pmatrix}}^{n+1}}
設Jn{\displaystyle J_{n}}為第n{\displaystyle n}個月有生育能力的兔子數量，An{\displaystyle A_{n}}為這一月份的兔子數量。
上式表達了兩個月之間，兔子數目之間的關係。而要求的是，An+1{\displaystyle A_{n+1}}的表達式。
根据特征值的计算公式，我们需要算出来|−λ111−λ|=0{\displaystyle {\begin{vmatrix}-\lambda &1\\1&1-\lambda \\\end{vmatrix}}=0}所对应的解。
展开行列式有：−λ(1−λ)−1×1=λ2−λ−1{\displaystyle -\lambda (1-\lambda )-1\times 1=\lambda ^{2}-\lambda -1}。
故當行列式的值為 0，解得λ1=12(1+5){\displaystyle \lambda _{1}={\frac {1}{2}}(1+{\sqrt {5}})}或λ2=12(1−5){\displaystyle \lambda _{2}={\frac {1}{2}}(1-{\sqrt {5}})}。
將兩個特徵值代入
求特徵向量x→{\displaystyle {\vec {x}}}得
x→1{\displaystyle {\vec {x}}_{1}}=(112(1+5)){\displaystyle {\begin{pmatrix}1\\{\frac {1}{2}}(1+{\sqrt {5}})\end{pmatrix}}}
x→2{\displaystyle {\vec {x}}_{2}}=(112(1−5)){\displaystyle {\begin{pmatrix}1\\{\frac {1}{2}}(1-{\sqrt {5}})\end{pmatrix}}}
第一個月的情況是兔子一對，新生0對。
將它分解為用特徵向量表示。
從
可得到
將（4） 代入 （5）
根據3
現在在6的基礎上，可以很快求出An+1{\displaystyle A_{n+1}}的表達式，將兩個特徵值代入6中
（7）即為An+1{\displaystyle A_{n+1}}的表達式
實際上，如果將斐波那契數列的通項公式寫成an−an−1−an−2=0{\displaystyle a_{n}-a_{n-1}-a_{n-2}=0}，即可利用解二階線性齊次遞迴關係式的方法，寫出其特徵多項式λ2−λ−1=0{\displaystyle \lambda ^{2}-\lambda -1=0}（該式和表達斐波那契數列的矩陣的特徵多項式一致），然後解出λ1{\displaystyle \lambda _{1}}=12(1+5){\displaystyle {\frac {1}{2}}(1+{\sqrt {5}})}，λ2{\displaystyle \lambda _{2}}=12(1−5){\displaystyle {\frac {1}{2}}(1-{\sqrt {5}})}，即有an=c1λ1n+c2λ2n{\displaystyle a_{n}=c_{1}\lambda _{1}^{n}+c_{2}\lambda _{2}^{n}}，其中c1,c2{\displaystyle c_{1},c_{2}}为常数。我们知道a0=0,a1=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}}=1\end{cases}}}，解得c1=15,c2=−15{\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}}}
設φ{\displaystyle \varphi }為黃金比例1+52{\displaystyle {\frac {1+{\sqrt {5}}}{2}}}，則有恆等式φn=Fn−1+φFn{\displaystyle \varphi ^{n}=F_{n-1}+\varphi F_{n}}與(1−φ)n=Fn+1−φFn{\displaystyle (1-\varphi )^{n}=F_{n+1}-\varphi F_{n}}，其中n{\displaystyle n}為任意整數，則
φn−(1−φ)n=(Fn−1+φFn)−(Fn+1−φFn)=(Fn−1−Fn+1)+2φFn=−Fn+2φFn=Fn(2φ−1)=Fn×5{\displaystyle {\begin{aligned}\varphi ^{n}-(1-\varphi )^{n}&=(F_{n-1}+\varphi F_{n})-(F_{n+1}-\varphi F_{n})\\&=(F_{n-1}-F_{n+1})+2\varphi F_{n}\\&=-F_{n}+2\varphi F_{n}\\&=F_{n}(2\varphi -1)\\&=F_{n}\times {\sqrt {5}}\\\end{aligned}}}
因此得到Fn{\displaystyle F_{n}}的一般式：
Fn=15[φn−(1−φ)n]=15[(1+52)n−(1−52)n]{\displaystyle {\begin{aligned}F_{n}&={\frac {1}{\sqrt {5}}}[\varphi ^{n}-(1-\varphi )^{n}]\\&={\frac {1}{\sqrt {5}}}\left[({\frac {1+{\sqrt {5}}}{2}})^{n}-({\frac {1-{\sqrt {5}}}{2}})^{n}\right]\\\end{aligned}}}
此一般式對任意整數n{\displaystyle n}成立
當n{\displaystyle n}為足夠大的正整數時，则
可通過編程觀察斐波那契數列。分為兩類問題，一種已知數列中的某一項，求序數。第二種是已知序數，求該項的值。
可通過遞歸遞推的算法解決此兩個問題。
事實上當n{\displaystyle n}相當巨大的時候，O（n）的遞推/遞歸非常慢……這時候要用到矩陣快速幂這一技巧，可以使遞迴加速到O(logn)。
開普勒發現數列前、後兩項之比12,23,35,58,813,1321,2134,⋯{\displaystyle {\frac {1}{2}},{\frac {2}{3}},{\frac {3}{5}},{\frac {5}{8}},{\frac {8}{13}},{\frac {13}{21}},{\frac {21}{34}},\cdots }，也組成了一個數列，會趨近黃金分割：
斐波那契數亦可以用連分數來表示：
11=121=1+1132=1+11+1153=1+11+11+1185=1+11+11+11+11{\displaystyle {\frac {1}{1}}=1\qquad {\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}}}}
而黃金分割數亦可以用無限連分數表示：
而黃金分割數也可以用無限多重根號表示：
斐氏數列見於不同的生物學現象，如樹的分枝、葉在枝條上的排列、菠蘿聚花果上小單果的排列、雅枝竹的花蕾、正在舒展的蕨葉、松毬的鱗的排列、蜜蜂的家族樹。开普勒曾指出斐氏數列存在於自然界，並以此解釋某些花的五邊形形態（與黄金分割率相關）。法國菊的「瓣」（舌狀花）數通常為斐氏數。1830年，K. F. Schimper和A. Braun發現植物的旋生葉序中，連續兩塊葉之間轉過的角度與周角之比，約成整數比時，常出現斐氏數，如2/5{\displaystyle 2/5}或5/13{\displaystyle 5/13}。
資料來源：
證明以下的恆等式有很多方法。以下會用組合論述來證明。
不失一般性，我們假設n≥1{\displaystyle n\geq 1}，Fn+1{\displaystyle F_{n+1}}是計算了將1和2加到n的方法的數目。若第一個被加數是1，有Fn{\displaystyle F_{n}}種方法來完成對n−1{\displaystyle n-1}的計算；若第一個被加數是2，有Fn−1{\displaystyle F_{n-1}}來完成對n−2{\displaystyle n-2}的計算。因此，共有Fn+Fn−1{\displaystyle F_{n}+F_{n-1}}種方法來計算n的值。
計算用多個1和多個2相加令其和等於n+1{\displaystyle n+1}的方法的數目，同時至少一個加數是2的情況。
如前所述，當n>0{\displaystyle n>0}，有Fn+2{\displaystyle F_{n+2}}種這樣的方法。因為當中只有一種方法不用使用2，就即1+1+...+1{\displaystyle 1+1+...+1}（n+1{\displaystyle n+1}項），於是我們從Fn+2{\displaystyle F_{n+2}}減去1。
若該數式包含2為被加數，2的首次出現位置必然在第1和n+1{\displaystyle n+1}的被加數之間。2在不同位置的情況都考慮到後，得出Fn+Fn−1+...+F0{\displaystyle F_{n}+F_{n-1}+...+F_{0}}為要求的數目。
在斐波那契數列中，有質數：2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……
截至2015年，已知最大的斐波那契質數是第104911個斐波那契數，一共有21925個十進制位。不过，人们仍不知道是不是有无限个斐波那契质数。
如§ 公因數和整除關係所述，Fkn{\displaystyle F_{kn}}總能被Fn{\displaystyle F_{n}}整除，故除F4=3{\displaystyle F_{4}=3}之外，任何斐氏質數的下標必同為質數。由於存在任意長（英语：Arbitrarily large）的一列連續合数，斐氏數列中亦能找到連續任意多項全為合數。
大於F6=8{\displaystyle F_{6}=8}的斐氏數，必不等於質數加一或減一。
斐波那契数列中，只有3個平方數：0、1、144。2001年，派特·奧蒂洛（匈牙利语：Pethő Attila）證明，斐氏數中的次方數衹有有限多個。2006年，Y. Bugeaud、M. Mignotte、S. Siksek三人證明，斐波那契数中的次方數只有0、1、8、144。
1、3、21、55為僅有的斐氏三角形數。Vern Hoggatt（英语：Verner Emil Hoggatt Jr.）曾猜想此結論，後來由罗明證明。
斐波那契數不能為完全数。推而廣之，除1之外，其他斐氏數皆非多重完全數，任兩個斐氏數之比亦不能是完全數。
斐波那契數列各項模n{\displaystyle n}的餘數構成週期數列，其最小正週期稱為皮萨诺周期，至多為6n{\displaystyle 6n}。皮薩諾週期對不同n{\displaystyle n}值的通項公式仍是未解問題，其中一步需要求出某個整數（同餘意義下）或二次有限域元素的乘法階數（英语：multiplicative order）。不過，對固定的n{\displaystyle n}，求解模n{\displaystyle n}的皮薩諾週期是週期檢測（英语：cycle detection）問題的特例。
斐波那西數列是斐波那西n步數列步數為2的特殊情況，也和盧卡斯數列有關。
反費波那西數列的遞歸公式如下：
如果它以1,-1開始，之後的數是：1,-1,2,-3,5,-8, ...
即是F2n+1=G2n+1=F−(2n+1),F2n=−G2n=−F−2n{\displaystyle F_{2n+1}=G_{2n+1}=F_{-(2n+1)},F_{2n}=-G_{2n}=-F_{-2n}}，
亦可寫成Fm=(−1)m+1Gm=(−1)m+1F−m{\displaystyle F_{m}=(-1)^{m+1}G_{m}=(-1)^{m+1}F_{-m}}，其中m{\displaystyle m}是非負整數。
反費波那西數列兩項之間的比會趨近−1φ≈−0.618{\displaystyle -{\frac {1}{\varphi }}\approx -0.618}。
證明Fm=(−1)m+1F−m{\displaystyle F_{m}=(-1)^{m+1}F_{-m}}，其中m{\displaystyle m}是非負整數
費波那西數列可以用一個接一個的正方形來表現，巴都萬數列則是用一個接一個的等邊三角形來表現，它有Pn=Pn−2+Pn−3{\displaystyle P_{n}=P_{n-2}+P_{n-3}}的關係。
佩爾數列的遞歸公式為Pn=2Pn−1+Pn−2{\displaystyle P_{n}=2P_{n-1}+P_{n-2}}，前幾項為0,1,2,5,12,29,70,169,408,...
1970年，尤裏·馬季亞謝維奇指出了偶角標的斐波那契函數
正是滿足Julia Robison假設的丟番圖函數，因而證明了希爾伯特第十問題是不可解的。