Hofstadter的非线性递推数列

在著名奇书 Gödel, Escher, Bach: An Eternal Golden Braid 的第五章中，为了展现出递推序列的神奇之处，作者 Douglas Hofstadter 定义了这么一个递推序列： G(n) = n – G(G(n – 1)) ，其中 G(1) = 1 。这个序列的前 30 项如下：

这个数列通常被称作 Hofstadter G-sequence 。它有什么特别的地方呢？如上图，如果把每个标号为 n 的结点都连接到标号为 G(n) 的结点下方，这样的话你将会得到一棵树。从第二行开始算起，各行的结点个数依次为 1, 1, 2, 3, 5, 8, 13, … 正好是著名的 Fibonacci 数列（头两个数都是 1 ，从第三个数开始，每个数都是前两个数之和）。如果我们把第 i 个 Fibonacci 数记作 F_i的话，上面的规律可以重新表述为：当 n ≥ 2 时，这棵树的第 n 行的结点总个数为 F_n-1。另外，这棵树的前 n 行的结点总数（也就是第 n 行最右边那个结点的编号）正好等于 F_n+1，也是一个个的 Fibonacci 数。对照上面两个事实，你会惊奇地发现，莫非 F₁+ F₂+ … + F_n-1+ 1 总是等于 F_n+1？事实的确如此，上面这个式子对于所有大于等于 2 的正整数 n 均成立。

这棵树本身还有别的来头。现在，让我们去掉树中最顶上的那个结点，只保留红色方框里的部分。不妨把这部分的图叫做图 R 。有读者发现图 R 很眼熟吗？它正是经典的“兔子问题族谱图”。假如每一对刚生下的幼兔都会在一个月之后变为成兔，并且在此后的每个月里都会生一对新的兔子。如果刚开始有一对幼兔，那么接下来的各个月里将会有多少对兔子？第一个月，就只有一对兔子；第二个月，还是只有一对兔子（不过已经长大了）；第三个月，这对兔子生了一对，于是变为两对兔子；第四个月，这对兔子又生出了一对，于是变为三对兔子。到了第五个月，情况变得有些复杂了，第三个月出生的兔子已经长大了，因而此时一共有了两对成兔。它们将各产生一对新的兔子，从而让第五个月的兔子总数变为五对。继续往下绘制“兔子族谱图”，得到的图形（如下图）将会和图 R 一模一样。各月的兔子对数形成了 Fibonacci 数列： 1, 1, 2, 3, 5, 8, 13, … 。

现在，让我们把图 R 中的最上面那个结点也去掉，只看图中蓝色方框内的部分。不妨把这部分的图叫做图 G 。图 G 具有一种让人更加震撼的结构：去掉 3 和 5 这两个结点后，你将会得到两棵分离的子树，这两棵子树的形状和整个图 G 完全一样，如右图所示。换句话说，图 G 是由它自身的两个拷贝高低错落地拼在一起得到的。 Hofstadter 在书里给出了一个更帅的描述：

现在，大家看到了同一棵树的好几种不同的描述方法，这些描述方法互相之间都是有联系的（其中有一些是非常明显的）。同时，每一种描述方法都给出了一个新的角度，来解释这棵树和 Fibonacci 数之间的联系。

回到数列 G 本身，它也有很多漂亮的等价定义。

任何一个正整数都可以唯一地表示成若干个两两不同并且两两不相邻的 Fibonacci 数之和。例如， 28 就可以写成 21 + 5 + 2 ，其中 21 、 5 和 2 是三个不同的 Fibonacci 数，并且它们是两两不相邻的。注意，为了把 28 写成若干个不同的 Fibonacci 数之和，我们可能还有一些其他的方法，比方说 28 = 13 + 8 + 5 + 2 ，但这里面包含有相邻的 Fibonacci 数，因而是不允许的。给定一个正整数后，为了找到满足要求的分解方案，我们可以简单地采用“贪心算法”：每次都选择尽可能大的 Fibonacci 数即可。例如，最大的不超过 28 的 Fibonacci 数是 21 ，选了 21 之后，我们就还剩下 7 ；最大的不超过 7 的 Fibonacci 数是 5 ，于是接下来我们选择 5 ，剩下一个 2 ；最大的不超过 2 的 Fibonacci 数就是 2 ，于是选完 2 之后，符合要求的分解方案就找到了： 28 = 21 + 5 + 2 。为什么这种算法得到的分解方案是符合要求的，以及为什么不会有其他满足要求的分解方案，可以参见 Wikipedia 的相关条目（http://en.wikipedia.org/wiki/Zeckendorf%27s_theorem）。这种用不重复并且不相邻的 Fibonacci 数之和表示正整数的方法就叫做正整数的 Zeckendorf 表达。好了，有趣的事情出现了，如果把正整数 n 的 Zeckendorf 表达中的每一个 Fibonacci 数都替换成它在 Fibonacci 序列中的前一个数，就会得到 G(n) ！例如， 28 = 21 + 5 + 2 ，把 21 、 5 、 2 分别替换成小一号的 Fibonacci 数，即 13 、 3 、 1 ，重新加起来便得到 13 + 3 + 1 = 17 ，这正好是 G(28) 的值！这可以看作是数列 G 的一个等价的定义。

观察数列 G ，容易看出很多其他的性质。例如，数列 G 从 1 开始逐渐递增，序列中的每个数要么出现了一次，要么出现了两次。考虑两个极端情况，数列 1, 2, 3, 4, 5, 6, … 将会是一个斜率为 1 的线性递增数列，数列 1, 1, 2, 2, 3, 3, 4, 4, … 则将是一个斜率为 0.5 的线性递增数列。因此，数列 G 也是线性递增的，平均增长速度将会介于 1 和 0.5 之间。那么，数列 G 的平均增长速度究竟是多少呢？为此，我们画出 G(n) / n 的图像，结果非常明确： G(n) / n 趋近于 0.618 附近的一个数，这让我们立即联想到黄金比例。

也就是说，数列 G 的平均增长速度是 (√5– 1) / 2 ？在 1984 年的一篇论文中， Downey 和 Griswold 证明了，事实上对于所有的 n ， G(n) 总是等于 ⌊ (n + 1) · (√5– 1) / 2 ⌋ ，其中 ⌊ x ⌋ 表示不超过 x 的最大整数。这可以看作是 G(n) 的另一个等价的定义。可见，数列 G 确实在以 (√5– 1) / 2 的速度增长。

故事远远没有结束。如果修改一下数列 G 的定义，我们又会得到什么呢？在那本庞大而诡异的奇书中， Hofstadter 定义了 G(n) 之后，立即介绍了一个新的数列： H(n) = n – H(H(H(n – 1))) ，其中 H(1) = 1 。注意它和 G(n) 的区别：仅仅是在递推时多嵌套了一层。新的序列的前 30 项如下：

仍然把每个编号为 n 的结点连接到编号为 H(n) 的结点下边，我们将会得到一个新的树形图，不妨就叫做图 H 。从第二行开始，写下各行的结点数量，就会得到下面这个数列： 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, … 。这是什么数列？如果大家经常玩找数列规律的游戏，一定会瞬间看出，这个数列可以看作是 Fibonacci 数列的一种推广：它的头三项都是 1 ，从第四项开始，每一项都是往前数一项和往前数三项这两个数之和。和之前一样，上面这棵树还会从另一方面和该数列发生联系：前 n 行的总结点数，或者说第 n 行的最右侧那个结点的编号，正好是数列中的第 n + 2 个数。如果我们把数列中的第 i 个数记作 C_i的话，我们将会得到下面这个恒等式： C₁+ C₂+ … + C_n-1+ 1 = C_n+2。

树形图 H 本身依旧有很多等价的描述。它仍然具有递归的性质，其构造方法可以简单地概括为上图。它仍然可以看作是一种族谱图，只需要稍加修改即可。据说， 14 世纪印度数学家 Narayana Pandit 曾经提出过“母牛生小牛问题”（做过基础编程练习的朋友或许很熟悉这个问题）：每一只小牛都在两年后长大，并在此之后每一年都会生产一只新的小牛，问今后每一年里都有多少牛。“母牛生小牛问题”和“兔子问题”非常类似，本质上只有一点不同：成熟期从一个单位的时长变成了两个单位的时长。这将导致新的族谱图中每条生命线都会延迟一层才开始出现分岔，于是便得到了新的树形图 H 。各年里牛的数量依次为 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, …，正是刚才的数列 C 。在OEIS（http://oeis.org/A000930）上可以看到，这个数列有一个可爱的名字，叫做 Narayana 奶牛数列。

Zeckendorf 分解的唯一性似乎不再适用于奶牛数列了，用这个数列里的数来表示 15 ，至少有 15 = 13 + 2 和 15 = 9 ＋ 4 ＋ 2 两种方案，这两种分解方案都是合法的，里面没有重复的或者相邻的数。但是，如果我们让选数的限制更加苛刻，要求任意两个所选的数在奶牛数列中都至少间隔两个数（或者说每三个连续的奶牛数当中最多只能选一个数），那么 15 的后一种分解方案就不合法了。事实上，可以证明，在新的限制下，任意整数在奶牛数列中的 Zeckendorf 分解仍然是唯一的，且同样可以用贪心算法获得这一分解方案。据此我们也能得出 H(n) 的等价定义：把正整数 n 的 Zeckendorf 分解方案中的每个数都变成它在奶牛数列中的前一个数，加起来就是 H(n) 的值。例如， 15 = 13 + 2 ，把 13 和 2 分别变成 9 和 1 ，而 9 + 1 = 10 ，这正好是 H(15) 的值。

H(n) / n 的图像显得稍微怪异一些，并趋向于一个约为 0.682 的值，它实际上是 x³+ x = 1 的唯一正实数根。回想一下， G(n) / n 的图像会趋于黄金分割值 (√5– 1) / 2 ，它实际上是 x²+ x = 1 的唯一正实数根！于是你会发现， H(n) 仍然满足 G(n) 所具有的各种性质，只是其中的某个参数在某种意义上平移了一位！

我们自然期待， I(n) = n – I(I(I(I(n – 1)))) 能够继续延续这种规律。我们甚至会设想，如果往反方向走，定义新的数列 F(n) = n – F(n – 1) ，规律是否也在反方向上继续延续。不用怀疑，答案是肯定的。数列 F 将会退化到一种大家非常熟悉的情形，实际分析起来颇有一种亲切感，大家不妨自己试试。

这一切都是为什么呢？大家或许会相信，这背后一定存在一个漂亮而完美的组合解释，可以把刚才观察到的所有现象全都串在一起。不过， Hofstadter 似乎并不这样认为。他冷静地举了一个新的例子来告诉我们，非线性递推序列还可以表现出一些更不可预测的行为。考虑序列 Q(n) = Q(n – Q(n – 1)) + Q(n – Q(n – 2)) ，其中 Q(1) = Q(2) = 1 。这个序列和 Fibonacci 数列的精神非常相似。在 Fibonacci 数列中，为了寻找下一个数是多少，我们总是去看往前 1 个数是多少，往前 2 个数是多少，然后把这两个数加起来。数列 Q(n) 也是类似的，只不过刚才的 1 和 2 变成了变量，由 Q(n – 1) 和 Q(n – 2) 的值来决定。 Q(n) 的前 30 项为：

Q(n) / n 的图像呢？这次就真的怪了：

目前，我们还不知道 Q(n) / n 会趋向于哪个值。事实上，我们还不知道 Q(n) / n 是否会趋向于某个值。事实上，我们甚至还不知道，数列 Q(n) 是否会无限继续下去。如果对于某个 n ， n – Q(n – 1) 或者 n – Q(n – 2) 是一个负数，那么 Q(n) = Q(n – Q(n – 1)) + Q(n – Q(n – 2)) 就不存在了。但目前，没有人能够证明，这样的事情不会发生。

1988 年， John Conway 曾经发现过一个行为更奇怪的非线性递推序列： a(n) = a(a(n – 1)) + a(n – a(n – 1)) ，其中 a(1) = a(2) = 1 。数列的前 30 项为：

a(n) / n 的图像则如下图所示：

这个图像相当出人意料，它包含一段一段跨度逐渐倍增但高度逐渐递减的拱形，每个拱形的样子都有如分形图形一般，且起始坐标和终止坐标正好都是 2 的幂。事实上， Conway 证明了 a(n) / n 最终会无限接近于 1 / 2 ，但在那个计算机还不够强大的年代，我们很难检测出它的收敛速度。 Conway 希望能够找到一个（可能很大的）正整数 N ，使得当 n 增加到了 N 时，今后所有的 a(n) / n 与 1 / 2 的差都小于，比如说， 1 / 20 。 Conway 甚至还悬赏了 10000 美元，奖励给第一个找到满足要求的 N 的人。不久之后，这个奖金由 Collin Mallows 领走，他给出的 N 值为 6 083 008 742 （这段故事还有一个小插曲，感兴趣的读者请搜索查看）。后来发现，其实 N 的值还可以小得多，最小的满足要求的 N 为 1489 。 a(1489) / 1489 = 0.55003358… ，此后的 a(n) / n 就再也没超过 0.55 了。事情传到 Hofstadter 那里之后， Hofstadter 宣称自己早在十多年前就已经发现了这个古怪而有趣的数列。因此，这个数列就叫做 Hofstadter–Conway $10,000 sequence 。

在 MathWorld 上的Hofstadter-Conway $10,000 Sequence（http://mathworld.wolfram.com/Hofstadter-Conway10000-DollarSequence.html）页面当中还给出了一个额外的例子。考虑递推数列 b(n) = b(b(n – 1)) + b(n – b(n – 2) – 1) ， 其中 b(1) = b(2) = 1 。数列的前 30 项为：

b(n) / n 的图像则是我们今天看到的所有图像中最奇异的一个：

很难相信，上图竟然是用一个如此简单的递推式生成的。这种奇妙的感觉就如同 Hofstadter 在 Gödel, Escher, Bach: An Eternal Golden Braid 中第一次介绍 G 数列时所写的那样：“我在研究函数 G 的时候，试图很快地计算它的值，我想到了把已知的值表示成一棵树。使我惊讶的是，这棵树最后竟会有这种极其规则的递归几何描述……递归几何结构有着优美的规则性，恰好与递归代数结构对应在了一起。”