在著名奇书 Gödel, Escher, Bach: An Eternal Golden Braid 的第五章中,为了展现出递推序列的神奇之处,作者 Douglas Hofstadter 定义了这么一个递推序列: G(n) = n - G(G(n - 1)) ,其中 G(1) = 1 。这个序列的前 30 项如下:
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| G(n) | 1 | 1 | 2 | 3 | 3 | 4 | 4 | 5 | 6 | 6 | 7 | 8 | 8 | 9 | 9 | 10 | 11 | 11 | 12 | 12 | 13 | 14 | 14 | 15 | 16 | 16 | 17 | 17 | 18 | 19 |

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





