不过，故事还远远没有结束。刚才我们给出了序列 W 的前几项，那时候你或许就已经发现了什么。让我们再多往后写几项：
(1, 2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15), (11, 18), (12, 20), (14, 23), (16, 26), (17, 28), (19, 31), (21, 34), (22, 36), (24, 39), (25, 41), (27, 44), (29, 47), (30, 49), …
你发现了什么？有没有觉得， (1, 2) 、 (3, 5) 、 (8, 13) 、 (21, 34) 这几项都特别熟悉？没错，如果把 Fibonacci 数列里的数都依次写下来：
1, 2, 3, 5, 8, 13, 21, 34, …
然后把它们两个两个分成一组：
(1, 2), (3, 5), (8, 13), (21, 34), …
由此得到的所有数对都在序列 W 当中！事实上，我们还能预测出，上述数对都出现在了序列 W 当中的什么位置。 (1, 2) 后面的那个数对是 (3, 5) ，它就是 W 当中的第 2 个数对； (3, 5) 后面的那个数对是 (8, 13) ，它就是 W 当中的第 5 个数对； (8, 13) 后面的那个数对是 (21, 34) ，它就是 W 当中的第 13 个数对……所以， (21, 34) 后面的那个数对，就应该是 W 当中的第 34 个数对咯？简单算算你会发现，嘿，还真是！根据定义， W 当中的第 34 个数对为 [34 · φ], [34 · φ2] ，而 34 · φ ≈ 55.013 ，34 · φ2 ≈ 89.013 ，取整后正好就是 (55, 89) 。你或许会猜测，该不会当 n 是 Fibonacci 数时， [n · φ] 和 [n · φ2] 一定就是后面两个 Fibonacci 数吧。事实上并非如此。让我们代入 n = 21 看看： 21 · φ ≈ 33.979 ， 21 · φ2 ≈ 54.979 ，所得到的两个数确实很接近 21 后面的两个 Fibonacci 数，但却要偏小一些。因此，取整之后的结果是 33 和 54 ，而并不是 34 和 55 。这一切都是为什么呢？
这一切都是因为， Fibonacci 数列有一个神奇的通项公式： φn / √5 – (1 – φ)n / √5 。注意，这个充满无理数的通项公式生成的并不是 Fibonacci 数的近似值，它生成的真的就是一个个的 Fibonacci 数。你可以试着把 n = 1, 2, 3, 4, 5, 6 代进去，得到的值将会精确地等于 1, 1, 2, 3, 5, 8 。
由于 φ ≈ 1.618 ，其绝对值大于 1 ，因此随着 n 的增加， φn / √5 的绝对值将会迅速变得非常非常大；由于 1 – φ ≈ – 0.618 ，其绝对值小于 1 ，因此随着 n 的增加， (1 – φ)n / √5 的绝对值将会迅速变得非常非常接近于 0 。最终， φn / √5 – (1 – φ)n / √5 将会无限接近于 φn / √5 ，一个以 φ 为公比的等比数列。这就解释了，为什么一个 Fibonacci 数的 φ 倍大致就等于下一个 Fibonacci 数。
但是，用这种方法推算出来的下一个 Fibonacci 数，究竟会偏大一些还是偏小一些呢？我们还得仔细分析一下误差。注意到 1 – φ 是个负数，因此随着 n 的增加， (1 – φ)n / √5 实际上是在正负交替地向 0 靠拢，因此 φn / √5 – (1 – φ)n / √5 实际上是在一上一下地无限接近于 φn / √5 。下表中的第一行依次是各个 Fibonacci 数，第二行是 n = 1, 2, 3, … 时 φn / √5 的值，第三行则是二者之间的误差。
![]()
这就回到了我们刚才观察到的现象：序列 W 中的第 2 个数对是 (3, 5) ，第 5 个数对是 (8, 13) ，第 13 个数对是 (21, 34) ，第 34 个数对是 (55, 89) ……我们也就算是证明了刚才提到的结论：把 Fibonacci 数列写下来，并且从 (1, 2) 开始，每两个数组成一个数对，则由此得到的所有数对都在序列 W 当中。这就解释了，为什么 34 · φ 和 34 · φ2 正好比 55 和 89 稍大一些。 34 和 55 非常接近 φ9 / √5 和 φ10 / √5 的值，其中后者是前者的 φ 倍。但 34 等于 φ9 / √5 加上某个很小的数， 55 等于 φ10 / √5 减去某个很小的数，因而 34 的 φ 倍就会比 55 略大一些了。 34 和 89 也都非常接近 φ9 / √5 和 φ11 / √5 的值，其中后者是前者的 φ2 倍。但 34 等于 φ9 / √5 加上某个很小的数， 89 等于 φ11 / √5 加上某个更小的数，因而 34 的 φ2 倍也会比 89 略大一些。类似地， 21 · φ 和 21 · φ2 正好比 34 和 55 稍小一些，也是因为 21 等于 φ8 / √5 减去某个很小的数， 34 等于 φ9 / √5 加上某个很小的数， 55 等于 φ10 / √5 减去某个更小的数。
于是，我们挖的坑又只剩最后一个了：为什么 φn / √5 – (1 – φ)n / √5 是 Fibonacci 数列的通项公式呢？这有一个非常具有启发性的推导方法。
让我们把满足递推式 a(n) = a(n – 1) + a(n – 2) 的数列叫作“广义 Fibonacci 数列”。而真正的 Fibonacci 数列，则可以看作是由初始条件 a(1) = 1 和 a(2) = 1 生成的。首先注意到，让广义 Fibonacci 数列里的每一项都乘上非 0 实数 c ，得到的仍然是一个广义 Fibonacci 数列。也就是说，如果数列
a(1), a(2), a(3), a(4), a(5), …
是一个由 a(1) 和 a(2) 生成的广义 Fibonacci 数列，那么
c · a(1), c · a(2), c · a(3), c · a(4), c · a(5), …
就是一个由 c · a(1) 和 c · a(2) 生成的广义 Fibonacci 数列。
另外，两个广义 Fibonacci 数列之和必然也是一个广义 Fibonacci 数列。也就是说，如果数列
a(1), a(2), a(3), a(4), a(5), …
是一个由 a(1) 和 a(2) 生成的广义 Fibonacci 数列，并且数列
b(1), b(2), b(3), b(4), b(5), …
是一个由 b(1) 和 b(2) 生成的广义 Fibonacci 数列，那么数列
a(1) + b(1), a(2) + b(2), a(3) + b(3), a(4) + b(4), a(5) + b(5), …
就是一个由 a(1) + b(1) 和 a(2) + b(2) 生成的广义 Fibonacci 数列。
最后， φ 和 1 – φ 是方程 1 + x = x2 的两根，因而数列
φ, φ2, φ3, φ4, φ5, φ6, …
和
1 – φ, (1 – φ)2, (1 – φ)3, (1 – φ)4, (1 – φ)5, (1 – φ)6, …
就成了两个非常特别的广义 Fibonacci 数列。
把上面三点结合起来，我们将会得出结论：对于任意的实数 k 、 l ，数列
k · φ + l · (1 – φ), k · φ2 + l · (1 – φ)2, k · φ3 + l · (1 – φ)3, k · φ4 + l · (1 – φ)4, …
都是一个广义 Fibonacci 数列。如果我们能找出合适的 k 和 l ，使得它们同时满足
k · φ + l · (1 – φ) = 1, k · φ2 + l · (1 – φ)2 = 1
这两个方程，那么我们就相当于找到了 Fibonacci 数列的通项公式。解得 k = 1 / √5, l = – 1 / √5 ，因而 Fibonacci 数列实际上就是
φ / √5 – (1 – φ) / √5, φ2 / √5 – (1 – φ)2 / √5, φ3 / √5 – (1 – φ)3 / √5, φ4 / √5 – (1 – φ)4 / √5, …
这就是 Fibonacci 数列的通项公式。容易看出，事实上，一切的广义 Fibonacci 数列都可以表示成
k · φ + l · (1 – φ), k · φ2 + l · (1 – φ)2, k · φ3 + l · (1 – φ)3, k · φ4 + l · (1 – φ)4, …
的形式，我们只需要求解关于 k 和 l 的二元一次方程组
k · φ + l · (1 – φ) = a(1), k · φ2 + l · (1 – φ)2 = a(2)
即可。因此，各种广义 Fibonacci 数列也将继承 Fibonacci 数列的很多宏观特征。比方说，随着 n 的增加， k · φn 的绝对值将会迅速变得非常非常大（即使 k 本身的绝对值很小）， l · (1 – φ)n 的绝对值将会正负交替地迅速向 0 靠拢（即使 l 本身的绝对值很大），最终 k · φn + l · (1 – φ)n 将会一上一下地无限靠近 k · φn 。也就是说，足够多项之后，一切广义 Fibonacci 数列都会一上一下地无限近似于一个以 φ 为公比的等比数列。
Fibonacci 数列有很多神奇之处，它的通项公式只是其中之一。每次说到 Fibonacci 数列时，我都喜欢讲讲 Fibonacci 数列的另一个神奇之处，就是 Zeckendorf 定理。这是由比利时数学家 Edouard Zeckendorf 发现的：任何一个正整数都可以唯一地表示成若干个不相邻的 Fibonacci 之和。例如，100 可以表示成 89 + 8 + 3 。我们把正整数的这种表示方法叫作它的 Zeckendorf 表达。注意，虽然 100 也可以表示成 55 + 34 + 8 + 2 + 1 ，但 55 和 34 是相邻的 Fibonacci 数， 2 和 1 也是相邻的 Fibonacci 数，因此这不能算 100 的 Zeckendorf 表达。需要特别指出的是，由于 F1 和 F2 都是 1 ，因此选了 F1 和 F3 本质上就相当于选了 F2 和 F3 ，根据规定，这也是不允许的。因此，接下来，我们假设每次选 1 的时候选的实际上都是 F2 ，这不会改变问题的实质。换句话说，接下来，我们假设 F1 是不能选的。
为什么 Zeckendorf 表达总是存在的呢？这很容易看出来。只要不断地选取尽可能大的 Fibonacci 数，我们就能得到一个 Zeckendorf 表达。比如，如何得出 100 的一个 Zeckendorf 表达呢？不超过 100 的最大的 Fibonacci 数是 89 。从 100 里减去 89 后，剩下的部分是 11 。不超过 11 的最大的 Fibonacci 数是 8 。从 11 里减去 8 后，剩下的部分是 3 ，这已经是一个 Fibonacci 了。所以， 100 的 Zeckendorf 表达就是 89 + 8 + 3 。在这个过程中，我们肯定不会用到相邻的 Fibonacci 数。这是因为，如果正整数 N 介于 Fi 和 Fi+1 之间（其中 Fi 表示第 i 个 Fibonacci 数），那么我们就有：
N – Fi i+1 – Fi = Fi-1
这说明，减去一个尽可能大的 Fibonacci 数，结果会比小一号的 Fibonacci 数更小。所以，在上面这种寻找 Zeckendorf 表达的过程中，我们会自动地跳过所有相邻的 Fibonacci 数。
Zeckendorf 定理真正最核心的，就是每一个正整数的 Zeckendorf 表达都是唯一的。为了证明这一点，让我们先来考虑两个问题。第一个问题是：从 F2, F3, …, Fn 数中选出若干个不相邻的数，怎样选才能让它们的和最大呢？不断把较小的 Fibonacci 数往大了调，你会发现，和最大的选法显然就是
Fn + Fn-2 + Fn-4 + …
如果 n 是偶数，上式将会以 … + F4 + F2 结尾。如果 n 是奇数，上式将会以 … + F5 + F3 结尾。这个数究竟等于多少呢？这个数与 Fn+1 很接近。这是因为：
Fn+1
= Fn + Fn-1
= Fn + Fn-2 + Fn-3
= Fn + Fn-2 + Fn-4 + Fn-5
= ……
不断像这样展开后，根据 n 的奇偶性的不同，我们要么会得到 Fn + Fn-2 + Fn-4 + … + F4 + F2 + F1 ，要么会得到 Fn + Fn-2 + Fn-4 + … + F5 + F3 + F2 。不管是哪种情况，这都比刚才选出的最大和多了一个 1 。也就是说，从 F2, F3, …, Fn 中选出若干个不相邻的数，最大的和为 Fn+1 – 1 。
我们需要考虑的第二个问题是， n 个物体排成一排，从中选出若干个不相邻的物体（可以不选），一共有多少种不同的方案？不妨把答案记作 a(n) 。如果只有 1 个物体，我们要么选它，要么不选它，一共有 2 种选法。如果有 2 个物体，我们要么选这个，要么选那个，要么都不选，一共有 3 种选法。也就是说， a(1) = 2 ， a(2) = 3 。另外，面对 n 个物体，满足要求的选法分为两类：如果不选最后那个物体，那就完全得看前 n – 1 个物体怎么选，这里面的方案数为 a(n – 1） ；如果选了最后那个物体，那么剩下的就只能再在前 n – 2 个物体里选了，这里面的方案数为 a(n – 2) 。这说明， a(n) = a(n – 1) + a(n – 2) 。于是，数列 a(1), a(2), a(3), a(4), … 实际上就是 2, 3, 5, 8, …。换句话说， a(n) = Fn + 2
结合上面两点，我们得到了这样一个结论：从 F2 到 Fn 这 n – 1 个数中选出若干个不相邻的数（可以不选），一共有 Fn+1 种选法；而这些数的总和的取值范围，则在 0 到 Fn+1 – 1 之间。所以，我们有 Fn+1 种选法，有 Fn+1 种可能的取值。另一方面，我们之前证明了，每个正整数都有至少一个 Zeckendorf 表达。所以， Fn+1 种选法必须得既无重复又无遗漏地取遍 Fn+1 种可能的取值。这就说明了，每一个正整数的 Zeckendorf 表达都是唯一的。
等等，我们是怎么扯到 Zeckendorf 表达的？让我想一想啊……哦！想起来了！想起来了！我们是从棋盘游戏，扯到与之等价的 Wythoff 游戏，扯到哪些状态后行者必胜，扯到 Wythoff 所定义的序列 W ，扯到序列 W 包含了一对一对的 Fibonacci 数，扯到 Fibonacci 数列那著名的通项公式，最后扯到了正整数的 Zeckendorf 表达。
扯远了，扯远了。我们再把整个思路捯回去。序列 W 的公式为：
([1 · φ], [1 · φ2]), ([2 · φ], [2 · φ2]), ([3 · φ], [3 · φ2]), ([4 · φ], [4 · φ2]), …
由此算出序列 W 的前几项：
(1, 2), (3, 5), (4, 7), (6, 10), (8, 13), (9, 15), (11, 18), (12, 20), (14, 23), (16, 26), (17, 28), (19, 31), (21, 34), (22, 36), (24, 39), (25, 41), (27, 44), (29, 47), (30, 49), …
我们证明了，序列 W 满足以下三个重要的性质：
性质 1 ： W 里面正好既无重复又无遗漏地包含了每一个正整数
性质 2 ： W 当中各项里的两数之差依次为 1, 2, 3, …
性质 3 ： W 当中各项里的较小数依次递增
这三个性质保证了， W 当中的所有项正好是 Wythoff 游戏中后行者必胜的所有状态。然后，我们发现 W 当中有很多项里包含了 Fibonacci 数。把它们连在一起，正好就是完整的 Fibonacci 数列：
(1, 2), (3, 5), (8, 13), (21, 34), …
其中 (1, 2) 后面的 (3, 5) 正好是 W 当中的第 2 项， (3, 5) 后面的 (8, 13) 正好是 W 当中的第 5 项， (8, 13) 后面的 (21, 34) 正好是 W 当中的第 13 项，以此类推。
那么， W 当中的其他项呢？仔细观察 W 当中的其他项，你能看出什么端倪吗？答案是， W 当中的其他项还隐藏着别的广义 Fibonacci 数列！比方说， W 当中的
(4, 7), (11, 18), (29, 47), …
正好拼成一个以 4, 7 打头的广义 Fibonacci 数列！而且， (11, 18) 就是 W 当中的第 7 项， (29, 47) 就是 W 当中的第 18 项。来猜猜看， (76, 123) 会不会正好是 W 当中的第 47 项？计算可得 47 · φ ≈ 76.0476 ， 47 · φ2 ≈ 123.048 。根据序列 W 的定义，第 47 项真的就是 (76, 123) ！
接下来，我们就来证明这件事：如果 (a, b) 是序列 W 中的某个数对，那么序列 W 中的第 b 项就是 (a + b, a + 2b) 。由于第 b 项里的两数之差就是 b ，因此我们只需要证明：如果 (a, b) 是序列 W 中的某个数对，那么序列 W 中的第 b 项的较小数就是 a + b 。不妨假设 (a, b) 是序列 W 中的第 n 项。根据序列 W 的定义， a 就等于 [n · φ] ， b 就等于 [n · φ2] ，而第 b 项的较小数则是 [[n · φ2] · φ] 。所以，我们真正只需要证明的就是：对于任意正整数 n ，都有 [n · φ] + [n · φ2] = [[n · φ2] · φ] 。这本质上就是证明：
[n · φ] + [n · φ2] ≤ [n · φ2] · φ 2] + 1
不妨用 {x} 表示 x 的小数部分。上式就变为了
n · φ – {n · φ} + n · φ2 – {n · φ2} ≤ (n · φ2 – {n · φ2}) · φ 2 – {n · φ2} + 1
也就是：
n · φ – {n · φ} + n · φ2 – {n · φ2} ≤ n · φ3 – {n · φ2} · φ 2 – {n · φ2} + 1
然而， φ 满足 1 + φ = φ2 ，也就满足 n · φ + n · φ2 = n · φ3 。于是，上面的不等式进一步简化为
– {n · φ} – {n · φ2} ≤ – {n · φ2} · φ 2} + 1
即
{n · φ} + {n · φ2} ≥ {n · φ2} · φ > {n · φ} + {n · φ2} – 1
最后，别忘了 φ 和 φ2 正好相差 1 ，因而 n · φ 和 n · φ2 正好相差一个整数，也就是说它们的小数部分是相等的。如果令它们的小数部分均为 r ，则上式变为
2 · r ≥ r · φ > 2 · r – 1
由于 r 是一个 0 到 1 之间的数，而 φ ≈ 1.618 ，所以上式显然成立。至此，我们就证明了，对于任意正整数 n ，都有 [n · φ] + [n · φ2] = [[n · φ2] · φ] 。
利用取整符号和常数 φ ，我们还能构造出很多类似的恒等式。用上面的这套方法来证明这些恒等式，则显得格外有效。为了说明这一点，我打算不惜文章的连贯性，在此处穿插一个习题。这是我最近见到的一个题目。讲完这个题目的解法后，我们会立即言归正传。题目是：求证，对于任意正整数 n ，都有 [[n · φ] · φ] = [n · φ2] – 1 。
解法和之前的几乎如出一辙。原等式等价于
[n · φ2] – 1 ≤ [n · φ] · φ 2]
它又可以变成
n · φ2 – {n · φ2} – 1 ≤ (n · φ – {n · φ}) · φ 2 – {n · φ2}
即
n · φ2 – {n · φ2} – 1 ≤ n · φ2 – {n · φ} · φ 2 – {n · φ2}
即
– {n · φ2} – 1 ≤ – {n · φ} · φ 2}
即
{n · φ2} + 1 ≥ {n · φ} · φ > {n · φ2}
由于 {n · φ} = {n · φ2} ，因此我们把它们都换成 r 。整个式子就变为了：
r + 1 ≥ r · φ > r
同样地，由于 r 是一个 0 到 1 之间的数，而 φ ≈ 1.618 ，所以上式显然成立。
如果序列 W 当中有 (a, b) 和 (a + b, a + 2b) 这么两项，我们就说， (a + b, a + 2b) 接在 (a, b) 后面。而我们刚才证明的实际上就是，序列 W 当中的第 [1 · φ2], [2 · φ2], [3 · φ2], … 项将会分别接在第 1, 2, 3, … 项的后面。把该接起来的数对全都接起来，我们就会得到很多链条，比如之前就已经观察到的
(1, 2), (3, 5), (8, 13), (21, 34), …
和
(4, 7), (11, 18), (29, 47), …
显然，每个链条里的数都构成了一个广义 Fibonacci 数列。而每个链条打头的数对，则是那些不能接在任何数对后面的数对，也就是第 [1 · φ2], [2 · φ2], [3 · φ2], … 项以外的数对。由 Beatty-Rayleigh 定理可知，它们正好就是 W 当中的第 [1 · φ], [2 · φ], [3 · φ], … 项。所以，我们把 W 当中的第 [1 · φ], [2 · φ], [3 · φ], … 项竖着写成一列，再不断地写出每个数对后面接着的数对，就能完整地给出 W 当中的数对产生的所有链条了。联想到 W 里面既无重复又无遗漏地包含了每一个正整数，因而我们相当于把全体正整数排成了一张无限大的数表，每个正整数都恰好只用了 1 次，使得数表中的每一行都是一个广义 Fibonacci 数列！我们把这个神奇的数表叫作 Wythoff 数表。
(1, 2) – (3, 5) – (8, 13) – (21, 34) – (55, 89) – (144, 233) – …
(4, 7) – (11, 18) – (29, 47) – (76, 123) – (199, 322) – (521, 843) – …
(6, 10) – (16, 26) – (42, 68) – (110, 178) – (288, 466) – (754, 1220) – …
(9, 15) – (24, 39) – (63, 102) – (165, 267) – (432, 699) – (1131, 1830) – …
(12, 20) – (32, 52) – (84, 136) – (220, 356) – (576, 932) – (1508, 2440) – …
(14, 23) – (37, 60) – (97, 157) – (254, 411) – (665, 1076) – (1741, 2817) – …
(17, 28) – (45, 73) – (118, 191) – (309, 500) – (809, 1309) – (2118, 3427) – …
… … … … … … …
真正神奇的事情出现了。现在，我们约定，接下来所说的广义 Fibonacci 数列一律限定在正整数范围内。如果两个广义 Fibonacci 数列的本质完全相同，只是下标被整体平移了一下，我们就认为它们俩是同一个数列。比方说，以 2, 1 打头的广义 Fibonacci 数列（这叫作 Lucas 数列）为：
2, 1, 3, 4, 7, 11, 18, 29, 47
它就是 Wythoff 数表中的第二行。接下来，我们来证明一个非常让人震惊的事实：在这个意义下， Wythoff 数表包含了所有可能的广义 Fibonacci 数列！
证明方法很简单。还记得吗，我们之前曾经得出，一切广义 Fibonacci 数列最终都会一上一下地无限地近似于一个以 φ 为公比的等比数列。所以，如果 a(1), a(2), a(3), … 是一个广义 Fibonacci 数列，那么我们一定能在找到某个 n ，使得 a(n + 1) = [a(n) · φ] ，并且 a(n + 2) = [a(n) · φ2] 。然而， ([a(n) · φ], [a(n) · φ2]) 就是序列 W 当中的第 a(n) 项，它出现在了 Wythoff 数表的某一行里。这一行所对应的广义 Fibonacci 数列，本质上就是数列 a(1), a(2), a(3), … 。
我们证明了一个如此优美的结论，将之前的所有东西都贯穿在了一起，一切都非常漂亮地完结了。再来一个简单的收尾后，这篇文章就该结束了。毕竟，我们之前挖过的所有坑都填上了，我们之前提过的所有东西都用到了。呃……是吗？
编故事有一个非常重要的原则，叫作“契科夫之枪”（Chekhov’s gun）。它说的是：如果你在第一章里提到了墙上挂着一把来复枪，那在第二章或者第三章里面它一定会开火，否则它就不应该挂在那里。举个例子：主人公踏上征途之前，一哥们儿给他递上一件东西并说：“把这个带上吧，没准儿能用上……”好，这玩意儿百分之百地会被用上。如果故事片里有一个镜头专门对着播报新闻的电视，记住了，这肯定和剧情有联系。如果枪战片里的人来到一个大房间，四壁都是养着鱼的大水缸……呵呵，我不说你都知道一会儿会出现啥。
这篇文章也挂着好几把契科夫之枪。比方说，刚才突然来的那个习题是怎么回事？在那个习题中，我们证明了 [[n · φ] · φ] = [n · φ2] – 1 恒成立。好了，现在考虑 Wythoff 数表的第 n 行，它是一个广义 Fibonacci 数列。如果再把这个数列往前推两项，会得到什么？注意到， Wythoff 数表的第 n 行是以序列 W 当中的第 [n · φ] 项打头的。也就是说， Wythoff 数表的第 n 行的头两个数是 [[n · φ] · φ], [[n · φ] · φ2] 。由于一个数的 φ 倍和 φ2 倍（以及它们同时取整后的结果）正好相差这个数本身这么多，因此 [[n · φ] · φ2] – [[n · φ] · φ] = [n · φ] ，并且 [[n · φ] · φ] – [n · φ] = [n · φ2] – 1 – [n · φ] = n – 1 。这就说明， Wythoff 数表的第 n 行可以看作是由 n – 1, [n · φ] 生成的广义 Fibonacci 数列。所以，我们得到了 Wythoff 数表的一个等价定义：在第 -1 列依次写下 0, 1, 2, 3, … ，在第 0 列对应地依次写下 [1 · φ], [2 · φ], [3 · φ], … ，于是每一行里都有两个数了；在每一行里都不断往后面写下新的数，每个数都是它的前面两个数之和，最后得到的就是 Wythoff 数表——它既无重复又无遗漏地包含了所有正整数，也既无重复又无遗漏地包含了所有广义 Fibonacci 数列。![]()
还记得 Zeckendorf 表达吗？接下来，该轮到它返场了！现在我们定义，把一个正整数的 Zeckendorf 表达里的所有 Fibonacci 数都往后移一位，得到的新的正整数就是原正整数的 “Fibonacci 后继” 。例如， 100 的 Zeckendorf 表达是 89 + 8 + 3 ，其中 89 的下一个 Fibonacci 数是 144 ， 8 的下一个 Fibonacci 数是 13 ， 3 的下一个 Fibonacci 数是 5 。那么， 100 的 Fibonacci 后继就是 144 + 13 + 5 ，也就是 162 。我们用 S(n) 来表示正整数 n 的 Fibonacci 后继。刚才我们演示的就是， S(100) = 162 。接下来，我们将证明这么一个结论：对于任意正整数 n 都有， 1 + S(n) 等于 [(n + 1) · φ] 。
如果 n 的 Zeckendorf 表达中各个 Fibonacci 数的下标为 i1, i2, i3, … ，令
X = φi1 + φi2 + φi3 + …
令
Y = (1 – φ)i1 + (1 – φ)i2 + (1 – φ)i3 + …
那么 n 就可以写成
X / √5 – Y / √5
由于 1 – φ 是一个绝对值小于 1 的负数，因而当 i1, i2, i3, … 正好是全体正偶数时， Y 的值达到最大。利用等比数列的求和公式可知， Y 的最大值是 φ – 1 ≈ 0.618 。对应地，当 i1, i2, i3, … 正好是全体大于 1 的正奇数时， Y 的值则达到最小（注意，在 Zeckendorf 表达里， Fibonacci 数的下标不能取 1 ）。利用等比数列的求和公式可知， Y 的最小值是 φ – 2 ≈ – 0.382 。当然，对于任意一个有限大的 n 来说，刚才算出的最大值和最小值都是取不到的。
为了把 n 变成 S(n) ，我们只需要把 X 里的每一个 φ 和 Y 里的每一个 (1 – φ) 的指数都变大一号即可。于是， 1 + S(n) 就可以表示为：
1 + φ · X / √5 – (1 – φ) · Y / √5
而我们要证明 1 + S(n) = [(n + 1) · φ] ，也就是
1 + φ · X / √5 – (1 – φ) · Y / √5 = [φ · X / √5 – φ · Y / √5 + φ]
由于等式左边的式子是一个整数，因此我们只需要证明等式右边的取整符号内的式子比等式左边的式子更大，但不会大 1 或更多。也就是说，我们只需要证明：
0 ≤ (φ · X / √5 – φ · Y / √5 + φ) – (1 + φ · X / √5 – (1 – φ) · Y / √5)
而
(φ · X / √5 – φ · Y / √5 + φ) – (1 + φ · X / √5 – (1 – φ) · Y / √5)
= (1 – φ) · Y / √5 – φ · Y / √5 + φ – 1
= (1 – 2φ) · Y / √5 + φ – 1
是一个关于 Y 的一次函数，且当 Y = φ – 2 时函数值为 1 ， Y = φ – 1 时函数值为 0 。这就说明，这个一次函数的函数值永远在 0 和 1 之间。至此，我们就证到了， 1 + S(n) 等于 [(n + 1) · φ] 。
之前我们提到了 Wythoff 数表的等价定义：在第 -1 列依次写下 0, 1, 2, 3, … ，在第 0 列对应地依次写下 [1 · φ], [2 · φ], [3 · φ], … ，然后每一行都不断往后面接着写，使得每个数都是它的前面两个数之和。由于 1 + S(n) 等于 [(n + 1) · φ] ，因此上面这个等价定义可以进一步改成：在第 -1 列依次写下 0, 1, 2, 3, … ，在第 0 列对应地依次写下 1 + S(0), 1 + S(1), 1 + S(2), … （这里，我们规定 S(0) = 0 ），然后每一行都不断往后面接着写，使得每个数都是它的前面两个数之和。
所以，第 1 列的数就应该依次为 0 + (1 + S(0)), 1 + (1 + S(1)), 2 + (1 + S(2)), … 。仔细想一想， n + (1 + S(n)) 究竟是什么？容易观察到， n + S(n) 的 Zeckendorf 表达与 n 的 Zeckendorf 表达有非常直接的联系。如果 n 等于 Fi1 + Fi2 + … + Fik ，那么 S(n) 就等于 Fi1+1 + Fi2+1 + … + Fik+1 ，于是 n + S(n) 就等于 Fi1+2 + Fi2+2 + … + Fik+2 。可见， n + S(n) 的 Zeckendorf 表达就是 n 的 Zeckendorf 表达中所有 Fibonacci 数都往后移两位而得的，显然它里面不包含 F2 和 F3 ，最小的一项至少都是 F4 。因此，为了得到 n + (1 + S(n)) 的 Zeckendorf 表达，我们只需要在 n + S(n) 的 Zeckendorf 表达里直接添加一个 F2 就行了。
举个例子，如果某一行的第 -1 个数是 F2 + F4 + F9 ，那么第 0 个数就是 1 + F3 + F5 + F10 ，第 1 个数就是 F2 + F4 + F6 + F11 。那么，这一行的第 2 个数是多少呢？由于第 2 个数是第 0 个数和第 1 个数之和，因此第 2 个数就是 F3 + F5 + F7 + F12 ，其中 1 和 F2 合并后得到了 F3 。类似地，由于第 3 个数是第 1 个数和第 2 个数之和，因此第 3 个数就是 F4 + F6 + F8 + F13 ；由于第 4 个数是第 2 个数和第 3 个数之和，因此第 4 个数就是 F5 + F7 + F9 + F14 ……规律已经非常明显了：在 Wythoff 数表当中，每一行的第 1 个数的 Zeckendorf 表达的最小项都是 F2 ，并且今后的每一个数都是它前一个数的 Fibonacci 后继，其 Zeckendorf 表达的最小项依次升级为 F3, F4, F5, … ！
回想 Wythoff 数表最早最早的定义：不断把那些不能接在任何数对后面的数对拎出来打头所得的一行一行的链条。因此，每一行打头的数都是在前面从来没有出现过的数中最小的数。所以，我们有了一种另类的生成 Wythoff 数表的方式。先在第一行的开头写下 1 。在它的右边不断写下 S(1), S(S(1)), S(S(S(1))), … 此时，在所有仍未出现的数中，最小的数是 4 。接下来，我们就在第二行的开头写下 4 ，并在它的右边不断写下 S(4), S(S(4)), S(S(S(4))), … 。此时，在所有仍未出现的数中，最小的数是 6 。接下来，我们就在第三行的开头写下 6 ，并在它的右边不断写下 S(6), S(S(6)), S(S(S(6))), … 。此时，在所有仍未出现的数中，最小的数是 8 。接下来，我们就在第四行的开头写下 8 ……不断这样做下去，我们就会得到一张无限大的数表，它就是 Wythoff 数表。这是 Wythoff 数表的另一个等价定义。
另外， Wythoff 数表的第 -1 列为 0, 1, 2, 3, … ，第 0 列依次为 [1 · φ], [2 · φ], [3 · φ], … ，这两列都是递增的。第 1 列的数等于第 -1 列的数和第 0 列的数之和。由于大点儿的数加上大点儿的数，和肯定也会更大，所以第 1 列的数也是递增的。同理，第 2 列，第 3 列，以至于今后的每一列，都是递增的。于是， Wythoff 数表还有这么一种生成方式：在第 1 列从小到大列出所有 Zeckendorf 表达的最小项为 F2 的数，在第 2 列从小到大列出所有 Zeckendorf 表达的最小项为 F3 的数，在第 3 列从小到大列出所有 Zeckendorf 表达的最小项为 F4 的数……不断这样做下去，我们就会得到一张无限大的数表，它就是 Wythoff 数表。这是 Wythoff 数表的又一个等价定义。
最后让我们回到“挪动皇后”和 Wythoff 游戏。 Wythoff 游戏的所有后行者必胜的状态构成了序列 W ，它的公式为：
([1 · φ], [1 · φ2]), ([2 · φ], [2 · φ2]), ([3 · φ], [3 · φ2]), ([4 · φ], [4 · φ2]), …
反过来，如果你面对的状态在序列 W 以外，那么你就是必胜的。但是，必胜的策略是什么呢？必胜的策略自然就是，把当前状态变成序列 W 当中的某个状态。但是，到时候你怎么才能算出，究竟应该变成序列 W 当中的哪个状态呢？早些时候，我们证明了，变法确实是存在的（见序列 W 所满足的第 3 个条件）。但是，利用当时的证明方法，很难得出一套固定的、易实施的具体策略，可以帮我们每次都准确地找出这个变法。毕竟，在没有高精度计算器的情况下，你甚至连 W 里的每一项具体是多少都搞不出来。然而，最后那几个 Wythoff 数表的等价定义是非常离散的，这给上述问题的解决开辟了一条新路。比如，我们可以立即得出，数对 (a, b) 在序列 W 当中，当且仅当 a 的 Zeckendorf 表达的最小项的下标是一个偶数，并且 b = S(a) 。所以，我们就有了一种判断数对是否在 W 当中的方法。刚才证明过恒等式 1 + S(n) = [(n + 1) · φ] ，据此可以推出 S(n – 1) + 1 = [n · φ] ；于是，序列 W 当中的第 n 项就是 (S(n – 1) + 1, S(S(n – 1) + 1)) 。再结合之前给出的序列 W 满足条件 3 的证明，最终得出的结论将会正好与 1977 年 Robert Silber 对 Wythoff 游戏的分析结果完全一致：若数对 (a, b) 不在序列 W 当中（其中 0
若 a 的 Zeckendorf 表达的最小项的下标是一个奇数，则把 b 变成 S-1(a) 。这里 S-1(x) 表示把 x 的 Zeckendorf 表达里的所有 Fibonacci 数都往前移一位之后得到的结果。
若 a 的 Zeckendorf 表达的最小项的下标是一个偶数，并且 b > S(a) ，则 b 变成 S(a) 。
若 a 的 Zeckendorf 表达的最小项的下标是一个偶数，并且 b
在写这篇文章的过程中，我看了很多资料。 1907 年， Willem Abraham Wythoff 在 A Modification of the Game of Nim 一文中提出了 Wythoff 游戏。 1977 年， Robert Silber 在 Wythoff’s NIM and Fibonacci Representations 一文中给出了基于 Fibonacci 数的分析。 Martin Gardner 在 Penrose Tiles to Trapdoor Ciphers 一书中对它们做了介绍。这三位作者的名字之前都有提过。 Wythoff 数表最早是 1980 年由 David Morrison 在 A Stolarsky Array of Wythoff Pairs 一文中提出的。它和 Zeckendorf 表达的关系则可以参见 Clark Kimberling 的 The Zeckendorf Array Equals the Wythoff Array 一文。与 Zeckendorf 表达本身有关的一些证明，尤其是 Zeckendorf 定理的证明，参考了 Tamás Lengyel 的 A Counting Based Proof of the Generalized Zeckendorf’s Theorem 一文。利用取整符号和常数 φ 能够构造出很多的恒等式，其证明方法参考了 Ian Connell 的 Some Properties of Beatty Sequences I 一文。我最早是因为看了 Neil Sloane 的 My Favorite Integer Sequences 一文后，了解到 Wythoff 数表，才打算写这篇文章的。为了把这一切联系在一起，形成一篇完整的文章，我写下了很多自己的理解，甚至有些地方的证明过程也是我自己的思考。如果有不对的地方，请网友们及时提出。
在数学世界里，各种数学研究对象织成了一张纵横交错的大网，捡石子游戏、 Wythoff 数表和 Fibonacci 数列只是其中的三个非常小的顶点而已。 2 万多字之后，我们终于把它们之间的种种关系理了个半清。但是，它们各自还能继续向外延伸，这些恐怕再花 20 万字也说不完。 Wythoff 游戏是 Nim 游戏的一个变种，后者在组合游戏理论中占据着非常核心的地位。对 Wythoff 游戏本身进行推广，还可以得到一系列类似的游戏。例如，把两堆石子换成三堆石子、四堆石子甚至 n 堆石子，情况又会怎样？很多数学家都对此有过研究。本文提到了 Wythoff 数表的很多令人意想不到的等价定义和非常让人震撼的数学性质，但这并不是 Wythoff 数表的全部。例如，在 Wythoff 数表中，下一行的每个数的大小正好夹在上一行数的空隙之间。这背后会涉及到非常有趣的 interspersion 和 dispersion 理论。 Wythoff 数表里既无重复又无遗漏地包含了所有正整数，那么从 1 开始的每个正整数究竟出现在了 Wythoff 数表中的哪一行呢？这个问题的答案就又构成了一个数列：
0, 0, 0, 1, 0, 2, 1, 0, 3, 2, 1, 4, 0, 5, 3, 2, 6, 1, 7, 4, …
这里我们规定， Wythoff 数表的首行为第 0 行。这个数列本身又有很多可圈可点之处，例如删掉数列中的第一个 0 、第一个 1 、第一个 2 等等，剩下的数列其实就是原数列本身。因此，这个数列具有分形的特征！当然，考察每个正整数究竟出现在了 Wythoff 数表中的哪一列，我们又可以得到一个数列，它也有很多独特的性质。
