斐波那契数列

斐波那契数列可由两个初始值和一条递推式确定。约定 $F_{1} = F_{2} = 1$ ，从第三项起令 $F_{n} = F_{n - 1} + F_{n - 2}$ ，得到 $1, 1, 2, 3, 5, 8, 13, \dots$ 。有些资料改用 $F_{0} = 0, F_{1} = 1$ ；两种编号给出的后续数字相同，引用公式时应先看从哪一项开始编号。

两项记忆的递推

要算 $F_{6}$ ，只需要前两项 $F_{4} = 3, F_{5} = 5$ ，所以 $F_{6} = 8$ 。但要从头开始计算，两个初始值都不可省。与等差数列的固定差、等比数列的固定比不同，这里增量 $F_{n} - F_{n - 1} = F_{n - 2}$ 本身在变化。

下图用边长为 1、1、2、3、5 的正方形拼成不断扩大的长方形。从第三块起，新正方形的边长等于前两块的边长之和；颜色只是帮助沿拼接顺序追踪数字。图形展示递推可以怎样出现，并不负责证明每个斐波那契恒等式。

依次拼接边长为一、一、二、三、五的五块正方形，每块边长标注数字并形成逐步扩大的长方形 — 沿着 1、1、2、3、5 的边长读拼图，可见新边长由前两次的长度相加。

前 n 项和

前几项相加有 $1 = F_{3} - 1$ 、 $1 + 1 = F_{4} - 1$ 、 $1 + 1 + 2 = F_{5} - 1$ 。这提示 $F_{1} + F_{2} + \dots + F_{n} = F_{n + 2} - 1 (n \geq 1) .$ 这些小例子只能帮助猜测。用数学归纳法证明： $n = 1$ 时两边同为 1。若前 $n$ 项之和为 $F_{n + 2} - 1$ ，再加入 $F_{n + 1}$ ，便得到 $F_{n + 2} + F_{n + 1} - 1 = F_{n + 3} - 1$ 。最后一步恰好使用递推式，因此结论对所有正整数 $n$ 成立。

例如前六项之和 $1 + 1 + 2 + 3 + 5 + 8 = 20$ ；公式给 $F_{8} - 1 = 21 - 1 = 20$ 。若误把 $F_{n + 1} - 1$ 写在右边， $n = 2$ 就会得到错误的 1，低下标核对能及时发现错位。

比值与极限

相邻项的比值依次为 $1, 2, 3 / 2, 5 / 3, 8 / 5, \dots$ ，并不恒定。若它趋于正数 $r$ ，递推式除以 $F_{n}$ 提示 $r = 1 + 1 / r$ ，正根为 $φ = (1 + \sqrt{5}) / 2$ 。这个方程只求出可能的极限，还需要证明比值真的收敛。

可以进一步求通项来完成证明。令 $ψ = (1 - \sqrt{5}) / 2$ ，则 $φ^{2} = φ + 1$ 、 $ψ^{2} = ψ + 1$ 。因此两个数列 $φ^{n}$ 、 $ψ^{n}$ 都满足“后一项等于前两项之和”的递推。它们的线性组合 $G_{n} = \frac{φ^{n} - ψ^{n}}{\sqrt{5}}$ 也满足同一递推，并且 $G_{0} = 0, G_{1} = 1$ 。与约定 $F_{0} = 0, F_{1} = 1$ 的斐波那契数列有相同起点和规则，归纳得到 $G_{n} = F_{n}$ 。又因 $| ψ / φ | < 1$ ， $\frac{F_{n + 1}}{F_{n}} = φ \frac{1 - (ψ / φ)^{n + 1}}{1 - (ψ / φ)^{n}} ⟶ φ .$ 通项看起来含无理数，但两个幂的差按递推必给出整数；收敛结论来自 $(ψ / φ)^{n} \to 0$ ，而不只是数表外观。

试算。已知 $F_{7} = 13, F_{8} = 21$ ，不用重算前六项，求前八项之和。递推给 $F_{9} = 34, F_{10} = 55$ ，所以 $S_{8} = F_{10} - 1 = 54$ 。

参考资料

OpenStax《Precalculus 2e》§11.1：递推定义与斐波那契数列。