以斐波那契數為邊的正方形拼成的近似的黃金矩形 (1:1.618) 斐波那契数 (意大利语 :Successione di Fibonacci),又譯為菲波拿契數 、菲波那西數 、斐氏數 、黃金分割數、費氏數列 。所形成的數列 稱為斐波那契数列 (意大利语 :Successione di Fibonacci),又譯為菲波拿契數列 、菲波那西數列 、斐氏數列 、黃金分割數列、費氏數列 。這個數列是由意大利 數學家 斐波那契 在他的《算盤書》中提出。
在數學 上,斐波那契數 是以遞歸 的方法來定義:
F 0 = 0 {\displaystyle F_{0}=0} F 1 = 1 {\displaystyle F_{1}=1} F n = F n − 1 + F n − 2 {\displaystyle F_{n}=F_{n-1}+F_{n-2}} ( n ≧ 2 {\displaystyle n\geqq 2} ) 用白話文來說,就是斐波那契數列由0和1開始,之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是:
1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34 、 55 、 89 、 144 、 233 、 377 、 610 、 987……(OEIS 數列A000045 ) 特別指出 :0 不是第一項,而是第零項( F 0 {\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} 對
斐波纳契数是杨辉三角的每一条红色对角线上数字的和。 斐波纳契数也是杨辉三角形 (即帕斯卡三角形)的每一条红色对角线上数字的和。
為求得斐波那契數列的一般表達式,可以藉助線性代數的方法。高中的初等數學知識也能求出。
已知:
a 1 = 1 {\displaystyle a_{1}=1} a 2 = 1 {\displaystyle a_{2}=1} a n = a n − 1 + a n − 2 {\displaystyle a_{n}=a_{n-1}+a_{n-2}} (n≥3) 設 a n + α a n − 1 = β ( a n − 1 + α a n − 2 ) {\displaystyle a_{n}+\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})} 化簡得 a n = ( β − α ) a n − 1 + α β a n − 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 − 1 2 β = 5 + 1 2 {\displaystyle {\begin{cases}\alpha ={\dfrac {{\sqrt {5}}-1}{2}}\\\beta ={\dfrac {{\sqrt {5}}+1}{2}}\end{cases}}} 又因为有 a n + α a n − 1 = β ( a n − 1 + α a n − 2 ) {\displaystyle a_{n}+\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})} , 即 { a n + α a n − 1 } {\displaystyle \left\{a_{n}+\alpha a_{n-1}\right\}} 為等比數列。
求出數列 { a n + α a n − 1 } {\displaystyle \left\{a_{n}+\alpha a_{n-1}\right\}} [ 编辑 ] 由以上可得: a n + 1 + α a n = ( a 2 + α a 1 ) β 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}}}
變形得: a n + 1 β n + 1 + α β ⋅ a n β n = 1 β {\displaystyle {\frac {a_{n+1}}{\beta ^{n+1}}}+{\frac {\alpha }{\beta }}\cdot {\frac {a_{n}}{\beta ^{n}}}={\frac {1}{\beta }}} 。 令 b n = a n β n {\displaystyle b_{n}={\frac {a_{n}}{\beta ^{n}}}}
求數列 { b n } {\displaystyle \left\{{b_{n}}\right\}} 進而得到 { a n } {\displaystyle \left\{a_{n}\right\}} [ 编辑 ] b n + 1 + α β b n = 1 β {\displaystyle b_{n+1}+{\frac {\alpha }{\beta }}b_{n}={\frac {1}{\beta }}} 設 b n + 1 + λ = − α β ( b n + λ ) {\displaystyle b_{n+1}+\lambda =-{\frac {\alpha }{\beta }}(b_{n}+\lambda )} ,解得 λ = − 1 α + β {\displaystyle \lambda =-{\frac {1}{\alpha +\beta }}} 。 故數列 { b n + λ } {\displaystyle \left\{b_{n}+\lambda \right\}} 為等比數列 即 b n + λ = ( − α β ) n − 1 ( b 1 + λ ) {\displaystyle b_{n}+\lambda =\left(-{\frac {\alpha }{\beta }}\right)^{n-1}\left(b_{1}+\lambda \right)} 。而 b 1 = a 1 β = 1 β {\displaystyle b_{1}={\frac {a_{1}}{\beta }}={\frac {1}{\beta }}} , 故有 b n + λ = ( − α β ) n − 1 ( 1 β + λ ) {\displaystyle b_{n}+\lambda =\left(-{\frac {\alpha }{\beta }}\right)^{n-1}\left({\frac {1}{\beta }}+\lambda \right)} 又有 { α = 5 − 1 2 β = 5 + 1 2 {\displaystyle {\begin{cases}\alpha ={\dfrac {{\sqrt {5}}-1}{2}}\\\beta ={\dfrac {{\sqrt {5}}+1}{2}}\end{cases}}} 和 b n = a n β n {\displaystyle b_{n}={\frac {a_{n}}{\beta ^{n}}}} 可得 a n = 5 5 ⋅ [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) 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 {\displaystyle {a_{n}}} 表達式
a n = 5 5 ⋅ [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) 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]}
證明 F n = 1 5 [ φ n − ( 1 − φ ) n ] {\displaystyle F_{n}={\frac {1}{\sqrt {5}}}[\varphi ^{n}-(1-\varphi )^{n}]} ,其中 φ {\displaystyle \varphi } 為黃金比例 1 + 5 2 {\displaystyle {\frac {1+{\sqrt {5}}}{2}}} , n {\displaystyle n} 為任意整數 若 n {\displaystyle n} 為非負整數 當 n = 0 {\displaystyle n=0} 時, 1 5 [ φ 0 − ( 1 − φ ) 0 ] = 1 5 [ 1 − 1 ] = 0 = F 0 {\displaystyle {\frac {1}{\sqrt {5}}}[\varphi ^{0}-(1-\varphi )^{0}]={\frac {1}{\sqrt {5}}}[1-1]=0=F_{0}} ,成立 當 n = 1 {\displaystyle n=1} 時, 1 5 [ φ 1 − ( 1 − φ ) 1 ] = 1 5 [ φ − 1 + φ ] = 1 5 [ 2 φ − 1 ] = 1 5 × 5 = 1 = F 1 {\displaystyle {\frac {1}{\sqrt {5}}}[\varphi ^{1}-(1-\varphi )^{1}]={\frac {1}{\sqrt {5}}}[\varphi -1+\varphi ]={\frac {1}{\sqrt {5}}}[2\varphi -1]={\frac {1}{\sqrt {5}}}\times {\sqrt {5}}=1=F_{1}} ,成立 設當 n = k {\displaystyle n=k} 及 n = k + 1 {\displaystyle n=k+1} 時皆成立,即 F k = 1 5 [ φ k − ( 1 − φ ) k ] {\displaystyle F_{k}={\frac {1}{\sqrt {5}}}[\varphi ^{k}-(1-\varphi )^{k}]} 且 F k + 1 = 1 5 [ φ k + 1 − ( 1 − φ ) k + 1 ] {\displaystyle F_{k+1}={\frac {1}{\sqrt {5}}}[\varphi ^{k+1}-(1-\varphi )^{k+1}]} 當 n = k + 2 {\displaystyle n=k+2} 時 F k + 2 = F k + 1 + F k = 1 5 [ φ k + 1 − ( 1 − φ ) k + 1 ] + 1 5 [ φ k − ( 1 − φ ) k ] = 1 5 [ φ k + 1 + φ k − ( 1 − φ ) k + 1 − ( 1 − φ ) k ] = 1 5 { φ k ( φ + 1 ) − ( 1 − φ ) k [ ( 1 − φ ) + 1 ] } = 1 5 { φ k ( φ 2 ) − ( 1 − φ ) k [ ( 1 − φ ) 2 ] } = 1 5 { φ k + 2 − ( 1 − φ ) k + 2 } {\displaystyle {\begin{aligned}F_{k+2}&=F_{k+1}+F_{k}\\&={\frac {1}{\sqrt {5}}}[\varphi ^{k+1}-(1-\varphi )^{k+1}]+{\frac {1}{\sqrt {5}}}[\varphi ^{k}-(1-\varphi )^{k}]\\&={\frac {1}{\sqrt {5}}}[\varphi ^{k+1}+\varphi ^{k}-(1-\varphi )^{k+1}-(1-\varphi )^{k}]\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{k}({\color {brown}\varphi +1})-(1-\varphi )^{k}[{\color {green}(1-\varphi )+1}]\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{k}({\color {brown}\varphi ^{2}})-(1-\varphi )^{k}[{\color {green}(1-\varphi )^{2}}]\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{k+2}-(1-\varphi )^{k+2}\right\}\\\end{aligned}}} 亦成立 若 n {\displaystyle n} 為非正整數 當 n = 0 {\displaystyle n=0} 時,成立 當 n = − 1 {\displaystyle n=-1} 時, 1 5 [ φ − 1 − ( 1 − φ ) − 1 ] = 1 5 [ ( φ − 1 ) − ( − φ ) ] = 1 5 [ 2 φ − 1 ] = 1 5 × 5 = 1 = F − 1 {\displaystyle {\frac {1}{\sqrt {5}}}[{\color {brown}\varphi ^{-1}}-{\color {green}(1-\varphi )^{-1}}]={\frac {1}{\sqrt {5}}}[({\color {brown}\varphi -1})-({\color {green}-\varphi })]={\frac {1}{\sqrt {5}}}[2\varphi -1]={\frac {1}{\sqrt {5}}}\times {\sqrt {5}}=1=F_{-1}} ,成立 設當 n = − k {\displaystyle n=-k} 及 n = − k − 1 {\displaystyle n=-k-1} 時皆成立,即 F − k = 1 5 [ φ − k − ( 1 − φ ) − k ] {\displaystyle F_{-k}={\frac {1}{\sqrt {5}}}[\varphi ^{-k}-(1-\varphi )^{-k}]} 且 F − k − 1 = 1 5 [ φ − k − 1 − ( 1 − φ ) − k − 1 ] {\displaystyle F_{-k-1}={\frac {1}{\sqrt {5}}}[\varphi ^{-k-1}-(1-\varphi )^{-k-1}]} 當 n = − k − 2 {\displaystyle n=-k-2} 時 F − k − 2 = F − k − F − k − 1 = 1 5 [ φ − k − ( 1 − φ ) − k ] − 1 5 [ φ − k − 1 − ( 1 − φ ) − k − 1 ] = 1 5 [ φ − k − φ − k − 1 − ( 1 − φ ) − k + ( 1 − φ ) − k − 1 ] = 1 5 { φ − k − 1 ( φ − 1 ) − ( 1 − φ ) − k − 1 [ ( 1 − φ ) − 1 ] } = 1 5 { φ − k − 1 ( φ − 1 ) − ( 1 − φ ) − k − 1 [ ( 1 − φ ) − 1 ] } = 1 5 { φ − k − 2 − ( 1 − φ ) − k − 2 } {\displaystyle {\begin{aligned}F_{-k-2}&=F_{-k}-F_{-k-1}\\&={\frac {1}{\sqrt {5}}}[\varphi ^{-k}-(1-\varphi )^{-k}]-{\frac {1}{\sqrt {5}}}[\varphi ^{-k-1}-(1-\varphi )^{-k-1}]\\&={\frac {1}{\sqrt {5}}}[\varphi ^{-k}-\varphi ^{-k-1}-(1-\varphi )^{-k}+(1-\varphi )^{-k-1}]\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{-k-1}({\color {brown}\varphi -1})-(1-\varphi )^{-k-1}[{\color {green}(1-\varphi )-1}]\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{-k-1}({\color {brown}\varphi ^{-1}})-(1-\varphi )^{-k-1}[{\color {green}(1-\varphi )^{-1}}]\right\}\\&={\frac {1}{\sqrt {5}}}\left\{\varphi ^{-k-2}-(1-\varphi )^{-k-2}\right\}\\\end{aligned}}} 亦成立 因此,根據數學歸納法原理,此表達式對於任意整數 n {\displaystyle n} 皆成立
( F n + 2 F n + 1 ) = ( 1 1 1 0 ) ⋅ ( F n + 1 F n ) {\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}}}
( F n + 2 F n + 1 F n + 1 F n ) = ( 1 1 1 0 ) 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}}
設 J n {\displaystyle J_{n}} 為第 n {\displaystyle n} 個月有生育能力的兔子數量, A n {\displaystyle A_{n}} 為這一月份的兔子數量。
( J n + 1 A n + 1 ) = ( 0 1 1 1 ) ⋅ ( J n A n ) , {\displaystyle {J_{n+1} \choose A_{n+1}}={\begin{pmatrix}0&1\\1&1\end{pmatrix}}\cdot {J_{n} \choose A_{n}},} 上式表達了兩個月之間,兔子數目之間的關係。而要求的是, A n + 1 {\displaystyle A_{n+1}} 的表達式。
求矩陣的特徵值 : λ {\displaystyle \lambda } [ 编辑 ] 根据特征值的计算公式 ,我们需要算出来 | − λ 1 1 1 − λ | = 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 = 1 2 ( 1 + 5 ) {\displaystyle \lambda _{1}={\frac {1}{2}}(1+{\sqrt {5}})} 或 λ 2 = 1 2 ( 1 − 5 ) {\displaystyle \lambda _{2}={\frac {1}{2}}(1-{\sqrt {5}})} 。
將兩個特徵值代入
( ( 0 1 1 1 ) − λ ⋅ E ) ⋅ x → = 0 {\displaystyle \left({\begin{pmatrix}0&1\\1&1\end{pmatrix}}-\lambda \cdot E\right)\cdot {\vec {x}}=0} 求特徵向量 x → {\displaystyle {\vec {x}}} 得
x → 1 {\displaystyle {\vec {x}}_{1}} = ( 1 1 2 ( 1 + 5 ) ) {\displaystyle {\begin{pmatrix}1\\{\frac {1}{2}}(1+{\sqrt {5}})\end{pmatrix}}}
x → 2 {\displaystyle {\vec {x}}_{2}} = ( 1 1 2 ( 1 − 5 ) ) {\displaystyle {\begin{pmatrix}1\\{\frac {1}{2}}(1-{\sqrt {5}})\end{pmatrix}}}
第一個月的情況是兔子一對,新生0對。
( J 1 A 1 ) = ( 0 1 ) {\displaystyle {J_{1} \choose A_{1}}={\begin{pmatrix}0\\1\end{pmatrix}}} 將它分解為用特徵向量表示。
( 0 1 ) = 1 5 ⋅ ( 1 1 2 ( 1 + 5 ) ) − 1 5 ⋅ ( 1 1 2 ( 1 − 5 ) ) {\displaystyle {\begin{pmatrix}0\\1\end{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) 從
( J n + 1 A n + 1 ) = ( 0 1 1 1 ) ⋅ ( J n A n ) {\displaystyle {J_{n+1} \choose A_{n+1}}={\begin{pmatrix}0&1\\1&1\end{pmatrix}}\cdot {J_{n} \choose A_{n}}} = λ ⋅ ( J n A n ) {\displaystyle \lambda \cdot {J_{n} \choose A_{n}}} 可得到
( J n + 1 A n + 1 ) = ( 0 1 1 1 ) n ⋅ ( J 1 A 1 ) = λ n ⋅ ( J 1 A 1 ) {\displaystyle {J_{n+1} \choose A_{n+1}}={\begin{pmatrix}0&1\\1&1\end{pmatrix}}^{n}\cdot {J_{1} \choose A_{1}}=\lambda ^{n}\cdot {J_{1} \choose A_{1}}} (5) 將(4) 代入 (5)
( J n + 1 A n + 1 ) = λ n ⋅ [ 1 5 ⋅ ( 1 1 2 ( 1 + 5 ) ) − 1 5 ⋅ ( 1 1 2 ( 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]} 根據3
( J n + 1 A n + 1 ) = 1 5 ⋅ λ 1 n ⋅ ( 1 1 2 ( 1 + 5 ) ) − 1 5 ⋅ λ 2 n ⋅ ( 1 1 2 ( 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}}} 現在在6的基礎上,可以很快求出 A n + 1 {\displaystyle A_{n+1}} 的表達式,將兩個特徵值代入6中
A n + 1 = 1 5 ⋅ λ 1 n + 1 − 1 5 ⋅ λ 2 n + 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 = 1 5 ⋅ ( λ 1 n + 1 − λ 2 n + 1 ) {\displaystyle A_{n+1}={\frac {1}{\sqrt {5}}}\cdot (\lambda _{1}^{n+1}-\lambda _{2}^{n+1})} A n + 1 = 1 5 ⋅ { [ 1 2 ( 1 + 5 ) ] n + 1 − [ 1 2 ( 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\}} (7) (7)即為 A n + 1 {\displaystyle A_{n+1}} 的表達式
實際上,如果將斐波那契數列的通項公式寫成 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} (該式和表達斐波那契數列的矩陣的特徵多項式一致),然後解出 λ 1 {\displaystyle \lambda _{1}} = 1 2 ( 1 + 5 ) {\displaystyle {\frac {1}{2}}(1+{\sqrt {5}})} , λ 2 {\displaystyle \lambda _{2}} = 1 2 ( 1 − 5 ) {\displaystyle {\frac {1}{2}}(1-{\sqrt {5}})} ,即有 a n = c 1 λ 1 n + c 2 λ 2 n {\displaystyle a_{n}=c_{1}\lambda _{1}^{n}+c_{2}\lambda _{2}^{n}} ,其中 c 1 , c 2 {\displaystyle c_{1},c_{2}} 为常数。我们知道 a 0 = 0 , a 1 = 1 {\displaystyle a_{0}=0,a_{1}=1} ,因此 { c 1 + c 2 = 0 c 1 ( 1 + 5 ) 2 + c 2 ( 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}}} ,解得 c 1 = 1 5 , c 2 = − 1 5 {\displaystyle c_{1}={\frac {1}{\sqrt {5}}},c_{2}=-{\frac {1}{\sqrt {5}}}} 。
F n = ∑ i = 0 ∞ ( n − i i ) {\displaystyle F_{n}=\sum _{i=0}^{\infty }{\binom {n-i}{i}}} [ 1]
F n − 1 + F n = ∑ i = 0 ∞ ( n − 1 − i i ) + ∑ i = 0 ∞ ( n − i i ) = 1 + ∑ i = 1 ∞ ( n − i i − 1 ) + ∑ i = 1 ∞ ( n − i i ) = 1 + ∑ i = 1 ∞ ( n + 1 − i i ) = ∑ i = 0 ∞ ( n + 1 − i i ) = F n + 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}} 設 φ {\displaystyle \varphi } 為黃金比例 1 + 5 2 {\displaystyle {\frac {1+{\sqrt {5}}}{2}}} ,則有恆等式 φ n = F n − 1 + φ F n {\displaystyle \varphi ^{n}=F_{n-1}+\varphi F_{n}} 與 ( 1 − φ ) n = F n + 1 − φ F n {\displaystyle (1-\varphi )^{n}=F_{n+1}-\varphi F_{n}} ,其中 n {\displaystyle n} 為任意整數[ 註 1] ,則
φ n − ( 1 − φ ) n = ( F n − 1 + φ F n ) − ( F n + 1 − φ F n ) = ( F n − 1 − F n + 1 ) + 2 φ F n = − F n + 2 φ F n = F n ( 2 φ − 1 ) = F n × 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}}}
因此得到 F n {\displaystyle F_{n}} 的一般式:
F n = 1 5 [ φ n − ( 1 − φ ) n ] = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) 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} 為足夠大的正整數時,则
F n ≈ 1 5 φ n = 1 5 ⋅ [ 1 2 ( 1 + 5 ) ] n ≈ 0.4472135955 ⋅ 1.61803398875 n {\displaystyle F_{n}\approx {\frac {1}{\sqrt {5}}}\varphi ^{n}={\frac {1}{\sqrt {5}}}\cdot \left[{\frac {1}{2}}\left(1+{\sqrt {5}}\right)\right]^{n}\approx 0.4472135955\cdot 1.61803398875^{n}} F − n ≈ − 1 5 ( 1 − φ ) − n = − 1 5 ⋅ [ 1 2 ( 1 − 5 ) ] − n ≈ − 0.4472135955 ⋅ ( − 0.61803398875 ) − n {\displaystyle F_{-n}\approx -{\frac {1}{\sqrt {5}}}(1-\varphi )^{-n}=-{\frac {1}{\sqrt {5}}}\cdot \left[{\frac {1}{2}}\left(1-{\sqrt {5}}\right)\right]^{-n}\approx -0.4472135955\cdot (-0.61803398875)^{-n}} 可通過編程觀察斐波那契數列。分為兩類問題,一種已知數列中的某一項,求序數。第二種是已知序數,求該項的值。
可通過遞歸 遞推 的算法解決此兩個問題。 事實上當 n {\displaystyle n} 相當巨大的時候,O(n)的遞推/遞歸非常慢……這時候要用到矩陣快速幂這一技巧,可以使遞迴加速到O(logn)。
開普勒 發現數列前、後兩項之比 1 2 , 2 3 , 3 5 , 5 8 , 8 13 , 13 21 , 21 34 , ⋯ {\displaystyle {\frac {1}{2}},{\frac {2}{3}},{\frac {3}{5}},{\frac {5}{8}},{\frac {8}{13}},{\frac {13}{21}},{\frac {21}{34}},\cdots } ,也組成了一個數列,會趨近黃金分割 :
f n + 1 f n ≈ a = 1 2 ( 1 + 5 ) = φ ≈ 1 . 618 . . . {\displaystyle {\frac {f_{n+1}}{f_{n}}}\approx a={\frac {1}{2}}(1+{\sqrt {5}})=\varphi \approx 1{.}618{...}} 斐波那契數亦可以用連分數 來表示:
1 1 = 1 2 1 = 1 + 1 1 3 2 = 1 + 1 1 + 1 1 5 3 = 1 + 1 1 + 1 1 + 1 1 8 5 = 1 + 1 1 + 1 1 + 1 1 + 1 1 {\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}}}}}}}}}
F n = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] = φ n 5 − ( 1 − φ ) n 5 {\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}}}}
而黃金分割數亦可以用無限連分數表示:
φ = 1 + 1 1 + 1 1 + 1 1 + 1 1 + . . . {\displaystyle \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+...}}}}}}}}} 春黄菊 的頭狀花序 上,小花呈螺旋狀排列,從不同方向可以數出21(深藍)和13(淺藍)條旋臂,為相鄰的斐氏數。類似的螺旋狀排列見於多種植物。 斐氏數列見於不同的生物學現象[ 2] ,如樹的分枝、葉在枝條上的排列 、菠蘿聚花果 上小單果的排列、[ 3] 雅枝竹 的花蕾、正在舒展的蕨葉、松毬 的鱗的排列[ 4] 、蜜蜂的家族樹[ 5] [ 6] 。开普勒 曾指出斐氏數列存在於自然界,並以此解釋某些花的五邊形形態(與黄金分割率 相關)。法國菊 的「瓣」(舌狀花)數通常為斐氏數。1830年,K. F. Schimper和A. Braun發現植物的旋生葉序中,連續兩塊葉之間轉過的角度與周角之比,約成整數比時,常出現斐氏數[ 9] ,如 2 / 5 {\displaystyle 2/5} 或 5 / 13 {\displaystyle 5/13} [ 10] 。
資料來源: [ 11]
證明以下的恆等式有很多方法。以下會用組合論述 來證明。
F n {\displaystyle F_{n}} 可以表示用多個1和多個2相加令其和等於 n {\displaystyle n} 的方法的數目。 不失一般性 ,我們假設 n ≥ 1 {\displaystyle n\geq 1} , F n + 1 {\displaystyle F_{n+1}} 是計算了將1和2加到n的方法的數目。若第一個被加數是1,有 F n {\displaystyle F_{n}} 種方法來完成對 n − 1 {\displaystyle n-1} 的計算;若第一個被加數是2,有 F n − 1 {\displaystyle F_{n-1}} 來完成對 n − 2 {\displaystyle n-2} 的計算。因此,共有 F n + F n − 1 {\displaystyle F_{n}+F_{n-1}} 種方法來計算n的值。
F 0 + F 1 + F 2 + F 3 + . . . + F n = F n + 2 − 1 {\displaystyle F_{0}+F_{1}+F_{2}+F_{3}+...+F_{n}=F_{n+2}-1} 計算用多個1和多個2相加令其和等於 n + 1 {\displaystyle n+1} 的方法的數目,同時至少一個加數是2的情況。
如前所述,當 n > 0 {\displaystyle n>0} ,有 F n + 2 {\displaystyle F_{n+2}} 種這樣的方法。因為當中只有一種方法不用使用2,就即 1 + 1 + . . . + 1 {\displaystyle 1+1+...+1} ( n + 1 {\displaystyle n+1} 項),於是我們從 F n + 2 {\displaystyle F_{n+2}} 減去1。
若第1個被加數是2,有 F n {\displaystyle F_{n}} 種方法來計算加至 n − 1 {\displaystyle n-1} 的方法的數目; 若第2個被加數是2、第1個被加數是1,有 F n − 1 {\displaystyle F_{n-1}} 種方法來計算加至 n − 2 {\displaystyle n-2} 的方法的數目。 重複以上動作。 若第 n + 1 {\displaystyle n+1} 個被加數為2,它之前的被加數均為1,就有 F 0 {\displaystyle F_{0}} 種方法來計算加至0的數目。 若該數式包含2為被加數,2的首次出現位置必然在第1和 n + 1 {\displaystyle n+1} 的被加數之間。2在不同位置的情況都考慮到後,得出 F n + F n − 1 + . . . + F 0 {\displaystyle F_{n}+F_{n-1}+...+F_{0}} 為要求的數目。
F 1 + 2 F 2 + 3 F 3 + . . . + n F n = n F n + 2 − F n + 3 + 2 {\displaystyle F_{1}+2F_{2}+3F_{3}+...+nF_{n}=nF_{n+2}-F_{n+3}+2} F 1 + F 3 + F 5 + . . . + F 2 n − 1 = F 2 n {\displaystyle F_{1}+F_{3}+F_{5}+...+F_{2n-1}=F_{2n}} F 2 + F 4 + F 6 + . . . + F 2 n = F 2 n + 1 − 1 {\displaystyle F_{2}+F_{4}+F_{6}+...+F_{2n}=F_{2n+1}-1} F 1 2 + F 2 2 + F 3 2 + . . . + F n 2 = F n F n + 1 {\displaystyle {F_{1}}^{2}+{F_{2}}^{2}+{F_{3}}^{2}+...+{F_{n}}^{2}=F_{n}F_{n+1}} F n F m − k − F m F n − k = ( − 1 ) n − k F m − n F k {\displaystyle F_{n}F_{m-k}-F_{m}F_{n-k}=(-1)^{n-k}F_{m-n}F_{k}} ,其中 m , n , k {\displaystyle m,n,k} 與 F {\displaystyle F} 的序數皆不限於正整數。[ 註 2] 特別地,當 n = m − k {\displaystyle n=m-k} 時, F n 2 − F n + k F n − k = ( − 1 ) n − k F k 2 {\displaystyle {F_{n}}^{2}-F_{n+k}F_{n-k}=(-1)^{n-k}{F_{k}}^{2}} 更特別地,當 k = 1 {\displaystyle k=1} 或 k = − 1 {\displaystyle k=-1} 時,對於數列連續三項,有 F n 2 − F n − 1 F n + 1 = ( − 1 ) n − 1 {\displaystyle {F_{n}}^{2}-F_{n-1}F_{n+1}=(-1)^{n-1}} 另一方面,當 ( m , n , k ) = ( n + 1 , n , − 2 ) {\displaystyle (m,n,k)=(n+1,n,-2)} 時,對於數列連續四項,有 F n F n + 3 − F n + 1 F n + 2 = ( − 1 ) n + 1 {\displaystyle F_{n}F_{n+3}-F_{n+1}F_{n+2}=(-1)^{n+1}} [ 註 3] φ n = F n − 1 + φ F n {\displaystyle \varphi ^{n}=F_{n-1}+\varphi F_{n}} 且 ( 1 − φ ) n = F n + 1 − φ F n {\displaystyle (1-\varphi )^{n}=F_{n+1}-\varphi F_{n}} ,其中 φ {\displaystyle \varphi } 為黃金比例 1 + 5 2 {\displaystyle {\frac {1+{\sqrt {5}}}{2}}} , n {\displaystyle n} 為任意整數[ 註 1] 藉由上述公式,又可推得以下恆等式[ 註 4] : F n {\displaystyle F_{n}} 整除 F m {\displaystyle F_{m}} ,若且唯若 n {\displaystyle n} 整除 m {\displaystyle m} ,其中 n ≧ 3 {\displaystyle n\geqq 3} 。 gcd ( F m , F n ) = F gcd ( m , n ) {\displaystyle \gcd(F_{m},F_{n})=F_{\gcd(m,n)}} 任意連續三個菲波那契數兩兩互質 ,亦即,對於每一個 n {\displaystyle n} , g c d ( F n , F n + 1 ) = g c d ( F n , F n + 2 ) = g c d ( F n + 1 , F n + 2 ) = 1 {\displaystyle \mathrm {gcd} (F_{n},F_{n+1})=\mathrm {gcd} (F_{n},F_{n+2})=\mathrm {gcd} (F_{n+1},F_{n+2})=1} 在斐波那契數列中,有質數 :[ 12] 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……
截至2015年,已知最大的斐波那契質數是第104911個斐波那契數,一共有21925個十進制位。不过,人们仍不知道是不是有无限个斐波那契质数。[ 13]
如§ 公因數和整除關係 所述, F k n {\displaystyle F_{kn}} 總能被 F n {\displaystyle F_{n}} 整除,故除 F 4 = 3 {\displaystyle F_{4}=3} 之外,任何斐氏質數的下標必同為質數。由於存在任意長 的一列連續合数 ,斐氏數列中亦能找到連續任意多項全為合數。
大於 F 6 = 8 {\displaystyle F_{6}=8} 的斐氏數,必不等於質數加一或減一。[ 14]
斐波那契数列中,只有3個平方數 :0 、1 、144 。[ 15] [ 16] 2001年,派特·奧蒂洛 證明衹有有限多個斐氏數是完全冪。[ 17] 2006年,Y. Bugeaud、M. Mignotte、S. Siksek三人證明此種冪僅得0、1、8、144。[ 18]
1、3、21、55為僅有的斐氏三角形數 。Vern Hoggatt 曾猜想此結論,後來由罗明證明。[ 19]
斐波那契數不能為完全数 。[ 20] 推而廣之,除1之外,其他斐氏數皆非多重完全數 [ 21] ,任兩個斐氏數之比亦不能是完全數[ 22] 。
斐波那契數列各項模 n {\displaystyle n} 的餘數構成週期數列 ,其最小正週期稱為皮萨诺周期 [ 23] ,至多為 6 n {\displaystyle 6n} [ 24] 。皮薩諾週期對不同 n {\displaystyle n} 值的通項公式仍是未解問題,其中一步需要求出某個整數(同餘意義下)或二次有限域 元素的乘法階數 。不過,對固定的 n {\displaystyle n} ,求解模 n {\displaystyle n} 的皮薩諾週期是週期檢測 問題的特例。
斐波那西數列是斐波那西n步數列 步數為2的特殊情況,也和盧卡斯數 列有關。
F n L n = F 2 n {\displaystyle F_{n}L_{n}=F_{2n}} 反費波那西數列的遞歸公式如下:
G n + 2 = G n − G n + 1 {\displaystyle G_{n+2}=G_{n}-G_{n+1}} 如果它以1,-1開始,之後的數是:1,-1,2,-3,5,-8, ...
即是 F 2 n + 1 = G 2 n + 1 = F − ( 2 n + 1 ) , F 2 n = − G 2 n = − F − 2 n {\displaystyle F_{2n+1}=G_{2n+1}=F_{-(2n+1)},F_{2n}=-G_{2n}=-F_{-2n}} ,
亦可寫成 F m = ( − 1 ) m + 1 G m = ( − 1 ) m + 1 F − 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} 。
證明 F m = ( − 1 ) m + 1 F − m {\displaystyle F_{m}=(-1)^{m+1}F_{-m}} ,其中 m {\displaystyle m} 是非負整數
以 φ {\displaystyle \varphi } 表示黃金分割數 1 + 5 2 {\displaystyle {\frac {1+{\sqrt {5}}}{2}}} ,則有 φ ( 1 − φ ) = − 1 {\displaystyle \varphi (1-\varphi )=-1} 故 ( − 1 ) m = [ φ ( 1 − φ ) ] m = φ m ( 1 − φ ) m {\displaystyle (-1)^{m}=[\varphi (1-\varphi )]^{m}=\varphi ^{m}(1-\varphi )^{m}} ,因此 ( − 1 ) m + 1 F − m = ( − 1 ) m + 1 × 1 5 [ φ − m − ( 1 − φ ) − m ] = ( − 1 ) × ( − 1 ) m × 1 5 [ φ − m − ( 1 − φ ) − m ] = ( − 1 ) × φ m ( 1 − φ ) m × 1 5 [ φ − m − ( 1 − φ ) − m ] = ( − 1 ) × 1 5 [ φ − m + m ( 1 − φ ) m − ( 1 − φ ) − m + m φ m ] = ( − 1 ) × 1 5 [ ( 1 − φ ) m − φ m ] = 1 5 [ φ m − ( 1 − φ ) m ] = F m {\displaystyle {\begin{aligned}(-1)^{m+1}F_{-m}&=(-1)^{m+1}\times {\frac {1}{\sqrt {5}}}[\varphi ^{-m}-(1-\varphi )^{-m}]\\&=(-1)\times {\color {brown}(-1)^{m}}\times {\frac {1}{\sqrt {5}}}[\varphi ^{-m}-(1-\varphi )^{-m}]\\&=(-1)\times {\color {brown}\varphi ^{m}(1-\varphi )^{m}}\times {\frac {1}{\sqrt {5}}}[\varphi ^{-m}-(1-\varphi )^{-m}]\\&=(-1)\times {\frac {1}{\sqrt {5}}}[\varphi ^{-m+m}(1-\varphi )^{m}-(1-\varphi )^{-m+m}\varphi ^{m}]\\&=(-1)\times {\frac {1}{\sqrt {5}}}[(1-\varphi )^{m}-\varphi ^{m}]\\&={\frac {1}{\sqrt {5}}}[\varphi ^{m}-(1-\varphi )^{m}]\\&=F_{m}\\\end{aligned}}} 費波那西數列可以用一個接一個的正方形來表現,巴都萬數列 則是用一個接一個的等邊三角形來表現,它有 P n = P n − 2 + P n − 3 {\displaystyle P_{n}=P_{n-2}+P_{n-3}} 的關係。
佩爾數列 的遞歸公式為 P n = 2 P n − 1 + P n − 2 {\displaystyle P_{n}=2P_{n-1}+P_{n-2}} ,前幾項為0,1,2,5,12,29,70,169,408,...
1970年,尤裏·馬季亞謝維奇 指出了偶角標的斐波那契函數
y = F 2 x {\displaystyle y=F_{2x}} 正是滿足Julia Robison假設的丟番圖函數 ,因而證明了希爾伯特第十問題 是不可解的。
高為6的斐波那契樹。平衡因子 以綠色標記,節點的高度則為紅色。最左一條路徑上的鍵值全為斐氏數。
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皮科夫.數學之戀.湖南科技出版社. ^ 斐波那契数列与组合数的一个关系及推广 . [2014-01-04 ] . (原始内容存档 于2019-05-02). ^ Douady, S; Couder, Y. Phyllotaxis as a Dynamical Self Organizing Process (PDF) . Journal of Theoretical Biology. 1996, 178 (3): 255–74. doi:10.1006/jtbi.1996.0026 . (原始内容 (PDF) 存档于2006-05-26). ^ Jones, Judy; Wilson, William. Science. An Incomplete Education . Ballantine Books. 2006: 544 . ISBN 978-0-7394-7582-9 . ^ Brousseau, A. Fibonacci Statistics in Conifers. Fibonacci Quarterly . 1969, (7): 525–32. ^ Marks for the da Vinci Code: B– , Maths (Computer Science For Fun: CS4FN), [2022-10-30 ] , (原始内容存档 于2009-05-31) ^ Scott, T.C.; Marketos, P., On the Origin of the Fibonacci Sequence (PDF) , MacTutor History of Mathematics archive , University of St Andrews, 2014-03 [2022-10-30 ] , (原始内容存档 (PDF) 于2019-09-18) ^ Varenne, Franck. Formaliser le vivant - Lois, Théories, Modèles . Hermann. 2010-11-16: 28 [2022-10-30 ] . ISBN 9782705678128 . (原始内容存档 于2022-10-30). ^ The Secret of the Fibonacci Sequence in Trees . 美國自然史博物館 . 2011 [2019-02-04 ] . (原始内容存档 于2013-05-04). ^ 11.0 11.1 11.2 李晨滔、馮勁敏. 費氏數列的性質整理 (PDF) . 桃園縣立大園國際高中. [2018-01-28 ] . (原始内容存档 (PDF) 于2019-06-25). ^ Sloane, N.J.A. (编). Sequence A005478 . The On-Line Encyclopedia of Integer Sequences . OEIS Foundation. ^ Weisstein, Eric W. (编). Fibonacci Prime . at MathWorld --A Wolfram Web Resource. Wolfram Research, Inc. (英语) . ^ Honsberger, Ross. Mathematical Gems III. AMS Dolciani Mathematical Expositions. 1985, (9): 133. ISBN 978-0-88385-318-4 . ^ JOHN H. E. COHN. Square Fibonacci Numbers, Etc. . Bedford College, University of London, London, N.W.1. [2019-05-12 ] . (原始内容 存档于2012-06-30). Theorem 3. If Fn = x2 , then n = 0, ±1, 2 or 12. ^ Cohn, J. H. E., On square Fibonacci numbers, The Journal of the London Mathematical Society, 1964, 39 : 537–540, MR 0163867 , doi:10.1112/jlms/s1-39.1.537 ^ Pethő, Attila. Diophantine properties of linear recursive sequences II. Acta Mathematica Academiae Paedagogicae Nyíregyháziensis. 2001, 17 : 81–96. MR 1887650 . ^ Bugeaud, Y; Mignotte, M; Siksek, S. Classical and modular approaches to exponential Diophantine equations. I. Fibonacci and Lucas perfect powers. Ann. Math. 2006, 2 (163): 969–1018. Bibcode:2004math......3046B . MR 2215137 . S2CID 10266596 . arXiv:math/0403046 . doi:10.4007/annals.2006.163.969 . ^ Luo, Ming. On triangular Fibonacci numbers (PDF) . Fibonacci Quart. 1989, 27 (2): 98–108 [2022-10-29 ] . MR 0995557 . (原始内容存档 (PDF) 于2022-10-29). ^ Luca, Florian. Perfect Fibonacci and Lucas numbers. Rendiconti del Circolo Matematico di Palermo. 2000, 49 (2): 313–18. ISSN 1973-4409 . MR 1765401 . S2CID 121789033 . doi:10.1007/BF02904236 . ^ Broughan, Kevin A.; González, Marcos J.; Lewis, Ryan H.; Luca, Florian; Mejía Huguet, V. Janitzio; Togbé, Alain. There are no multiply-perfect Fibonacci numbers . Integers. 2011, 11a : A7 [2022-10-29 ] . MR 2988067 . (原始内容存档 于2022-01-23). ^ Luca, Florian; Mejía Huguet, V. Janitzio. On Perfect numbers which are ratios of two Fibonacci numbers . Annales Mathematicae at Informaticae. 2010, 37 : 107–24. ISSN 1787-6117 . MR 2753031 . ^ Sloane, N.J.A. (编). Sequence A001175 . The On-Line Encyclopedia of Integer Sequences . OEIS Foundation. ^ Freyd, Peter; Brown, Kevin S. Problems and Solutions: Solutions: E3410. The American Mathematical Monthly. 1993, 99 (3): 278–79. JSTOR 2325076 . doi:10.2307/2325076 . ^ Knuth, Donald E . The Art of Computer Programming. 1: Fundamental Algorithms 3rd. Addison–Wesley. 1997: 343. ISBN 978-0-201-89683-1 . ^ Adelson-Velsky, Georgy; Landis, Evgenii. An algorithm for the organization of information. Proceedings of the USSR Academy of Sciences . 1962, 146 : 263–266 (俄语) . Myron J. Ricci 的英文翻譯 (页面存档备份 ,存于互联网档案馆 )載於 Soviet Mathematics - Doklady , 3:1259–1263, 1962.