斐波那契数列-族谱新闻-族谱网

斐波那契数列

2020-10-16

出处：族谱网

作者：阿族小谱

浏览:666次

转发:0次

评论:0

源起根据高德纳（DonaldErvinKnuth）的《计算机程序设计艺术》（TheArtofComputerProgramming），1150年印度数学家Gopala和金月在研究箱子包装物件长宽刚好为1和2的可行方法数目时，首先描述这个数列。在西方，最先研究这个数列的人是比萨的列奥那多（意大利人斐波那契LeonardoFibonacci），他描述兔子生长的数目时用上了这数列:第一个月初有一对刚诞生的兔子第二个月之后（第三个月初）它们可以生育每月每对可生育的兔子会诞生下一对新兔子兔子永不死去假设在n月有兔子总共a对，n+1月总共有b对。在n+2月必定总共有a+b对：因为在n+2月的时候，前一月（n+1月）的b对兔子可以存留至第n+2月（在当月属于新诞生的兔子尚不能生育）。而新生育出的兔子对数等于所有在n月就已存在的a对表达式为求得斐波那契数列的一般表达式，可以借助线性代数的方法。高中的初等数...

源起

根据高德纳（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对

表达式

为求得斐波那契数列的一般表达式，可以借助线性代数的方法。高中的初等数学知识也能求出。

初等代数解法

已知

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

首先构建等比数列

设 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 a_{n}+\alpha a_{n-1}} }

由以上可得：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 }}{\frac {a_{n}}{\beta ^{n}}}={\frac {1}{\beta }}} 。令 b n = a n β β --> n {\displaystyle b_{n}={\frac {a_{n}}{\beta ^{n}}}}

求数列{ b n {\displaystyle b_{n}} }进而得到{ a n {\displaystyle a_{n}} }

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 + 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 为第n个月有生育能力的兔子数量，A n 为这一月份的兔子数量。

上式表达了两个月之间，兔子数目之间的关系。而要求的是，A n+1 的表达式。

求矩阵的特征值： λ λ --> {\displaystyle \lambda }

行列式： − − --> λ λ --> ( 1 − − --> λ λ --> ) − − --> 1 × × --> 1 = λ λ --> 2 − − --> λ λ --> − − --> 1 {\displaystyle -\lambda (1-\lambda )-1\times 1=\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}})}

特征向量

将两个特征值代入

求特征向量 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对。

将它分解为用特征向量表示。

用数学归纳法证明

从

可得到

化简矩阵方程

将（4）代入（5）

根据3

求A的表达式

现在在6的基础上，可以很快求出A n+1 的表达式，将两个特征值代入6中

（7）即为A n+1 的表达式

组合数解法

F n = ∑ ∑ --> i = 0 ∞ ∞ --> ( n − − --> i i ) {\displaystyle F_{n}=\sum _{i=0}^{\infty }{\binom {n-i}{i}}}

近似值

用计算机求解

可通过编程观察斐波那契数列。分为两类问题，一种已知数列中的某一项，求序数。第二种是已知序数，求该项的值。

可通过递归递推的算法解决此两个问题。事实上当n相当巨大的时候，O（n）的递推/递归非常慢……这时候要用到矩阵快速幂这一技巧，可以使递归加速到O(logn)

和黄金分割的关系

开普勒发现数列前、后两项之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,...... ,也组成了一个数列，会趋近黄金分割：

斐波那契数亦可以用连分数来表示：

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

而黄金分割数亦可以用无限连分数表示：

而黄金分割数也可以用无限多重根号表示：

和自然的关系

许多的生物构成都和斐波那契数列有正相关。例如人体从脚底至头顶之距离和从肚脐至脚底之距趋近于 lim n → → --> ∞ ∞ --> F n F ( n − − --> 1 ) {\displaystyle \lim _{n\to \infty }{\frac {F_{n}}{F_{(n-向日葵}种子 ,向日葵的种子螺旋排列有99%是 F n {\displaystyle F_{n}} 。

恒等式

证明以下的恒等式有很多方法。以下会用组合论述来证明。

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 − − --> 1 F n + 1 − − --> F n 2 = ( − − --> 1 ) n {\displaystyle F_{n-1}F_{n+1}-{F_{n}}^{2}=(-1)^{n}}

定理

特别地，当 m = n 时，

F n {\displaystyle F_{n}} 整除 F m {\displaystyle F_{m}} ，当且仅当 n 整除 m ，其中 n ≧3。

gcd ( F m , F n ) = F gcd ( m , n ) {\displaystyle \gcd(F_{m},F_{n})=F_{\gcd(m,n)}}

任意连续三个菲波那契数两两互素，亦即，对于每一个 n ，