1个回答
展开全部
斐波那契数列
维基百科，自由的百科全书
(重定向自斐波那契数)
跳转到： 导航, 搜索
以斐波那契数为边的正方形拼成的长方形
放大
以斐波那契数为边的正方形拼成的长方形
斐波那契数列，英文为Fibonacci Number，台湾翻为费伯纳西数列。
在数学上，斐波那契数列是以递归的方法来定义：
* F0 = 0
* F1 = 1
* Fn = Fn - 1 + Fn - 2
用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数就由之前的两数相加。首几个斐波那契数是（OEIS A000045）：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
目录
[隐藏]
* 1 源起
* 2 表达式
o 2.1 线性代数解法
o 2.2 近似值
o 2.3 用计算机求解
* 3 和黄金分割的关系
* 4 恒等式
* 5 相关的数列
o 5.1 和卢卡斯数列的关系
o 5.2 反斐波那契数列
o 5.3 巴都万数列
* 6 应用
* 7 参考
* 8 参见
[编辑]
源起
根据高德纳的《计算机程序设计艺术》，1150年印度数学家Gopala和Hemachandra在研究箱子包装物件长阔刚好为1和2的可行方法数目时，首先描述这个数列。在西方，最先研究这个数列的人是比萨的列奥纳多（又名斐波那契），他描述兔子生长的数目时用上了这数列。
* 第一个月有一对刚诞生的兔子
* 第两个月之后它们可以生育
* 每月每对可生育的兔子会诞生下一对新兔子
* 兔子永不死去
假设在n月有新生及可生育的兔子总共a对，n+1月就总共有b对。在n+2月必定总共有a+b对：因为在n+2月的时候，所有在n月就已存在的a对兔子皆已可以生育并诞下a对后代；同时在前一月(n+1月)之b对兔子中，在当月属于新诞生的兔子尚不能生育。
[编辑]
表达式
为求得斐波那契数列的一般表达式，可以借助线性代数的方法。
[编辑]
线性代数解法
1 首先构建一个矩阵方程
设Jn为第n个月新出生的兔子数量，An为这一月份的兔子数量。
{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}},
上式表达了两个月之间，兔子数目之间的关系。而要求的是，An+1的表达式。
2 求矩阵的特征值: λ
行列式：-λ*(1-λ)-1*1=λ²-λ-1
当行列式的值为0，解得λ1=\frac{1}{2} (1 + \sqrt{5}) 或 λ2=\frac{1}{2} (1 - \sqrt{5})
3 特征向量
将两个特征值代入
(\begin{pmatrix}0&1\\1&1\end{pmatrix}-\lambda \cdot E) \cdot\vec x = 0
求特征向量\vec x 得
\vec x_1=\begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}
\vec x_2=\begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}
4 分解首向量
第一个月的情况是兔子一对，新生0对。
{J_{1}\choose A_{1}} = \begin{pmatrix}0\\1\end{pmatrix}
将它分解为用特征向量表示。
\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）
5 用数学归纳法证明
从
{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}}=\lambda \cdot {J_n\choose A_{n}}
可得
{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）
6 化简矩阵方程
将（4） 代入 （5）
{J_{n+1}\choose A_{n+1}} = \lambda^n \cdot [\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}]
根据 3
{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}
7 求A的表达式
现在在6的基础上，可以很快求出An+1 的表达式,将两个特征值代入 6 中
A_{n+1}=\frac{1}{\sqrt{5}} \cdot \lambda_1^{n+1} - \frac{1}{\sqrt{5}} \cdot \lambda_2^{n+1}
A_{n+1}=\frac{1}{\sqrt{5}} \cdot (\lambda_1^{n+1} - \lambda_2^{n+1})
A_{n+1}=\frac{1}{\sqrt{5}} \cdot ((\frac{1}{2} (1 + \sqrt{5}))^{n+1} - (\frac{1}{2} (1 - \sqrt{5}))^{n+1}) (7)
(7)即为An+1 的表达式
[编辑]
近似值
F_n \approx \frac{1}{\sqrt{5}} a^n = \frac{1}{\sqrt{5}} \cdot ( \frac{1}{2} (1 + \sqrt{5}) )^n \approx 0,223606798 \cdot 3,236067977^n
[编辑]
用计算机求解
可通过编程观察斐波那契数列。分为两类问题，一种已知数列中的某一项，求序数。第二种是已知序数，求该项的值。
可通过递归的算法解决此两个问题。
[编辑]
和黄金分割的关系
开普勒发现两个斐波那契数的比会趋近黄金分割：
\frac {f_{n+1}}{f_n} \approx a = \frac{1}{2} (1 + \sqrt{5}) = \Phi \approx 1{,}618{...}
斐波那契数亦可以用连分数来表示：
\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 = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} = {\phi^n \over \sqrt{5}} - {(1-\phi)^n \over \sqrt{5}}
而黄金分割数亦可以用无限连分数表示：
\Phi = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1+ ...}}}}
[编辑]
恒等式
证明以下的恒等式有很多方法。以下会用组合论述来证明。Fn可以表示成用多个1和多个2相加令其和等于n-1的方法的数目。例如F0 = 0，表示没有方法可以加到0。在这里加的过程中，先后次序不同但使用1和使用2的数目一样的两个方法视为不同。例如 1+1+2 和 2+1+1 是两个不同的方法。
* Fn + 1 = Fn + Fn − 1
不失一般性，我们假设n ≥ 1。Fn + 1是计算了将1和2加到n的方法的数目。若第一个被加数是1，有Fn种方法来完成对n-1的计算；若第一个被加数是2，有F(n-1)来完成对n-2的计算。因此，共有Fn + Fn - 1种方法来计算n的值。
* F1 + F2 + F3 + ... + Fn = Fn + 2 - 1
计算用多个1和多个2相加令其和等于n+1的方法的数目，同时最后一个加数是2的情况。
如前所述，当n ≥ 0，有Fn + 2种这样的方法。因为当中只有一种方法不用使用2，就即 1 + 1 + ... + 1 （n+1项），于是我们从Fn + 2减去1。
1. 若第1个被加数是2，有Fn个方法来计算加至n-1的方法的数目；
2. 若第2个被加数是2、第1个被加数是1，有Fn - 1个方法来计算加至n-2的方法的数目。
3. 重覆以上动作。
4. 若第n+1个被加数为2，它之前的被加数均为1，就有F(0)个方法来计算加至0的数目。
若该数式包含2为被加数，2的首次出现位置必然在第1和n+1的被加数之间。2在不同位置的情况都考虑到后，得出Fn + Fn - 1 + ... + F0为要求的数目。
* F1 + 2F2 + 3F3 + ... + nFn = nFn + 2 - Fn + 3 + 2
* F1 + F3 + F5 + ... + F2n - 1 = F2n
* F2 + F4 + F6 + ... + F2n = F2n + 1 - 1
* {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
[编辑]
相关的数列
斐波那契数列是卢卡斯数列的特殊情况。或是斐波那契n步数列步数为2的情形。
[编辑]
和卢卡斯数列的关系
[编辑]
反斐波那契数列
反斐波那契数列的递归公式如下：
Gn + 2 = Gn − Gn + 1
如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...
即是F_{2n+1} = G_{2n+1}，F_{2n} = - G_{2n}。
反斐波那契数列两项之间的比会趋近-\frac{1}{\phi}=-0.618。
[编辑]
巴都万数列
斐波那契数列可以用一个接一个的正方形来表现，巴都万数列则是用一个接一个的等边三角形来表现，它有Pn + 2 = Pn − 2 + Pn − 3的关系。
[编辑]
应用
[编辑]
参考
* Donald E. Knuth: THE ART OF COMPUTER PROGRAMMING Volume 1/Fundamental
Algorithms. 第一章第 1.2.8 节《斐波那契数》。
* 本页的英语、德语和日语版本
[编辑]
参见
* 首五百个斐波那契数
* 齐肯多夫定理
维基百科，自由的百科全书
(重定向自斐波那契数)
跳转到： 导航, 搜索
以斐波那契数为边的正方形拼成的长方形
放大
以斐波那契数为边的正方形拼成的长方形
斐波那契数列，英文为Fibonacci Number，台湾翻为费伯纳西数列。
在数学上，斐波那契数列是以递归的方法来定义：
* F0 = 0
* F1 = 1
* Fn = Fn - 1 + Fn - 2
用文字来说，就是斐波那契数列由0和1开始，之后的斐波那契数就由之前的两数相加。首几个斐波那契数是（OEIS A000045）：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946
目录
[隐藏]
* 1 源起
* 2 表达式
o 2.1 线性代数解法
o 2.2 近似值
o 2.3 用计算机求解
* 3 和黄金分割的关系
* 4 恒等式
* 5 相关的数列
o 5.1 和卢卡斯数列的关系
o 5.2 反斐波那契数列
o 5.3 巴都万数列
* 6 应用
* 7 参考
* 8 参见
[编辑]
源起
根据高德纳的《计算机程序设计艺术》，1150年印度数学家Gopala和Hemachandra在研究箱子包装物件长阔刚好为1和2的可行方法数目时，首先描述这个数列。在西方，最先研究这个数列的人是比萨的列奥纳多（又名斐波那契），他描述兔子生长的数目时用上了这数列。
* 第一个月有一对刚诞生的兔子
* 第两个月之后它们可以生育
* 每月每对可生育的兔子会诞生下一对新兔子
* 兔子永不死去
假设在n月有新生及可生育的兔子总共a对，n+1月就总共有b对。在n+2月必定总共有a+b对：因为在n+2月的时候，所有在n月就已存在的a对兔子皆已可以生育并诞下a对后代；同时在前一月(n+1月)之b对兔子中，在当月属于新诞生的兔子尚不能生育。
[编辑]
表达式
为求得斐波那契数列的一般表达式，可以借助线性代数的方法。
[编辑]
线性代数解法
1 首先构建一个矩阵方程
设Jn为第n个月新出生的兔子数量，An为这一月份的兔子数量。
{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}},
上式表达了两个月之间，兔子数目之间的关系。而要求的是，An+1的表达式。
2 求矩阵的特征值: λ
行列式：-λ*(1-λ)-1*1=λ²-λ-1
当行列式的值为0，解得λ1=\frac{1}{2} (1 + \sqrt{5}) 或 λ2=\frac{1}{2} (1 - \sqrt{5})
3 特征向量
将两个特征值代入
(\begin{pmatrix}0&1\\1&1\end{pmatrix}-\lambda \cdot E) \cdot\vec x = 0
求特征向量\vec x 得
\vec x_1=\begin{pmatrix}1\\\frac{1}{2} (1 + \sqrt{5})\end{pmatrix}
\vec x_2=\begin{pmatrix}1\\\frac{1}{2} (1 - \sqrt{5})\end{pmatrix}
4 分解首向量
第一个月的情况是兔子一对，新生0对。
{J_{1}\choose A_{1}} = \begin{pmatrix}0\\1\end{pmatrix}
将它分解为用特征向量表示。
\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）
5 用数学归纳法证明
从
{J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} \cdot {J_n\choose A_{n}}=\lambda \cdot {J_n\choose A_{n}}
可得
{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）
6 化简矩阵方程
将（4） 代入 （5）
{J_{n+1}\choose A_{n+1}} = \lambda^n \cdot [\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}]
根据 3
{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}
7 求A的表达式
现在在6的基础上，可以很快求出An+1 的表达式,将两个特征值代入 6 中
A_{n+1}=\frac{1}{\sqrt{5}} \cdot \lambda_1^{n+1} - \frac{1}{\sqrt{5}} \cdot \lambda_2^{n+1}
A_{n+1}=\frac{1}{\sqrt{5}} \cdot (\lambda_1^{n+1} - \lambda_2^{n+1})
A_{n+1}=\frac{1}{\sqrt{5}} \cdot ((\frac{1}{2} (1 + \sqrt{5}))^{n+1} - (\frac{1}{2} (1 - \sqrt{5}))^{n+1}) (7)
(7)即为An+1 的表达式
[编辑]
近似值
F_n \approx \frac{1}{\sqrt{5}} a^n = \frac{1}{\sqrt{5}} \cdot ( \frac{1}{2} (1 + \sqrt{5}) )^n \approx 0,223606798 \cdot 3,236067977^n
[编辑]
用计算机求解
可通过编程观察斐波那契数列。分为两类问题，一种已知数列中的某一项，求序数。第二种是已知序数，求该项的值。
可通过递归的算法解决此两个问题。
[编辑]
和黄金分割的关系
开普勒发现两个斐波那契数的比会趋近黄金分割：
\frac {f_{n+1}}{f_n} \approx a = \frac{1}{2} (1 + \sqrt{5}) = \Phi \approx 1{,}618{...}
斐波那契数亦可以用连分数来表示：
\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 = \frac{1}{\sqrt{5}} \left\{ \left( \frac{1+\sqrt{5}}{2} \right)^n - \left( \frac{1-\sqrt{5}}{2} \right)^n \right\} = {\phi^n \over \sqrt{5}} - {(1-\phi)^n \over \sqrt{5}}
而黄金分割数亦可以用无限连分数表示：
\Phi = 1+\frac{1}{1+ \frac{1}{1+ \frac{1}{1+ \frac{1}{1+ ...}}}}
[编辑]
恒等式
证明以下的恒等式有很多方法。以下会用组合论述来证明。Fn可以表示成用多个1和多个2相加令其和等于n-1的方法的数目。例如F0 = 0，表示没有方法可以加到0。在这里加的过程中，先后次序不同但使用1和使用2的数目一样的两个方法视为不同。例如 1+1+2 和 2+1+1 是两个不同的方法。
* Fn + 1 = Fn + Fn − 1
不失一般性，我们假设n ≥ 1。Fn + 1是计算了将1和2加到n的方法的数目。若第一个被加数是1，有Fn种方法来完成对n-1的计算；若第一个被加数是2，有F(n-1)来完成对n-2的计算。因此，共有Fn + Fn - 1种方法来计算n的值。
* F1 + F2 + F3 + ... + Fn = Fn + 2 - 1
计算用多个1和多个2相加令其和等于n+1的方法的数目，同时最后一个加数是2的情况。
如前所述，当n ≥ 0，有Fn + 2种这样的方法。因为当中只有一种方法不用使用2，就即 1 + 1 + ... + 1 （n+1项），于是我们从Fn + 2减去1。
1. 若第1个被加数是2，有Fn个方法来计算加至n-1的方法的数目；
2. 若第2个被加数是2、第1个被加数是1，有Fn - 1个方法来计算加至n-2的方法的数目。
3. 重覆以上动作。
4. 若第n+1个被加数为2，它之前的被加数均为1，就有F(0)个方法来计算加至0的数目。
若该数式包含2为被加数，2的首次出现位置必然在第1和n+1的被加数之间。2在不同位置的情况都考虑到后，得出Fn + Fn - 1 + ... + F0为要求的数目。
* F1 + 2F2 + 3F3 + ... + nFn = nFn + 2 - Fn + 3 + 2
* F1 + F3 + F5 + ... + F2n - 1 = F2n
* F2 + F4 + F6 + ... + F2n = F2n + 1 - 1
* {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
[编辑]
相关的数列
斐波那契数列是卢卡斯数列的特殊情况。或是斐波那契n步数列步数为2的情形。
[编辑]
和卢卡斯数列的关系
[编辑]
反斐波那契数列
反斐波那契数列的递归公式如下：
Gn + 2 = Gn − Gn + 1
如果它以1,-1，之后的数是：1,-1,2,-3,5,-8, ...
即是F_{2n+1} = G_{2n+1}，F_{2n} = - G_{2n}。
反斐波那契数列两项之间的比会趋近-\frac{1}{\phi}=-0.618。
[编辑]
巴都万数列
斐波那契数列可以用一个接一个的正方形来表现，巴都万数列则是用一个接一个的等边三角形来表现，它有Pn + 2 = Pn − 2 + Pn − 3的关系。
[编辑]
应用
[编辑]
参考
* Donald E. Knuth: THE ART OF COMPUTER PROGRAMMING Volume 1/Fundamental
Algorithms. 第一章第 1.2.8 节《斐波那契数》。
* 本页的英语、德语和日语版本
[编辑]
参见
* 首五百个斐波那契数
* 齐肯多夫定理
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
