# 斐波那契数

（重定向自斐波纳契数

• ${\displaystyle F_{0}=0}$
• ${\displaystyle F_{1}=1}$
• ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$（n≧2）

1123581321345589144233377610、 987……（OEIS中的数列A000045

## 起源

• 第一個月初有一對剛誕生的兔子
• 第二個月之後（第三個月初）牠們可以生育
• 每月每對可生育的兔子會誕生下一對新兔子
• 兔子永不死去

## 表達式

### 初等代數解法

• ${\displaystyle a_{1}=1}$
• ${\displaystyle a_{2}=1}$
• ${\displaystyle a_{n}=a_{n-1}+a_{n-2}}$ （n≥3）

#### 首先構建等比數列

${\displaystyle a_{n}+\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})}$

${\displaystyle a_{n}=(\beta -\alpha )a_{n-1}+\alpha \beta a_{n-2}}$

${\displaystyle {\begin{cases}\beta -\alpha =1\\\alpha \beta =1\end{cases}}}$

${\displaystyle {\begin{cases}\alpha ={\dfrac {{\sqrt {5}}-1}{2}}\\\beta ={\dfrac {{\sqrt {5}}+1}{2}}\end{cases}}}$

#### 求出數列{${\displaystyle a_{n}+\alpha a_{n-1}}$ }

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

#### 求數列{${\displaystyle b_{n}}$ }進而得到{${\displaystyle a_{n}}$ }

${\displaystyle b_{n+1}+{\frac {\alpha }{\beta }}b_{n}={\frac {1}{\beta }}}$
${\displaystyle b_{n+1}+\lambda =-{\frac {\alpha }{\beta }}(b_{n}+\lambda )}$ ，解得${\displaystyle \lambda =-{\frac {1}{\alpha +\beta }}}$ 。 故數列${\displaystyle \left\{b_{n}+\lambda \right\}}$ 為等比數列
${\displaystyle b_{n}+\lambda =\left(-{\frac {\alpha }{\beta }}\right)^{n-1}\left(b_{1}+\lambda \right)}$ 。而${\displaystyle b_{1}={\frac {a_{1}}{\beta }}={\frac {1}{\beta }}}$ ， 故有${\displaystyle b_{n}+\lambda =\left(-{\frac {\alpha }{\beta }}\right)^{n-1}\left({\frac {1}{\beta }}+\lambda \right)}$

${\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]}$

### 線性代數解法

${\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}}}$

${\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}}$

#### 構建一個矩陣方程

${\displaystyle {J_{n+1} \choose A_{n+1}}={\begin{pmatrix}0&1\\1&1\end{pmatrix}}\cdot {J_{n} \choose A_{n}},}$

#### 特徵向量

${\displaystyle \left({\begin{pmatrix}0&1\\1&1\end{pmatrix}}-\lambda \cdot E\right)\cdot {\vec {x}}=0}$

${\displaystyle {\vec {x}}_{1}}$ =${\displaystyle {\begin{pmatrix}1\\{\frac {1}{2}}(1+{\sqrt {5}})\end{pmatrix}}}$

${\displaystyle {\vec {x}}_{2}}$ =${\displaystyle {\begin{pmatrix}1\\{\frac {1}{2}}(1-{\sqrt {5}})\end{pmatrix}}}$

#### 分解首向量

${\displaystyle {J_{1} \choose A_{1}}={\begin{pmatrix}0\\1\end{pmatrix}}}$

${\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）

#### 用數學歸納法證明

${\displaystyle {J_{n+1} \choose A_{n+1}}={\begin{pmatrix}0&1\\1&1\end{pmatrix}}\cdot {J_{n} \choose A_{n}}}$ =${\displaystyle \lambda \cdot {J_{n} \choose A_{n}}}$

${\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）

#### 化簡矩陣方程

${\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]}$

${\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的表達式

${\displaystyle A_{n+1}={\frac {1}{\sqrt {5}}}\cdot \lambda _{1}^{n+1}-{\frac {1}{\sqrt {5}}}\cdot \lambda _{2}^{n+1}}$
${\displaystyle A_{n+1}={\frac {1}{\sqrt {5}}}\cdot (\lambda _{1}^{n+1}-\lambda _{2}^{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）即為An+1的表達式

### 組合數解法

${\displaystyle F_{n}=\sum _{i=0}^{\infty }{\binom {n-i}{i}}}$ [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 }$ 黃金比例${\displaystyle {\frac {1+{\sqrt {5}}}{2}}}$ ，則有恆等式${\displaystyle \varphi ^{n}=F_{n-1}+F_{n}\times \varphi }$ ${\displaystyle (1-\varphi )^{n}=F_{n+1}-F_{n}\times \varphi }$ ，其中${\displaystyle n}$ 為任意整數[註 1]，則

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

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

### 近似值

${\displaystyle 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}}$
${\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}}$

## 和黃金分割的關係

${\displaystyle {\frac {f_{n+1}}{f_{n}}}\approx a={\frac {1}{2}}(1+{\sqrt {5}})=\varphi \approx 1{.}618{...}}$

${\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}}}}}}}}}$

${\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}}}}$

${\displaystyle \varphi =1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1+{\frac {1}{1+...}}}}}}}}}$

${\displaystyle \varphi ={\sqrt {1+{\sqrt {1+{\sqrt {1+{\sqrt {1+...}}}}}}}}}$

## 恆等式

• ${\displaystyle F_{n}}$ 可以表示用多個1和多個2相加令其和等於${\displaystyle n}$ 的方法的數目。

• ${\displaystyle F_{0}+F_{1}+F_{2}+F_{3}+...+F_{n}=F_{n+2}-1}$

1. 若第1個被加數是2，有${\displaystyle F_{n}}$ 種方法來計算加至${\displaystyle n-1}$ 的方法的數目；
2. 若第2個被加數是2、第1個被加數是1，有${\displaystyle F_{n-1}}$ 種方法來計算加至${\displaystyle n-2}$ 的方法的數目。
3. 重複以上動作。
4. 若第${\displaystyle n+1}$ 個被加數為2，它之前的被加數均為1，就有${\displaystyle F_{0}}$ 種方法來計算加至0的數目。

• ${\displaystyle F_{1}+2F_{2}+3F_{3}+...+nF_{n}=nF_{n+2}-F_{n+3}+2}$
• ${\displaystyle F_{1}+F_{3}+F_{5}+...+F_{2n-1}=F_{2n}}$
• ${\displaystyle F_{2}+F_{4}+F_{6}+...+F_{2n}=F_{2n+1}-1}$
• ${\displaystyle {F_{1}}^{2}+{F_{2}}^{2}+{F_{3}}^{2}+...+{F_{n}}^{2}=F_{n}F_{n+1}}$
• ${\displaystyle F_{n-1}F_{n+1}-{F_{n}}^{2}=(-1)^{n}}$
• ${\displaystyle \varphi ^{n}=F_{n-1}+F_{n}\times \varphi }$ ${\displaystyle (1-\varphi )^{n}=F_{n+1}-F_{n}\times \varphi }$ ，其中${\displaystyle \varphi }$ 黃金比例${\displaystyle {\frac {1+{\sqrt {5}}}{2}}}$ ${\displaystyle n}$ 為任意整數[註 1]

## 定理

{\displaystyle {\begin{aligned}{F_{m}}{F_{n}}+{F_{m-1}}{F_{n-1}}&=F_{m+n-1}\\F_{m}F_{n+1}+F_{m-1}F_{n}&=F_{m+n}\end{aligned}}}

{\displaystyle {\begin{aligned}F_{2n-1}&=F_{n}^{2}+F_{n-1}^{2}\\F_{2n}&=(F_{n-1}+F_{n+1})F_{n}\\&=(2F_{n-1}+F_{n})F_{n}\end{aligned}}}
• ${\displaystyle F_{n}}$ 整除${\displaystyle F_{m}}$ ，若且唯若n整除m，其中n≧3。
• ${\displaystyle \gcd(F_{m},F_{n})=F_{\gcd(m,n)}}$
• 任意連續三個菲波那契數兩兩互質，亦即，對於每一個n
gcd(Fn, Fn+1) = gcd(Fn, Fn+2) = gcd(Fn+1, Fn+2) = 1

## 相關的數列

### 和盧卡斯數列的關係

${\displaystyle F_{n}L_{n}=F_{2n}}$

### 反費波那西數列

${\displaystyle G_{n+2}=G_{n}-G_{n+1}}$

## 應用

1970年，尤裏·馬季亞謝維奇指出了偶角標的斐波那契函數

${\displaystyle y=F_{2x}}$

## 程式參考

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));

#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';
}

# 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)))


func fibonacci(n int) int {
if n < 2 {
return n
}

return fibonacci(n-2) + fibonacci(n-1)
}


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皮科夫.數學之戀.湖南科技出版社.

## 參考文獻

1. ^ 斐波那契数列与组合数的一个关系及推广. [2014-01-04]. （原始内容存档于2019-05-02）.
2. ^ 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. 李晨滔、馮勁敏. 費氏數列的性質整理 (PDF). 桃園縣立大園國際高中. [2018-01-28]. （原始内容存档 (PDF)于2019-06-25）.
4. ^

## 註釋

1. 這可以透過${\displaystyle \varphi ^{2}=1+\varphi }$ ${\displaystyle {\frac {1}{\varphi }}=\varphi -1}$ ${\displaystyle {\frac {1}{1-\varphi }}=-\varphi }$ 此三個等式，以及費氏數列的的遞歸定義，以數學歸納法證明。