斐波那契数

斐波那契数（意大利语：Numero di Fibonacci），又译为菲波拿契数、菲波那西数、斐氏数、黄金分割数、费氏数列。所形成的数列称为斐波那契数列（意大利语：Successione di Fibonacci），又译为菲波拿契数列、菲波那西数列、斐氏数列、黄金分割数列、费氏数列。这个数列是由意大利数学家斐波那契在他的《算盘书》中提出。

在数学上，斐波那契数是以递归的方法来定义：

- $$F_0=0$$
- $$F_1=1$$
- $F_n = F_{n-1}+ F_{n-2}$（$n\geqq 2$）

用白话文来说，就是斐波那契数列由0和1开始，之后的斐波那契数就是由之前的两数相加而得出。首几个斐波那契数是：

987……

特别指出：0 不是第一项，而是第零项（$F_0$）。

## 起源

公元1150年印度数学家Gopala和金月在研究箱子包装物件长宽刚好为1和2的可行方法数目时，首先描述这个数列。在西方，最先研究这个数列的人是比萨的列奥那多（意大利人斐波那契Leonardo Fibonacci, 1175－1250），他描述兔子生长的数目时用上了这数列：

<image>

- 第一个月初有一对刚诞生的兔子
- 第二个月之后（第三个月初）它们可以生育
- 每月每对可生育的兔子会诞生下一对新兔子
- 兔子永不死去

假设在$n$月有兔子总共$a$对，$n+1$月总共有$b$对。在$n+2$月必定总共有$a+b$对：因为在$n+2$月的时候，前一月（$n+1$月）的$b$对兔子可以存留至第$n+2$月（在当月属于新诞生的兔子尚不能生育）。而新生育出的兔子对数等于所有在$n$月就已存在的$a$对

<image>

斐波纳契数也是杨辉三角形（即帕斯卡三角形）的每一条红色对角线上数字的和。

## 表达式

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

### 初等代数解法

已知：

- $$a_1=1$$
- $$a_2=1$$
- $a_n = a_{n-1}+ a_{n-2}$（n≥3）

#### 首先构建等比数列

设$a_n +\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})$化简得$a_n=(\beta -\alpha) a_{n-1}+ \alpha\beta a_{n-2}$ 比较系数可得：

$$\begin{cases} \beta-\alpha=1 \\ \alpha\beta=1 \end{cases}$$ 不妨设$\beta>0, \alpha>0$ 解得：

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

又因为有$a_n +\alpha a_{n-1}=\beta (a_{n-1}+\alpha a_{n-2})$。

即$\left\{a_n +\alpha a_{n-1}\right\}$为等比数列。

#### 求出数列{an+αan-1}

由以上可得：

$\begin{align}a_{n+1} +\alpha a_{n} &=(a_2+\alpha a_1)\beta^{n-1}\\ & = (1+\alpha)\beta^{n-1}\\ & =\beta^n \\ \end{align}$

变形得：

$\frac{a_{n+1}}{\beta^{n+1}}+\frac{\alpha}{\beta}\cdot\frac{a_{n}}{\beta^{n}}=\frac{1}{\beta}$。

令$b_n=\frac{a_n}{\beta^n}$

#### 求数列{bn}进而得到{an}

$b_{n+1}+\frac{\alpha}{\beta}b_{n}=\frac{1}{\beta}$ 设$b_{n+1}+\lambda=-\frac{\alpha}{\beta} (b_{n}+\lambda)$，解得$\lambda=-\frac{1}{\alpha+\beta}$。

故数列$\left\{b_n+\lambda\right\}$为等比数列即$b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(b_1+\lambda\right)$。而$b_1=\frac{a_1}{\beta}=\frac{1}{\beta}$。

故有$b_n+\lambda=\left(-\frac{\alpha}{\beta}\right)^{n-1}\left(\frac{1}{\beta}+\lambda\right)$ 又有$\begin{cases} \alpha=\dfrac{\sqrt{5}-1}{2} \\ \beta=\dfrac{\sqrt{5}+1}{2} \end{cases}$ 和$b_n=\frac{a_n}{\beta^n}$ 可得$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}$表达式，称比内公式(Binet's Formula)

$$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=\frac{1}{\sqrt{5}}[\varphi^n-(1-\varphi)^n]$，其中$\varphi$为黄金比例$\frac{1+\sqrt{5}}{2}$，$n$为任意整数

- 若$n$为非负整数

当$n=0$时，$\frac{1}{\sqrt{5}}[\varphi^0-(1-\varphi)^0]=\frac{1}{\sqrt{5}}[1-1]=0=F_0$，成立

当$n=1$时，$\frac{1}{\sqrt{5}}[\varphi^1-(1-\varphi)^1]=\frac{1}{\sqrt{5}}[\varphi-1+\varphi]=\frac{1}{\sqrt{5}}[2\varphi-1]=\frac{1}{\sqrt{5}} \times \sqrt{5}=1=F_1$，成立

设当$n=k$及$n=k+1$时皆成立，即$F_k=\frac{1}{\sqrt{5}}[\varphi^k-(1-\varphi)^k]$且$F_{k+1}=\frac{1}{\sqrt{5}}[\varphi^{k+1}-(1-\varphi)^{k+1}]$

当$n=k+2$时

$$\begin{align} F_{k+2}&=F_{k+1}+F_k \\ & =\frac{1}{\sqrt{5}}[\varphi^{k+1}-(1-\varphi)^{k+1}]+\frac{1}{\sqrt{5}}[\varphi^k-(1-\varphi)^k] \\ & =\frac{1}{\sqrt{5}} [\varphi^{k+1}+\varphi^k-(1-\varphi)^{k+1}-(1-\varphi)^k] \\ & =\frac{1}{\sqrt{5}} \left\{ \varphi^k({\color{brown}\varphi+1})-(1-\varphi)^k[{\color{green}(1-\varphi)+1}] \right\} \\ & =\frac{1}{\sqrt{5}} \left\{ \varphi^k({\color{brown}\varphi^2})-(1-\varphi)^k[{\color{green}(1-\varphi)^2}] \right\} \\ & =\frac{1}{\sqrt{5}} \left\{ \varphi^{k+2}-(1-\varphi)^{k+2} \right\} \\ \end{align}$$

亦成立

- 若$n$为非正整数

当$n=0$时，成立

当$n=-1$时，$\frac{1}{\sqrt{5}}[{\color{brown}\varphi^{-1}}-{\color{green}(1-\varphi)^{-1}}]=\frac{1}{\sqrt{5}}[({\color{brown}\varphi-1})-({\color{green}-\varphi})]=\frac{1}{\sqrt{5}}[2\varphi-1]=\frac{1}{\sqrt{5}} \times \sqrt{5}=1=F_{-1}$，成立

设当$n=-k$及$n=-k-1$时皆成立，即$F_{-k}=\frac{1}{\sqrt{5}}[\varphi^{-k}-(1-\varphi)^{-k}]$且$F_{-k-1}=\frac{1}{\sqrt{5}}[\varphi^{-k-1}-(1-\varphi)^{-k-1}]$

当$n=-k-2$时

$$\begin{align} F_{-k-2}&=F_{-k}-F_{-k-1} \\ & =\frac{1}{\sqrt{5}}[\varphi^{-k}-(1-\varphi)^{-k}]-\frac{1}{\sqrt{5}}[\varphi^{-k-1}-(1-\varphi)^{-k-1}] \\ & =\frac{1}{\sqrt{5}}[\varphi^{-k}-\varphi^{-k-1}-(1-\varphi)^{-k}+(1-\varphi)^{-k-1}] \\ & =\frac{1}{\sqrt{5}}\left\{\varphi^{-k-1}({\color{brown}\varphi-1})-(1-\varphi)^{-k-1}[{\color{green}(1-\varphi)-1}] \right\} \\ & =\frac{1}{\sqrt{5}}\left\{\varphi^{-k-1}({\color{brown}\varphi^{-1}})-(1-\varphi)^{-k-1}[{\color{green}(1-\varphi)^{-1}}] \right\} \\ & =\frac{1}{\sqrt{5}}\left\{\varphi^{-k-2}-(1-\varphi)^{-k-2}\right\} \\ \end{align}$$

亦成立

因此，根据数学归纳法原理，此表达式对于任意整数$n$皆成立

### 线性代数解法

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

$$\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}$$ 称为“斐波那契Q矩阵”(Fibonacci Q-Matrix)

#### 构建一个矩阵方程

设$J_n$为第$n$个月有生育能力的兔子数量，$A_n$为这一月份的兔子数量。

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

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

#### 求矩阵的特征值：λ

根据特征值的计算公式，我们需要算出来 $\begin{vmatrix} <pre> -\lambda & 1 \\ 1 & 1 - \lambda \\ </pre> \end{vmatrix} = 0$ 所对应的解。

展开行列式有：$-\lambda(1-\lambda)-1\times1=\lambda^2-\lambda-1$。

故当行列式的值为 0，解得 $\lambda_1 =\frac{1}{2} (1 + \sqrt{5})$ 或 $\lambda_2 =\frac{1}{2} (1 - \sqrt{5})$。

#### 特征向量

将两个特征值代入

$$\left(\begin{pmatrix}0&1\\1&1\end{pmatrix}-\lambda \cdot E\right) \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}$

#### 分解首向量

第一个月的情况是兔子一对，新生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）

#### 用数学归纳法证明

从

${J_{n+1}\choose A_{n+1}} = \begin{pmatrix}0&1\\1&1\end{pmatrix} <pre> \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）

#### 化简矩阵方程

将（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]$$

根据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}$$

#### 求A的表达式

现在在6的基础上，可以很快求出$A_{n+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 \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）即为$A_{n+1}$的表达式

### 数论解法

实际上，如果将斐波那契数列的通项公式写成$a_n-a_{n-1}-a_{n-2}=0$，即可利用解二阶线性齐次递回关系式的方法，写出其特征多项式$\lambda^2-\lambda-1=0$（该式和表达斐波那契数列的矩阵的特征多项式一致），然后解出$\lambda_1$=$\frac{1}{2} (1 + \sqrt{5})$，$\lambda_2$=$\frac{1}{2} (1 - \sqrt{5})$，即有$a_n=c_1\lambda_1^n+c_2\lambda_2^n$，其中$c_1,c_2$为常数。我们知道$a_0=0,a_1=1$，因此$\begin{cases} c_1+c_2=0 \\ \frac{c_1(1+\sqrt{5})}{2} +\frac{c_2(1-\sqrt{5})} {2}=1\end{cases}$，解得$c_1=\frac{1}{\sqrt{5}},c_2=-\frac{1}{\sqrt{5}}$。

### 组合数解法

$F_n=\sum_{i=0}^{\infty} \binom {n-i}{i}$

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

### 黄金比例恒等式解法

设$\varphi$为黄金比例$\frac{1+\sqrt{5}}{2}$，则有恒等式$\varphi^n=F_{n-1}+\varphi F_n$与$(1-\varphi)^n=F_{n+1}-\varphi F_n$，其中$n$为任意整数，则

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

因此得到$F_n$的一般式：

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

此一般式对任意整数$n$成立

### 近似值

当$n$为足够大的正整数时，则

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

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

### 用计算机求解

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

可通过递归递推的算法解决此两个问题。

事实上当$n$相当巨大的时候，O（n）的递推/递归非常慢……这时候要用到矩阵快速幂这一技巧，可以使递回加速到O(logn)。

## 和黄金分割的关系

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

$$\frac {f_{n+1}}{f_n} \approx a = \frac{1}{2} (1 + \sqrt{5}) = \varphi \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] = {\varphi^n \over \sqrt{5}} - {(1-\varphi)^n \over \sqrt{5}}$$

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

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

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

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

## 和自然的关系

<image>

斐氏数列见于不同的生物学现象，如树的分枝、叶序、菠萝聚花果上小单果的排列、雅枝竹的花蕾、正在舒展的蕨叶、松球的鳞的排列、蜜蜂的家族树。开普勒曾指出斐氏数列存在于自然界，并以此解释某些花的五边形形态（与黄金分割率相关）。法国菊的“瓣”（舌状花）数通常为斐氏数。1830年，K. F. Schimper和A. Braun发现植物的旋生叶序中，连续两块叶之间转过的角度与周角之比，约成整数比时，常出现斐氏数，如$2/5$或$5/13$。

## 恒等式

资料来源：

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

- $F_n$可以表示用多个1和多个2相加令其和等于$n$的方法的数目。

不失一般性，我们假设$n\geq1$，$F_{n+1}$是计算了将1和2加到n的方法的数目。若第一个被加数是1，有$F_n$种方法来完成对$n-1$的计算；若第一个被加数是2，有$F_{n-1}$来完成对$n-2$的计算。因此，共有$F_n + F_{n-1}$种方法来计算n的值。

- $$F_0 + F_1 + F_2 + F_3 + ... + F_n = F_{n+2} - 1$$

计算用多个1和多个2相加令其和等于$n+1$的方法的数目，同时至少一个加数是2的情况。

如前所述，当$n>0$，有$F_{n+2}$种这样的方法。因为当中只有一种方法不用使用2，就即$1+1+...+1$ （$n+1$项），于是我们从$F_{n+2}$减去1。

- 若第1个被加数是2，有$F_n$种方法来计算加至$n-1$的方法的数目。
- 若第2个被加数是2、第1个被加数是1，有$F_{n-1}$种方法来计算加至$n-2$的方法的数目。
- 重复以上动作。
- 若第$n+1$个被加数为2，它之前的被加数均为1，就有$F_{0}$种方法来计算加至0的数目。

若该数式包含2为被加数，2的首次出现位置必然在第1和$n+1$的被加数之间。2在不同位置的情况都考虑到后，得出$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$$
- $$F_1 + F_3 + F_5 + ... + F_{2n-1} = F_{2n}$$
- $$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}$$
- ${F_1}^3 + {F_2}^3 + {F_3}^3 + \cdots + {F_n}^3 = \frac{3F_{n+1}^2F_n-F_{n+1}^3-F_n^3+1}{2}$
- $$F_1F_2+F_2F_3+F_3F_4+ \cdots +F_{2n}F_{2n+1}={F_{2n+1}}^2-1$$
- $$F_1F_2+F_2F_3+F_3F_4+ \cdots +F_{2n+1}F_{2n+2}={F_{2n+2}}^2$$
- $F_nF_{m-k}-F_mF_{n-k}=(-1)^{n-k}F_{m-n}F_k$，其中$m,n,k$与$F$的序数皆不限于正整数。例如当$(m,n,k)=(4,-8,6)$时，$F_{-8}F_{-2}-F_4F_{-14}=(-21) \times (-1)-3 \times (-377)=(-1)^{-14}F_{12}F_6=1 \times 144 \times 8=1152$
- 特别地，当$n=m-k$时，${F_n}^2-F_{n+k} F_{n-k} = (-1)^{n-k}{F_k}^2$
- 更特别地，当$k=1$或$k=-1$时，对于数列连续三项，有${F_n}^2-F_{n-1} F_{n+1} = (-1)^{n-1}$
- 另一方面，当$(m,n,k)=(n+1,n,-2)$时，对于数列连续四项，有$F_nF_{n+3}-F_{n+1}F_{n+2}=(-1)^{n+1}$
- $\varphi^n=F_{n-1}+\varphi F_n$且$(1-\varphi)^n=F_{n+1}-\varphi F_n$，其中$\varphi$为黄金比例$\frac{1+\sqrt{5}}{2}$，$n$为任意整数这可以透过$\varphi^2=1+\varphi$与$\frac{1}{\varphi}=\varphi-1$与$\frac{1}{1-\varphi}=-\varphi$此三个等式，以及费氏数列的递归定义，以数学归纳法证明。

借由上述公式，又可推得以下恒等式利用指数律$\varphi^{m+n}=\varphi^m \times \varphi^n$、性质$\varphi^2=1+\varphi$，以及“若$a,b,c,d$是有理数，$x$是无理数，且满足$a+bx=c+dx$，则$a=c,b=d$”证明。

- ${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}$特别地，当$m=n$时，$\begin{align} <pre> 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 </pre> \end{align}$

## 数论性质

### 公因数和整除关系

- $F_n$整除$F_m$，当且仅当$n$整除$m$，其中$n\geqq 3$。
- $$\gcd(F_m,F_n)=F_{\gcd(m,n)}$$
- 任意连续三个菲波那契数两两互质，亦即，对于每一个$n$。

$$\mathrm{gcd}(F_n, F_{n+1})=\mathrm{gcd}(F_n, F_{n+2})=\mathrm{gcd}(F_{n+1}, F_{n+2})=1$$

### 斐波那契质数

在斐波那契数列中，有质数：

2, 3, 5, 13, 89, 233, 1597, 28657, 514229, 433494437, 2971215073, 99194853094755497, 1066340417491710595814572169, 19134702400093278081449423917……

截至2015年，已知最大的斐波那契质数是第104911个斐波那契数，一共有21925个十进制位。不过，人们仍不知道是不是有无限个斐波那契质数。

如#公因数和整除关系所述，$F_{kn}$总能被$F_n$整除，故除$F_4 = 3$之外，任何斐氏质数的下标必同为质数。由于存在任意大的一列连续合数，斐氏数列中亦能找到连续任意多项全为合数。

大于$F_6 = 8$的斐氏数，必不等于质数加一或减一。

### 与其他数列的交集

斐波那契数列中，只有3个平方数：0、1、144。2001年，派特·奥蒂洛证明，斐氏数中的次方数只有有限多个。2006年，Y. Bugeaud、M. Mignotte、S. Siksek三人证明，斐波那契数中的次方数只有0、1、8、144。

1、3、21、55为仅有的斐氏三角形数。Vern Hoggatt曾猜想此结论，后来由罗明证明。

斐波那契数不能为完全数。推而广之，除1之外，其他斐氏数皆非多重完全数，任两个斐氏数之比亦不能是完全数。

### 模n的周期性

斐波那契数列各项模$n$的余数构成周期数列，其最小正周期称为皮萨诺周期，至多为$6n$。皮萨诺周期对不同$n$值的通项公式仍是未解问题，其中一步需要求出某个整数（同余意义下）或二次有限域元素的乘法阶数。不过，对固定的$n$，求解模$n$的皮萨诺周期是周期检测问题的特例。

## 推广

斐波那西数列是斐波那西n步数列步数为2的特殊情况，也和卢卡斯数列有关。

### 和卢卡斯数列的关系

$$F_nL_n=F_{2n}$$

### 反费波那西数列

反费波那西数列的递归公式如下：

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

如果它以1,-1开始，之后的数是：1,-1,2,-3,5,-8, ...

即是$F_{2n+1} = G_{2n+1}=F_{-(2n+1)}, F_{2n} = - G_{2n}=-F_{-2n}$。

亦可写成$F_m = (-1)^{m+1}G_m=(-1)^{m+1}F_{-m}$，其中$m$是非负整数。

反费波那西数列两项之间的比会趋近$-\frac{1}{\varphi} \approx -0.618$。

#### 证明关系式

证明$F_m = (-1)^{m+1}F_{-m}$，其中$m$是非负整数

以$\varphi$表示黄金分割数$\frac{1+\sqrt{5}}{2}$，则有$\varphi (1-\varphi)=-1$

故$(-1)^m=[\varphi (1-\varphi)]^m=\varphi^m (1-\varphi)^m$，因此

$$\begin{align} (-1)^{m+1}F_{-m}&=(-1)^{m+1} \times \frac{1}{\sqrt{5}}[\varphi^{-m}-(1-\varphi)^{-m}]\\ &=(-1) \times {\color{brown}(-1)^m} \times \frac{1}{\sqrt{5}}[\varphi^{-m}-(1-\varphi)^{-m}]\\ &=(-1)\times {\color{brown}\varphi^m (1-\varphi)^m} \times \frac{1}{\sqrt{5}}[\varphi^{-m}-(1-\varphi)^{-m}]\\ &=(-1) \times \frac{1}{\sqrt{5}}[\varphi^{-m+m}(1-\varphi)^m-(1-\varphi)^{-m+m}\varphi^m]\\ &=(-1) \times \frac{1}{\sqrt{5}}[(1-\varphi)^m-\varphi^m]\\ &=\frac{1}{\sqrt{5}}[\varphi^m-(1-\varphi)^m]\\ &=F_m\\ \end{align}$$

### 巴都万数列

费波那西数列可以用一个接一个的正方形来表现，巴都万数列则是用一个接一个的等边三角形来表现，它有$P_{n} = P_{n-2} + P_{n-3}$的关系。

### 佩尔数列

佩尔数列的递归公式为$P_{n} = 2P_{n-1} + P_{n-2}$，前几项为0,1,2,5,12,29,70,169,408,...

## 应用

1970年，尤里·马季亚谢维奇指出了偶角标的斐波那契函数

$$y = F_{2x}$$

正是满足Julia Robison假设的丢番图函数，因而证明了希尔伯特第十问题是不可解的。

### 电脑科学

<image>

- 考虑以辗转相除法求两个正整数的最大公因数，分析此算法的运行时间。同等输入规模下，最坏情况（用时最长）发生于输入为两个相邻斐氏数时。
- 归并排序算法有一多相（polyphase）版本用到斐氏数列，是将未排序的数组分为两份，长度为相邻的斐氏数（因此比值接近黄金比）。《计算机程序设计艺术》描述了此种多相合并排序的实作方法，适用于以磁带机为外存的情况。
- 斐波那契树是一棵二叉树，其每个节点的左右子树高皆恰好差1。由此，斐氏树为AVL树，且对固定高度而言，是最少节点的AVL树。此类树的节点数可写成斐氏数减1。
- 某些伪随机数生成器用到斐氏数列。
- 斐波那契堆是一种数据结构，分析其时间复杂度时会用到斐波那契数。
- 斐波那契编码是以01字串表示正整数的一种方法，负斐波那契编码与之类似，还可以表示负数。

## 延伸阅读

- KNUTH, D. E. 1997. The Art 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皮科夫.数学之恋.湖南科技出版社.

## 外部链接

- 费波那契数，孙智宏（pdf）
- Periods of Fibonacci Sequences Mod m at MathPages
- Scientists find clues to the formation of Fibonacci spirals in nature
- Fibonacci Sequence