Fibonacci 数列及其计算方法

#Fibonacci 数列及其计算方法| 来源: 网络整理| 查看: 265

Fibonacci 数列及其计算方法

斐波那契数列（Fibonacci sequence），又称黄金分割数列，这个数列最早是由印度数学家提出来的。不过更多的人学习到这个数列是因为意大利数学家列昂纳多·斐波那契（Leonardoda Fibonacci）和他的《Liber Abaci》一书。在这本书中，列昂纳多·斐波那契以兔子繁殖为例子引出了这个序列，因此这个序列又称为“兔子数列”。这个序列的前几项是这样的： 0,1,1,2,3,5,8,13,21,34,⋯ 在数学上，斐波纳契数列以如下被以递归的方法定义：

F(0)=0F(1)=1F(n)=F(n−1)+F(n−2) ,(n≥2,n∈N)

Fibonacci 数列的通项公式

Fibonacci 数列除了递归形式之外，当然还可以写出通项公式。下面就来算算 F(n) 。

F(n)=F(n−1)+F(n−2) 是典型的线性差分方程，可以用经典的待定系数法来解，当然也可以用 Z 变换解。考虑到不是每个人都学过 Z 变换，这里就给个最基本的待定系数法。假设 F(n)=C×Wn ， C 和 W 是两个待定系数，那么有： Wn=Wn−1+Wn−2 化简一下，得到： W2=W+1 很显然， W 有两个解： W1=1−5√2≈−0.618,W2=1+5√2≈1.618

那么 F(n)=C1Wn1+C2Wn2 也满足 F(n)=F(n−1)+F(n−2) 。 C1,C2 可以通过起始条件来确定。

F(0)=0=C1+C2F(1)=1=C1W1+C2W2 这是一个简单的二元一次方程，计算后可以得到： C1=−5√5,C2=5√5

所以：

F(n)=−5√51−5√2n+5√51+5√2n

当 n 较大时，C1Wn1=−0.4472×(−0.618)n≈0 所以 n 较大时，

F(n)≈5√51+5√2n≈0.4472×1.618n

有些没有学过差分方程理论的同学可能会问为什么假设 F(n)=C×Wn 。简单的说，这是猜的。当然也不是无缘无故的猜测。我们知道 F(n) 的差分方程是这样的：

F(n)=F(n−1)+F(n−2) 我们再构造两个辅助的差分方程：

F1(n)=2F1(n−1)F2(n)=2F2(n−2)

那么当起始条件相同时，明显有 F2(n)

【本文地址】

公司简介

联系我们