以斐波那契數為邊的正方形拼成的近似的黃金矩形 (1:1.618) 在數學 上,斐波那契數 是以遞歸 的方法來定義:
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開始,之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是:
特別指出 :0 不是第一項,而是第零項。
起源
表達式
為求得斐波那契數列的一般表達式,可以藉助線性代數的方法。高中的初等數學知識也能求出。
初等代數解法 已知
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}}} 求A的表達式 現在在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}}}
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} 為任意整數,則
φ 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+...}}}}}}}}} 和自然的關係
恆等式
資料來源:
證明以下的恆等式有很多方法。以下會用組合論述來證明。
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} 的序數皆不限於正整數。 特別地,當 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}} φ 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} 為任意整數 數論性質
公因數和整除關係 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} 斐波那契质数 在斐波那契數列中,有質數 : 2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……
截至2015年,已知最大的斐波那契質數是第104911個斐波那契數,一共有21925個十進制位。不过,人们仍不知道是不是有无限个斐波那契质数。
如§ 公因數和整除關係 所述, 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} 的斐氏數,必不等於質數加一或減一。
與其他數列的交集 斐波那契数列中,只有3個平方數 :0 、1 、144 。2001年,派特·奧蒂洛 證明衹有有限多個斐氏數是完全冪。2006年,Y. Bugeaud、M. Mignotte、S. Siksek三人證明此種冪僅得0、1、8、144。
1、3、21、55為僅有的斐氏三角形數 。Vern Hoggatt 曾猜想此結論,後來由罗明證明。
斐波那契數不能為完全数 。推而廣之,除1之外,其他斐氏數皆非多重完全數 ,任兩個斐氏數之比亦不能是完全數。
模n 的週期性 斐波那契數列各項模 n {\displaystyle n} 的餘數構成週期數列 ,其最小正週期稱為皮萨诺周期 ,至多為 6 n {\displaystyle 6n} 。皮薩諾週期對不同 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皮科夫.數學之戀.湖南科技出版社. 參考文獻 註釋 參見 外部連結
This article uses material from the Wikipedia 中文 article 斐波那契数 , which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0") ; additional terms may apply (view authors ). 除非另有声明,本网站内容采用CC BY-SA 4.0 授权。 Images, videos and audio are available under their respective licenses. ®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki 中文 (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.