以斐波那契數為邊的正方形拼成的近似的
黃金矩形(1:1.618)
斐波那契数(意大利语:Successione di Fibonacci),又譯為菲波拿契數、菲波那西數、斐氏數、黃金分割數。所形成的數列稱為斐波那契数列(意大利语:Successione di Fibonacci),又譯為菲波拿契數列、菲波那西數列、斐氏數列、黃金分割數列。
在數學上,斐波那契數是以遞歸的方法來定義:


(n≧2)
用文字來說,就是斐波那契數列由0和1開始,之後的斐波那契數就是由之前的兩數相加而得出。首幾個斐波那契數是:
- 1、 1、 2、 3、 5、 8、 13、 21、 34、 55、 89、 144、 233、 377、 610、 987……(OEIS中的数列A000045)
特別指出:0不是第一項,而是第零項。
公元1150年印度數學家Gopala和金月在研究箱子包裝物件長宽剛好為1和2的可行方法數目時,首先描述這個數列。在西方,最先研究這個數列的人是比薩的李奧納多(義大利人斐波那契Leonardo Fibonacci),他描述兔子生長的數目時用上了這數列:
- 第一個月初有一對剛誕生的兔子
- 第二個月之後(第三個月初)牠們可以生育
- 每月每對可生育的兔子會誕生下一對新兔子
- 兔子永不死去
假設在n月有兔子總共a對,n+1月總共有b對。在n+2月必定總共有a+b對:因為在n+2月的時候,前一月(n+1月)的b對兔子可以存留至第n+2月(在當月屬於新誕生的兔子尚不能生育)。而新生育出的兔子對數等於所有在n月就已存在的a對
斐波纳契数也是杨辉三角的每一条红色对角线上数字的和。
表達式[编辑]
為求得斐波那契數列的一般表達式,可以藉助線性代數的方法。高中的初等數學知識也能求出。
初等代數解法[编辑]
已知


(n≥3)
首先構建等比數列[编辑]
設
化簡得

比較係數可得:
不妨設
解得:
又因为有
,
即
為等比數列。
求出數列{
}[编辑]
由以上可得:

變形得:
。
令
求數列{
}進而得到{
}[编辑]

設
,解得
。
故數列
為等比數列
即
。而
,
故有
又有
和
可得
得出
表達式
線性代數解法[编辑]
構建一個矩陣方程[编辑]
設Jn為第n個月有生育能力的兔子數量,An為這一月份的兔子數量。

上式表達了兩個月之間,兔子數目之間的關係。而要求的是,An+1的表達式。
求矩陣的特徵值:
[编辑]
根据特征值的计算公式,我们需要算出来
所对应的解。
展开行列式有:
。
故當行列式的值為 0,解得
或
。
將兩個特徵值代入

求特徵向量
得
=
=
分解首向量[编辑]
第一個月的情況是兔子一對,新生0對。

將它分解為用特徵向量表示。
(4)
從
=
可得到
(5)
化簡矩陣方程[编辑]
將(4) 代入 (5)
![{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]](https://wikimedia.org/api/rest_v1/media/math/render/svg/bc133beb4b93512f07a7d4137d65f3370ef034b0)
根據3

求A的表達式[编辑]
現在在6的基礎上,可以很快求出An+1的表達式,將兩個特徵值代入6中


(7)
(7)即為An+1的表達式
數論解法[编辑]
實際上,如果將斐波那契數列的通項公式寫成
,即可利用解二階線性齊次遞迴關係式的方法,寫出其特徵多項式
(該式和表達斐波那契數列的矩陣的特徵多項式一致),然後解出
=
,
=
,即有
,其中
为常数。我们知道
,因此
,解得
。
組合數解法[编辑]
[1]

黃金比例恆等式解法[编辑]
設
為黃金比例
,則有恆等式
與
,其中
為任意整數[註 1],則
因此得到
的一般式:
此一般式對任意整數
成立
近似值[编辑]
當
為足夠大的正整數時
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/50053dc83435d2c5ae69ad1ad31e0f1caf5cf4a7)
![{\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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fd72835a21743b30d3cbb877616c0951db09ee0a)
用計算機求解[编辑]
可通過編程觀察斐波那契數列。分為兩類問題,一種已知數列中的某一項,求序數。第二種是已知序數,求該項的值。
可通過遞歸遞推的算法解決此兩個問題。
事實上當n相當巨大的時候,O(n)的遞推/遞歸非常慢……這時候要用到矩陣快速幂這一技巧,可以使遞迴加速到O(logn)。
和黃金分割的關係[编辑]
開普勒發現數列前、後兩項之比1/2 ,2/3 , 3/5 ,5/8 ,8/13 ,13/21 ,21/34 ,...... ,也組成了一個數列,會趨近黃金分割:

斐波那契數亦可以用連分數來表示:
而黃金分割數亦可以用無限連分數表示:

而黃金分割數也可以用無限多重根號表示:

與平方數的關係[编辑]
斐波那契数列中,只有3個平方數:0、1、144。[2]
和自然的關係[编辑]
許多的生物構成都和斐波那契數列有正相關。例如人體從脚底至頭頂之距離和從肚臍至腳底之距趨近於
,向日葵的種子螺旋排列有99%是
。[來源請求]
恆等式[编辑]
資料來源:[3]
證明以下的恆等式有很多方法。以下會用組合論述來證明。
可以表示用多個1和多個2相加令其和等於
的方法的數目。
不失一般性,我們假設
,
是計算了將1和2加到n的方法的數目。若第一個被加數是1,有
種方法來完成對
的計算;若第一個被加數是2,有
來完成對
的計算。因此,共有
種方法來計算n的值。

計算用多個1和多個2相加令其和等於
的方法的數目,同時至少一個加數是2的情況。
如前所述,當
,有
種這樣的方法。因為當中只有一種方法不用使用2,就即
(
項),於是我們從
減去1。
- 若第1個被加數是2,有
種方法來計算加至
的方法的數目;
- 若第2個被加數是2、第1個被加數是1,有
種方法來計算加至
的方法的數目。
- 重複以上動作。
- 若第
個被加數為2,它之前的被加數均為1,就有
種方法來計算加至0的數目。
若該數式包含2為被加數,2的首次出現位置必然在第1和
的被加數之間。2在不同位置的情況都考慮到後,得出
為要求的數目。





且
,其中
為黃金比例
,
為任意整數[註 1]
資料來源:[3]

特別地,當m = n時,

整除
,若且唯若n整除m,其中n≧3。

- 任意連續三個菲波那契數兩兩互質,亦即,對於每一個n,
- gcd(Fn, Fn+1) = gcd(Fn, Fn+2) = gcd(Fn+1, Fn+2) = 1
相關的數列[编辑]
斐波那西數列是斐波那西n步數列步數為2的特殊情況,也和盧卡斯數列有關。
和盧卡斯數列的關係[编辑]

反費波那西數列[编辑]
反費波那西數列的遞歸公式如下:

如果它以1,-1開始,之後的數是:1,-1,2,-3,5,-8, ...
即是
。
反費波那西數列兩項之間的比會趨近
。
巴都萬數列[编辑]
費波那西數列可以用一個接一個的正方形來表現,巴都萬數列則是用一個接一個的等邊三角形來表現,它有
的關係。
佩爾數列[编辑]
佩爾數列的遞歸公式為
,前幾項為0,1,2,5,12,29,70,169,408,...
1970年,尤裏·馬季亞謝維奇指出了偶角標的斐波那契函數

正是滿足Julia Robison假設的丟番圖函數,因而證明了希爾伯特第十問題是不可解的。
斐波那契质数[编辑]
在斐波那契數列中,有質數:
2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……
目前已知最大質數是第81839個斐波那契數,一共有17103位數。不过,人们仍不知道是不是无限个有斐波那契质数。[4]
程式參考[编辑]
JavaScript迭代版
function fib(n) {
var fib_n = function(curr, next, n) {
if (n == 0) {
return curr;
}
else {
return fib_n(next, curr+next, n-1);
}
}
return fib_n(0, 1, n);
}
alert(fib(40));
C语言通项公式版
#include <stdio.h>
#include <math.h>
int main()
{
int n;
double constant_a = (1 + sqrt(5)) / 2;
double constant_b = (1 - sqrt(5)) / 2;
double constant_c = sqrt(5) / 5;
double value_1 = 0;
int value_2 = 0;
scanf("%d", &n);
if(n > 0)
{
for (int i = 0; i < n; i++)
{
value_1 = constant_c * (pow(constant_a, i) - pow(constant_b, i));
value_2 = (int)value_1;
printf("%d\n", value_2);
}
return 0;
}
else
{
return -1;
}
}
c++二變數求某項版
#include <iostream>
using namespace std;
int main () {
int x,y,n;
x=1;y=0;
cin >> n;
for (int i=0;i<n;i=i+1) {
x=x+y;
y=x-y;
}
cout << y;
return 0;
}
c++通项公式版
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
unsigned long long n;
double ca = (1 + sqrt(5)) / 2;
double cb = (1 - sqrt(5)) / 2;
double cc = sqrt(5) / 5;
double v1 = 0;
double v2 = 0;
cout <<" ";
cin>>n;
if(n > 0)
{
for (unsigned long long i = 0; i < n; i++)
{
v1 = cc * (pow(ca, i) - pow(cb, i));
v2 = (int)v1;
cout <<v2<<endl;
}
return 0;
}
else
{
return -1;
}
cout <<'/b';
}
Python语言通项公式版
# Fibonacci numbers module
def fib(n): # write Fibonacci series up to n
a, b = 0, 1
while b < n:
print(b, end=' ')
a, b = b, a+b
print()
def fib2(n): # return Fibonacci series up to n
result = []
a, b = 0, 1
while b < n:
result.append(b)
a, b = b, a+b
return result
fibs = [0, 1]
numZS = int(input('How many Fibonacci numbers do you want? '))
for i in range(numZS-2):
fibs.append(fibs[-2] + fibs[-1])
print fibs
Common Lisp
(defun fibs (x)
(cond ((equal x 0) 1)
((equal x 1) 1)
(t (+ (fibs (- x 1))
(fibs (- x 2))))))
(defun fibs (x)
(do ((n 0 (+ n 1))
(i 1 j)
(j 1 (+ i j)))
((equal n x) i)))
Go
遞迴版,時間複雜度為 O(2^n):
func fibonacci(n int) int {
if n < 2 {
return n
}
return fibonacci(n-2) + fibonacci(n-1)
}
通用版,時間複雜度為 O(n):
func fibonacci(n int) int {
a, b := n%2, 1
for i := 0; i < n/2; i++ {
a += b
b += a
}
return a
}
Java语言通项公式版:
public int fibonacci(int n){
if(n<2){
return n;
}else {
return fibonacci(n-1)+fibonacci(n-2);
}
}
Java语言快捷版:
public int fibonacci(int n){
if(n<2){
return n;
}else {
int[] ans = new int[n];
ans[0] = 1;
ans[1] = 2;
for(int i=2;i<n;i++) {
ans[i]=ans[i-1]+ans[i-2];
}
return ans[n-1];
}
}
C语言陣列版:
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n,s,L;
printf("輸入長度");
scanf("%d",&L);
while(L<0)
{
printf("錯誤");
return 0;
}
int a[L];
int x=1,y=2;
a[0]=x;
a[1]=x;
a[2]=y;
for(n=3;n<L;n++)
{
a[n]=a[n-1]+a[n-2];
}
for(n=0;n<L;n++)
{
printf("%d ",a[n]);
}
system("pause");
return 0;
}
Python Lambda 遞迴版:
fib = lambda n: n if n<2 else fib(n-1) + fib(n-2)
延伸閱讀[编辑]
- 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).
- ^ JOHN H. E. COHN. Square Fibonacci Numbers, Etc.. Bedford College, University of London, London, N.W.1. (原始内容存档于2012-06-30).
Theorem 3. If Fn = x2, then n = 0, ±1, 2 or 12.
- ^ 3.0 3.1 李晨滔、馮勁敏. 費氏數列的性質整理 (PDF). 桃園縣立大園國際高中. [2018-01-28]. (原始内容存档 (PDF)于2019-06-25).
- ^ 埃里克·韦斯坦因. Fibonacci Prime. MathWorld.
外部連結[编辑]