斐波那契数列

观察

固定 $L = 6$ ，把切口 $m$ 从 $1$ 拖到 $5$ 。总数一直是 $13$ ，两堆的大小却在变。公式里的两个乘积是不是始终等于两堆的数目？
看第二堆（跨过切口的那一堆）：被描深的那一对横牌，总是盖住第 $m$ 列和第 $m + 1$ 列。拿走它，剩下的是两段更短的长条。
把 $m$ 拖到 $1$ 。等式变成了什么？你应该认出它：这就是斐波那契数列的递推式 $F_{L + 1} = F_{L} + F_{L - 1}$ 。
取 $L = 7$ 、 $m = 3$ 。等式右边两个乘积里都有同一个因数 $F_{4} = 3$ 。这说明 $F_{8}$ 是 $F_{4}$ 的倍数——这不是巧合。

斐波那契数列 ${F_{n}}$ ： $F_{1} = F_{2} = 1$ ， $F_{n + 2} = F_{n + 1} + F_{n}$ 。用 $1 \times 2$ 的骨牌铺 $2 \times n$ 的长条，铺法数恰好是 $F_{n + 1}$ ：看最右边，竖放一块剩 $2 \times (n - 1)$ ，横放两块剩 $2 \times (n - 2)$ 。上面的观察合起来，就是一条“加法公式”：

F_{p + q} = F_{p} F_{q + 1} + F_{p - 1} F_{q} .

先猜后证

2×8 的长条一共有 $F_{9} = 34$ 种铺法。在第 $4$ 列后面切一刀，切口干净（没有横牌跨过切口）的铺法有多少种？

种

先选定答案，才能看到结论。

为什么

“数两次”：同一批铺法，先整体数，再按切口处的样子分两堆数。

加法公式：在长条上切一刀

第 1 / 6 步

要数的东西
2×7 的长条有 $F_{8} = 21$ 种铺法。我们在第 $m$ 列后面画一条虚线，问：铺法在这条线上断开还是连着？

$F_{8} = 21$
切口干净的一堆
跨过切口的一堆
两堆加起来
取 m = 1
取 p = q

再往前走一步，就得到斐波那契数列最漂亮的性质：求两项的最大公约数，可以转到下标上去求。

整除与最大公约数

第 1 / 4 步

先证：倍数下标的项是倍数
对 $k$ 归纳。 $k = 1$ 显然。若 $F_{n} ∣ F_{k n}$ ，在加法公式里取 $p = k n$ ， $q = n$ ：两项都含因数 $F_{n}$ 。

$F_{(k + 1) n} = F_{k n} F_{n + 1} + F_{k n - 1} F_{n}$
相邻两项互质
下标做一次“减法”
辗转相除搬到下标上

正方形拼长方形

边长为 $1, 1, 2, 3, 5, \dots$ 的正方形，一块接一块贴在已有图形的长边上，总能严丝合缝地拼成一个长方形。加一块正方形，图形的两条边就从 $F_{n - 1}, F_{n}$ 变成 $F_{n}, F_{n + 1}$ ——这正是递推式。数面积：

F_{1}^{2} + F_{2}^{2} + \dots + F_{n}^{2} = F_{n} F_{n + 1} .

右下角的读数是相邻两项的比

F_{n + 1} / F_{n}

。把

n

一格一格加大，它在

φ = \frac{1 + 5}{2}

的两侧来回跳，越跳越近。

先猜后证

$\frac{F _{n + 1}}{F _{n}}$ 依次是 $\frac{1}{1}, \frac{2}{1}, \frac{3}{2}, \frac{5}{3}, \frac{8}{5}, \dots$ 。它和 $φ \approx 1.618$ 的差，正负号怎样变化？

一直比

φ

小一直比

φ

大一次小、一次大，交替出现

先选定答案，才能看到结论。

如果去掉一个条件

Break it

反例实验室：去掉一个条件

结论： $G_{1}^{2} + \dots + G_{n}^{2} = G_{n} G_{n + 1}$ ，正方形拼成长方形

斐波那契数列的前两项都是 $1$ ：第二块正方形正好贴满第一块的一条边，此后每一块都贴得严丝合缝。

练一练

练习 1基础

求 $F_{1} + F_{2} + \dots + F_{10}$ 。

练习 2基础

用 $1 \times 2$ 的骨牌铺满 $2 \times 9$ 的长条，有多少种铺法？

练习 3提高

求 $F_{24}$ 与 $F_{36}$ 的最大公约数。

练习 4挑战

证明：对一切正整数 $n$ ， $F_{n + 1}^{2} - F_{n} F_{n + 2} = (- 1)^{n}$ 。

观察

为什么

加法公式：在长条上切一刀

整除与最大公约数

正方形拼长方形

如果去掉一个条件

反例实验室：去掉一个条件

练一练

错误博物馆 · 本站展品

铺法数和斐波那契数差一个下标

把“必要条件”当成“充分条件”