Hofstadter的非线性递推数列
这篇讲的是Hofstadter G序列——一个由G(n) = n - G(G(n - 1))定义的非线性递推数列。作者从它在《GEB》中的登场出发，揭示了它与斐波那契数列的多重巧妙联系。 序列G生成的树形结构，其每一层节点数恰好构成斐波那契数列。这棵树本身还对应着经典的“兔子繁殖”族谱图。更神奇的是，序列G的值可以通过正整数的Zeckendorf表示（用不重复、不相邻的斐波那契数之和表示）来等价定义：只需将表示式中的每个斐波那契数替换成它前一个数再相加即可。研究还表明，G(n)以黄金比例(√5-1)/2的平均速度线性增长。 文章并未止步于此，而是探索了嵌套更深一层的变体H序列：H(n) = n - H(H(H(n - 1)))。它生成的“奶牛树”同样具有自相似性，并对应着满足不同成熟周期的种群增长模型。H序列遵循类似的规律，但其增长率变为方程x³ + x = 1的正实根，约为0.682。 作者借此展示，简单的递推定义背后，隐藏着从斐波那契数列、黄金比例到整数独特分解的一整套自洽而优美的数学结构。改变递推嵌套的层数，便能系统性地引出一族性质相通但参数平移的序列。