斐波那契数 (意大利语 :Successione di Fibonacci),又译为菲波拿契数 、菲波那西数 、斐氏数 、黄金分割数 。所形成的数列 称为斐波那契数列 (意大利语 :Successione di Fibonacci),又译为菲波拿契数列 、菲波那西数列 、斐氏数列 、黄金分割数列 。这个数列是由意大利 数学家 斐波那契 在他的《算盘书》中提出。
以斐波那契数为边的正方形拼成的近似的黄金矩形 (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开始,之后的斐波那契数就是由之前的两数相加而得出。首几个斐波那契数是:
1 、 1 、 2 、 3 、 5 、 8 、 13 、 21 、 34 、 55 、 89 、 144 、 233 、 377 、 610 、 987……(OEIS 数列A000045 )特别指出 :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}}} [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+...}}}}}}}}} 和自然的关系
编辑
资料来源: [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 的周期性
编辑
斐波那契数列各项模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.
外部链接
编辑