字符串 hello 当中连续出现了两个 l 。字符串 prototype 当中连续出现了两个 ot 。字符串 nonsense 当中连续出现了两个 nse 。如果某个字符串中连续出现了两个相同的片段，换句话说这个字符串里面含有形如 XX 的模式（其中 X 代表一个子串），我们就说这个字符串中含有一个“平方”（square）。如果某个字符串中没有平方出现，我们就说这个字符串是“免平方”的（square-free）。
如果只使用两种字符，比方说字符 0 和字符 1 的话，我们只能构造出一些长度非常有限的免平方字符串。事实上，我们只能构造出以下 6 个免平方字符串： 0 、 1 、 01 、 10 、 010 、 101 。然而，如果允许使用三种字符，比方说字符 0 、 1 、 2 的话，我们不但能够构造出任意长的免平方字符串，还能构造出无限长的免平方字符串。在继续阅读下去之前，你不妨先自己试试看。
你或许熟知一个非常经典的结论： Fibonacci 数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … （头两项都是 1 ，此后每一项都是前两项之和）的相邻两项之比将会越来越接近黄金比例 0.618 ，不信请看：
1 / 1 = 1.0000000…
1 / 2 = 0.50000000…
2 / 3 = 0.66666667…
3 / 5 = 0.60000000…
5 / 8 = 0.62500000…
8 / 13 = 0.61538462…
13 / 21 = 0.61904762…
21 / 34 = 0.61764706…
34 / 55 = 0.61818182…
55 / 89 = 0.61797753…
89 / 144 = 0.61805556…
144 / 233 = 0.61802575…
… …
Fibonacci 数列究竟是怎么和黄金比例扯上关系的？一个简单的解释就是，假设相邻两项之比存在一个极限，那么到了无穷远的时候，连续的三个数 a, b, a + b 将会满足 a / b = b / (a + b) ，这正好就是黄金比例的定义。我最近用 Mathematica 做了一组动画，尝试着用图形化的方法更直观地展示 Fibonacci 数列和黄金比例之间的联系。
在著名奇书 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 均成立。
数列 1, 1, 2, 3, 5, 8, 13, 21, 34, … 叫做 Fibonacci 数列。这个数列有很多神奇的性质，其中一个性质是，每一个 Fibonacci 数的平方与它前后两个 Fibonacci 数的乘积一定正好相差 1 。具体地说，如果把第 n 个 Fibonacci 数记做 Fn ，那么有：
Fn+1 · Fn+1 – Fn · Fn+2 = (-1)n
今天看到了这个定理的一个组合数学证明，觉得非常有意思，在这里和大家分享。
今天听说了 Conway’s Soldiers ，这是 Conway 大牛在 1961 年提出的一个数学谜题（似乎 Conway 的出镜率也太高了），我觉得非常有意思，在这里跟大家介绍一下。内容基本上来自于 Wikipedia 的相关页面。
假设有一个无限大的棋盘。棋盘上可以放置一些象征着士兵的棋子。一个棋子可以跳过并吃掉和它相邻的一枚棋子（就像孔明棋一样）。这是棋子的唯一一种移动方式。现在，在某个位置画一条无限长的水平线，你需要在水平线下面放置足够多的棋子，使得它们前仆后继地往水平线上方跳，最终能够跳到水平线以上 n 个单位的位置。
如图所示，当 n = 1 时，两个棋子就够了。当 n = 2 时，我们需要 4 个棋子。当 n = 3 时，最少需要 8 个棋子。