最后更新: 2025-05-28 08:29 查看: 644 次纠错评论(0) 课件开VIP

附录1：斐波那契数列

> 之所以把斐波那契数列单独拿出来介绍是因为这个数列在数学、物理、计算机、自然科学里占有重要地位，很多较为复杂的公式都是以他为基础。

## 斐波那契数列起源
故事得从西元1202年说起，话说有一位意大利青年，名叫斐波那契。在他的一部著作中提出了一个有趣的问题：假设一对刚出生的小兔一个月后就能长成大兔，再过一个月就能生下一对小兔，并且此后每个月都生一对小兔，一年内没有发生死亡，问：一对刚出生的兔子，一年内繁殖成多少对兔子?

![图片](/uploads/2025-02/278907.jpg)

解：我们可以推算：
①1 月 1 对
②2 月 1 对
③3 月 2 对
④4 月 3 对
⑤5 月 5 对

如下图

![图片](/uploads/2025-02/ee3ceb.jpg)

记第 $n$ 个月的兔子对数为 $F_n$ ，则

$$
F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, \cdots, F_{12}=144 .
$$

这说明，一年过后，一对兔子会变成 144 对兔子．我们用数字将数列 $\left\{F_n\right\}$ 排列出来：

$$
1,1,2,3,5,8,13,21,34,55,89,144,233, \cdots,
$$

就得到了著名的斐波那契数列．
观察上述数列，我们不难发现：

$$
\boxed{
F_n=F_{n-1}+F_{n-2}(n \geqslant 3)
}
$$

这是一个由**递推关系**给出的数列，这也意味着要求 $F_n$ ，需先求 $F_{n-1}$ 和 $F_{n-2}$（如图 2）．

![图片](/uploads/2025-02/07210b.jpg)

> **斐波那契数列转换为数学语言就是：一个函数初始条件$F(0)=0，F(1)=1$, 然后 $F(n) = F(n-1) + F(n-2)$**

然后，就是这么一个看似平淡无奇的数列，却支撑了半个数学的半壁江山。

## 和黄金分割的关系
让我们再把斐波那契数列的签名几项写出来：
$$
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233……
$$

天文学家开普勒研究了该数列后发现，该数列前、后两项之比 $\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 \ldots
$$

这里就引入了另外一个股市：黄金分割点。

### 黄金分割点

公元前4世纪，古希腊数学家欧多克索斯曾提出一个问题：**能否将一条线段分为不相等的两部分，使较长部分为原线段和较短部分的比例中项**， 转换为数学语言就是：给你一条1米长的线段，截取一段为$x$,则剩余一段为$1-x$ ，要求
$\frac{x}{1}=\frac{1-x}{x}$
可以解的$x=0.618$ ,这个 0.618 被称为黄金分割点。有资料记载，早在公元前6世纪，古希腊的毕达哥拉斯学派就发现 $1:0.618$就是黄金分割。
为什么被称为黄金分割点呢？因此生理学家发现，**具有黄金分割点的东西是最美的**。

比如，在人脑的感官里，如果鼻子到发际线的长度和脸的长度比值为 0.618， 人会感觉非常协调，自然是最美的。

![图片](/uploads/2025-05/6880eb.jpg){width=200px}

画家们则发现，按0.618:1来设计的比例，画出的画最优美，古希腊的著名雕像断臂维纳斯通过故意延长双腿，使之与身高的比值为0.618，以达到最美的效果

![图片](/uploads/2025-05/1c1efa.jpg){width=300px}
 
黄金分割具有严格的比例性、艺术性、和谐性，蕴藏着丰富的美学价值，这一比值能够引起人们的美感，被认为是建筑和艺术中最理想的比例。

## 植物生长
植物学家法线，很多植物的生长服从斐波那契数

![图片](/uploads/2025-05/f51515.jpg)
 
观察不同种类的花朵，你会发现它们的花瓣数量常常是斐波那契数！比如：百合有3片花瓣；野玫瑰有5片；雏菊可能有21片、34片，甚至55片，这些数字恰恰都是斐波那契数列中的数字，后来研究表明，**这是因为斐波那契数列能够让花瓣在生长时均匀排列，帮助植物更好地吸收阳光和雨露**。

再如，树苗在第一年长出一条新枝，新枝成长一年后变为老枝，老枝每年都长出一条新枝。每一条树枝都按照这个规律成长，则每年的分枝数正好构成斐波那契数列（如图3）。

![图片](/uploads/2025-02/0517f0.jpg)
 
## 生成函数
斐波那契数，其定义为 $F_0=0$ ， $F_1=1$ ，一般形式为 
 
 $$
 \boxed{
 F_n=F_{n-1}+F_{n-2}
 }
 $$ 
 
 它的前几项是 $0,1,1,2,3,5,8,13, \cdots$ ．
 
 从原则上说，斐波那契数不存在任何奥秘，因为它有明确的公式，我们可以求出序列中的任何项．在实际应用中，这个公式显然不适用于较大的 $n$ ．虽然我们可以求出 $F_{10}=55$ ，但是计算 $F_{100}=354224848179261915075$ 会是件相当乏味无聊的事。如果用纸笔去计算 $F_{2011}$ ，则要引起警觉，因为它超过了 400位数字！
那么，有没有简单、快速计算后续项的方法呢？拉格朗日研究了该数学，提出了生成函数的办法。关于具体推导，可以参考[此处](https://kb.kmath.cn/kbase/detail.aspx?id=2558)

下面是斐波那契数列的通项公式。

$$
\boxed{
F_n=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^n-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^n
}
$$
 
有了通项公式，就可以任意算出数列的第N项，而不用一层层递归计算。

## 与矩阵的关系

斐波那契数列的递推可以用矩阵乘法的形式表达：

$$
\begin{bmatrix}F_{n-1} & F_{n} \cr\end{bmatrix} = \begin{bmatrix}F_{n-2} & F_{n-1} \cr\end{bmatrix} \begin{bmatrix}0 & 1 \cr 1 & 1 \cr\end{bmatrix}
$$

设 $P = \begin{bmatrix}0 & 1 \cr 1 & 1 \cr\end{bmatrix}$，我们得到

$$
\begin{bmatrix}F_n & F_{n+1} \cr\end{bmatrix} = \begin{bmatrix}F_0 & F_1 \cr\end{bmatrix} P^n
$$

于是我们可以用矩阵乘法在 $\Theta(\log n)$ 的时间内计算斐波那契数列。

最终可以求得 $T$ 的本征值和对应本征向量

$$
\left\{\begin{array}{l}
v_1=\left(1, \frac{1+\sqrt{5}}{2}\right), \lambda_1=\frac{1+\sqrt{5}}{2} \\
v_2=\left(1, \frac{1-\sqrt{5}}{2}\right), \lambda_2=\frac{1-\sqrt{5}}{2}
\end{array}\right.
$$

## 斐波那契数列的连分数表示
斐波那契数亦可以用连分数来表示:

$$
\begin{aligned}
& \frac{1}{1}=1 \quad \frac{2}{1}=1+\frac{1}{1} \quad \frac{3}{2}=1+\frac{1}{1+\frac{1}{1}} \quad \frac{5}{3}=1+\frac{1}{1+\frac{1}{1+\frac{1}{1}}} \quad \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]=\frac{\varphi^n}{\sqrt{5}}-\frac{(1-\varphi)^n}{\sqrt{5}}
\end{aligned}
$$

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

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

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

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

## 极坐标与斐波那契图像
有数学家把斐波那契图像的个点画在纸上，然后把各个点连接起来，会发现形成一个螺旋线。 其图像如下

![图片](/uploads/2023-10/118907.jpg){width=300px}

他的形状和自然界生物的生成类似，为研究生物的生成提供了数学依据。

![图片](/uploads/2025-05/19c33c.jpg){width=300px}

## 斐波那契编码

我们可以利用斐波那契数列为正整数编码。根据 [齐肯多夫定理](https://zh.wikipedia.org/wiki/%E9%BD%8A%E8%82%AF%E5%A4%9A%E5%A4%AB%E5%AE%9A%E7%90%86)，任何自然数 $n$ 可以被唯一地表示成一些斐波那契数的和：

$$
N = F_{k_1} + F_{k_2} + \ldots + F_{k_r}
$$

并且 $k_1 \ge k_2 + 2,\ k_2 \ge k_3 + 2,\  \ldots,\  k_r \ge 2$（即不能使用两个相邻的斐波那契数）

于是我们可以用 $d_0 d_1 d_2 \dots d_s 1$ 的编码表示一个正整数，其中 $d_i=1$ 则表示 $F_{i+2}$ 被使用。编码末位我们强制给它加一个 1（这样会出现两个相邻的 1），表示这一串编码结束。举一个例子

**编码过程**：以整数 19 为例：
斐波那契数列：1, 2, 3, 5, 8, 13, 21, ...
找到不大于 19 的最大斐波那契数：13。
减去 13 得 6，继续找 5，剩余 1，最后 1。
编码：101001（从大到小标记选中的数，末尾补 1 表示结束）。

**解码过程** 反向操作：101001 → 13 + 5 + 1 = 19。

这种编码广泛应用在通信行业对数据的编码里。

## 和皮萨诺周期的关系

皮萨诺周期是指斐波那契数列模  $m$  的余数序列的周期性。具体来说，斐波那契数列定义为：
$$
F_0 = 0, \quad F_1 = 1, \quad F_{n} = F_{n-1} + F_{n-2} \quad (n \geq 2)
$$
当我们对斐波那契数列的每一项取模  m  时，得到的余数序列  $F_n \mod m $ 会呈现周期性。这个周期的长度称为皮萨诺周期，记作$ \pi(m)$。

皮萨诺周期可用于构造周期性伪随机数序列,在数论研究里， 有助于理解模运算下的数列行为。

## 和卢卡斯数列的关系

我们有卢卡斯数列的通项公式：

$$
L_n = \left(\frac{1 + \sqrt{5}}{2}\right)^n + \left(\frac{1 - \sqrt{5}}{2}\right)^n
$$

与斐波那契数列非常相似。事实上有：

$$
\frac{L_n + F_n\sqrt{5}}{2} = \left(\frac{1 + \sqrt{5}}{2}\right)^n
$$

也就是说，$L_n$ 和 $F_n$ 恰好构成 $\left(\frac{1 + \sqrt{5}}{2}\right)^n$ 二项式展开再合并同类项后的分子系数。也就是说，Pell 方程

$$
x^2-5y^2=-4
$$

的全体解，恰好是

$$
\frac{x_n + y_n\sqrt{5}}{2} = \frac{L_n + F_n\sqrt{5}}{2}
$$

恰好是卢卡斯数列和斐波那契数列。因此有

$$
{L_n}^2-5{F_n}^2=-4
$$

卢卡斯数列是判定大素数的重要工具。设整系数一元二次方程$x^{2}-Px + Q = 0，(P,Q)=1$的两根为$\alpha，\beta$，则序列$u_{n}$和$v_{n}$称为卢卡斯数列。对于素数$p$，若$u_{l}$是序列$u_{1},u_{2},\cdots$中能被p整除的足标最小的数，则$pu_{n}$的充分必要条件是$l|n$。例如取P = 4，Q = 1，利用卢卡斯数列$v_{0}=2，v_{1}=4，v_{n + 2}=4v_{n + 1}-v_{n}$，可以判别梅森数$2^{q}-1$是否为素数，1930年莱默（D.H.Lehmer）给出的莱默判别法就是利用该数列来进行的。