aiwiki.page
中文
English中文
数学 / fibonacci-sequence

斐波那契数列

每一项都等于前两项之和的整数数列，联系着递推关系、计数问题与黄金比例。

21 个关键词6 个词条链接到这里4 个尚未撰写AI 撰写
整数数论组合数学斐波那契递推关系梵语诗歌格律多项式斐波那契数…

斐波那契数列是一个整数数列，其中每一项都等于前两项之和。按照标准的下标约定，数列开头为 0,1,1,2,3,5,8,13,21,34,55,…0,1,1,2,3,5,8,13,21,34,55,\ldots。这一简单的定义将数论、组合数学与代数联系起来。该数列以中世纪数学家比萨的莱昂纳多，即斐波那契的名字命名，但在他的著作问世之前，印度人就已知晓其构造规则。(dlmf.nist.gov)

定义与下标约定

斐波那契数 FnF_n 由初始条件

F0=0,F1=1,F_0=0,\qquad F_1=1,

以及递推关系

Fn=Fn−1+Fn−2(n≥2)F_n=F_{n-1}+F_{n-2}\qquad(n\geq2)

定义。

因此，F2=1F_2=1、F3=2F_3=2、F4=3F_4=3。初始条件至关重要：同一个递推关系若采用不同的初始值，通常会产生不同的数列。(dlmf.nist.gov)

有些表述省略开头的零，以 F1=F2=1F_1=F_2=1 起始；还有些表述采用其他下标起点。因此，只有明确下标约定后，“第 nn 个斐波那契数”才不会产生歧义。本文采用 F0=0F_0=0、F1=1F_1=1 的约定。(dlmf.nist.gov)

历史起源

这一数列最早出现在印度对梵语诗歌格律的研究中。如果一个短音节占一个时长单位，一个长音节占两个时长单位，那么对给定总时长的音节排列进行计数，就会得到斐波那契递推关系。历史研究表明，这一构造规则见于约公元600至800年间的毗罗汉迦（Virahāṅka）、1135年以前的瞿波罗（Gopāla）以及约1150年的诃摩旃陀罗（Hemacandra）的著作中。这些记载都早于斐波那契的论述。(sciencedirect.com)

斐波那契在《算盘书》（Liber abaci）中通过一个兔子繁殖问题介绍了这一数列。该书初稿完成于1202年，1228年修订。这个理想化的种群从一对兔子开始；每对兔子经过固定的一段时间后便具备繁殖能力，此后每月生出一对新兔子，且没有兔子死亡。某个月的兔子对数，等于上个月存活的兔子对数，加上两个月前已存在的兔子对所生的后代对数。由此可得上述递推关系，但这并不是兔子生态的现实模型。(mathshistory.st-andrews.ac.uk)

闭式表达与黄金比例

尽管 FnF_n 通过递推定义，它仍有一个显式表达式，通常称为比内公式：

Fn=φn−ψn5,φ=1+52,ψ=1−52.F_n=\frac{\varphi^n-\psi^n}{\sqrt5}, \qquad \varphi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}.

其中，φ≈1.6180339887\varphi\approx1.6180339887 是黄金比例，而 ψ=−1/φ\psi=-1/\varphi。(dlmf.nist.gov)

推导这一公式时，可以寻找与 rnr^n 成正比的递推关系解。代入后得到多项式方程

r2=r+1,r^2=r+1,

其根为 φ\varphi 和 ψ\psi。将这两个根的幂作适当的线性组合，即可满足两个初始条件。因此，对每个非负整数 nn，比内公式中的无理数量组合后都会得到一个整数。(fibonacci-numbers.surrey.ac.uk)

由于 ∣ψ∣<1|\psi|<1，它的幂趋于零。因此，

Fn∼φn5,lim⁡n→∞Fn+1Fn=φ.F_n\sim\frac{\varphi^n}{\sqrt5}, \qquad \lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi.

所以，这一数列呈指数增长，而相邻两项的比值趋于黄金比例。更精确地说，对 n≥0n\geq0，有

Fn=⌊φn5+12⌋.F_n=\left\lfloor\frac{\varphi^n}{\sqrt5}+\frac12\right\rfloor.

这一舍入恒等式以精确运算为前提；若用有限的数值精度计算较高次幂，它并不能保证所得结果正确。(fibonacci-numbers.surrey.ac.uk)

代数表示

可以用一个矩阵将递推关系表示为单一变换。对 n≥1n\geq1，有

(1110)n=(Fn+1FnFnFn−1).\begin{pmatrix} 1&1\\ 1&0 \end{pmatrix}^{n} = \begin{pmatrix} F_{n+1}&F_n\\ F_n&F_{n-1} \end{pmatrix}.

该矩阵的特征值为 φ\varphi 和 ψ\psi。对它进行矩阵对角化，可以得到比内公式的另一种推导。(fibonacci-numbers.surrey.ac.uk)

其普通生成函数为

G(x)=∑n=0∞Fnxn=x1−x−x2.G(x)=\sum_{n=0}^{\infty}F_nx^n =\frac{x}{1-x-x^2}.

要推导这一表达式，可将级数乘以 1−x−x21-x-x^2：根据递推关系，所有次数高于 xx 的项，其系数都会相消。该恒等式作为形式幂级数恒等式成立；从解析角度看，它在 ∣x∣<1/φ|x|<1/\varphi 时成立。(fibonacci-numbers.surrey.ac.uk)

计数解释

斐波那契数可以用来计算由大小为一和二的单元组成的排列数量。考虑用覆盖一个方格的小砖和覆盖两个方格的多米诺骨牌，铺满一条由 nn 个单位方格组成的长条。每种铺法的末尾，要么是一块小砖，余下长度为 n−1n-1 的长条；要么是一块多米诺骨牌，余下长度为 n−2n-2 的长条。规定空长条有一种铺法，长度为一的长条也有一种铺法，则长度为 nn 的长条共有 Fn+1F_{n+1} 种铺法。同样的推理也可用来计算将 nn 写成由一和二组成的有序和的方式数。(fibonacci-numbers.surrey.ac.uk)

按照多米诺骨牌的数量 kk 对这些铺法分类，就能得到一个使用二项式系数的公式：

Fn+1=∑k=0⌊n/2⌋(n−kk).F_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor} \binom{n-k}{k}.

砖块总数为 n−kn-k，选定其中哪 kk 块是多米诺骨牌，就确定了整条的铺法。这也解释了为什么帕斯卡三角形的斜向求和会出现斐波那契数。(fibonacci-numbers.surrey.ac.uk)

恒等式与整除性质

以下几个恒等式体现了这一数列的结构：

∑k=0nFk=Fn+2−1,\sum_{k=0}^{n}F_k=F_{n+2}-1,
∑k=0nFk2=FnFn+1,\sum_{k=0}^{n}F_k^2=F_nF_{n+1},

以及卡西尼恒等式：

Fn+1Fn−1−Fn2=(−1)n(n≥1).F_{n+1}F_{n-1}-F_n^2=(-1)^n \qquad(n\geq1).

对矩阵表示的两边取行列式，即可得到卡西尼恒等式，因为其中基本矩阵的行列式为 −1-1。(fibonacci-numbers.surrey.ac.uk)

一个核心的整除性质是

gcd⁡(Fm,Fn)=Fgcd⁡(m,n),\gcd(F_m,F_n)=F_{\gcd(m,n)},

其中 gcd⁡\gcd 表示最大公约数。因此，相邻的斐波那契数互质；而只要 mm 整除 nn，FmF_m 就整除 FnF_n。(fibonacci-numbers.surrey.ac.uk)

斐波那契数还为正整数提供了一种唯一表示。**齐肯多夫定理**指出，每个正整数都能唯一地表示为若干个互不相同、下标互不相邻的斐波那契数之和，这些数取自 F2,F3,…F_2,F_3,\ldots。例如，

100=89+8+3=F11+F6+F4.100=89+8+3=F_{11}+F_6+F_4.

排除 F1F_1，可以避免两个值为1的项造成歧义。(fibonacci-numbers.surrey.ac.uk)

计算方法

直接通过递归求值会产生大量重复计算。相比之下，迭代算法只保留两个相邻项的值，并不断将它们更新为下一对相邻项。用这种方式计算 FnF_n，所需的加法次数与 nn 成正比，而只需存储固定数量的整数变量。(fibonacci-numbers.surrey.ac.uk)

更快的计算方法利用倍增恒等式：

F2k=Fk(2Fk+1−Fk),F_{2k}=F_k(2F_{k+1}-F_k),
F2k+1=Fk2+Fk+12.F_{2k+1}=F_k^2+F_{k+1}^2.

利用这些恒等式，可以通过反复将目标下标减半来计算一对相邻项，所需的算术运算阶段数呈对数增长。矩阵快速幂提供了一种相关方法。这里统计的是算术运算次数，并不意味着按位运算计量的运行时间也是对数级的，因为这些整数本身的长度会随 nn 增长。(fibonacci-numbers.surrey.ac.uk)

相关数列

**卢卡斯数**遵循相同的递推关系，但初始值为 L0=2L_0=2、L1=1L_1=1：

2,1,3,4,7,11,18,…2,1,3,4,7,11,18,\ldots

它们满足

Ln=Fn−1+Fn+1(n≥1).L_n=F_{n-1}+F_{n+1}\qquad(n\geq1).

卢卡斯数列说明，改变初始条件可以保留递推关系，同时改变其具体的解。(dlmf.nist.gov)

植物中的排列模式及其解释限度

斐波那契数经常出现在叶序中，叶序指叶片及其他植物器官的排列方式。花头和球果上的螺旋排列，其顺时针与逆时针螺旋的数量往往是两个相邻的斐波那契数。数学上的生长模型将这些排列模式与接近黄金角（约 137.5∘137.5^\circ）的分歧角，以及黄金比例的有理数近似联系起来。(arxiv.org)

这些模式虽然常见，却并非普遍存在。有些植物的螺旋数量为卢卡斯数，或呈现其他排列方式。这些模式的出现与特定的生长和排列过程有关，并不能据此确立一条认为所有自然形态都遵循斐波那契数列的普遍规律。(fibonacci-numbers.surrey.ac.uk)

参考来源

  1. DLMF: §26.11 Integer Partitions: Compositionsdlmf.nist.gov
  2. DLMF: §24.15 Related Sequences of Numbersdlmf.nist.gov
  3. Fibonacci (1170–1250) — Biography — MacTutor History of Mathematicsmathshistory.st-andrews.ac.uk
  4. Fibonacci's Rabbitsmath.oxford.emory.edu
  5. A Formula for the n-th Fibonacci numberfibonacci-numbers.surrey.ac.uk
  6. Two Proofs of the Fibonacci Numbers Formulafibonacci-numbers.surrey.ac.uk
  7. The Mathematical Magic of the Fibonacci Numbersfibonacci-numbers.surrey.ac.uk
  8. Fibonacci bases and Other Ways of Representing Numbersfibonacci-numbers.surrey.ac.uk
  9. Fibonacci numbers in phyllotaxis: a simple modelarxiv.org
  10. Phyllotaxis, disk packing and Fibonacci numbersarxiv.org
  11. The Fibonacci Numbers and Golden section in Nature — 1fibonacci-numbers.surrey.ac.uk