1.1 河内塔 THE TOWER OF HANOI
河内塔问题
Step 1: 引入记号
用$T_n$表示将$n$个圆盘从一根柱子上移动到另一根柱子上的最小移动次数
Step 2: 考虑小的情形
$T_1$显然是1，而$T_2=3$。当然，数学家还会考虑$T_0$的情况，虽然它的结果只是0。
Step 3: 考虑大的情形
一方面，要将$n$个圆盘移动到另一个柱子上，像移动3个圆盘一样，可以采取这样的办法：先将上面的$n-1$个圆盘移动到不同的柱子上(需要$T_{n-1}$次移动)，然后移动最大的圆盘，再将那$n-1$个小圆盘移动到最大圆盘的上面(也需要$T_{n-1}$次移动)。这样，至多需要$2T_{n-1}+1$次移动就能移动$n(n>0)$个圆盘了。即
$$T_n \le 2T_{n-1}+1 , \quad n>0$$
另一方面，上面的式子中用的是$\le$号，那么，有更好的方法吗？实际上没有，我们迟早要移动那个最大的圆盘，而在这之前，那$n-1$个小圆盘已经按次序放在某个柱子上(这至少需要T_{n-1}次移动)。我们至少需要1次才能将最大的圆盘移动到目标柱子上，这之后，我们还必须把那$n-1$个小圆盘移动到大圆盘上面(而这也至少需要T_{n-1}次移动)。从而
$$T_n \ge 2T_{n-1}+1 , \quad n>0$$
把这两个不等式和$T_0$结合起来就得到了
$$ T_0 = 0$$
$$T_n = 2T_{n-1}+1 , \quad n>0 \tag{1.1}$$
像式(1.1)这样的一组等式称为递归式。它给出一个边界值，以及一个用前面的值给出一般值的方程。
然而，我们对这个结果还不够满意，希望能得出递归式的解（一个漂亮的封闭形式，即$T_n = \cdots$），这样，我们就可以快捷计算$T_n$。
封闭形式粗略的定义：如果可以利用至多固定次数(其次数与$n$无关)的初等运算来计算量$f(n)$的表达式，那么这个表达式就是封闭形式。
一种办法是猜出正确的解，而猜测解的最好办法就是研究小的情形。例如：$T_3 = 2 \times 3+1=7$，$T_4=2\times 7+1=15$，$T_5=2 \times 15+1=31$，$T_6=2 \times 31+1=63$。这看起来像是有
$$T_n=2^n-1,\quad n \ge 0$$
至少这对$n \le 6$是成立的。
数学归纳法
数学归纳法是证明某个命题对所有满足 $n\ge n_0$ 的整数都成立的一般方法，首先我们在 $n$ 取最小值 $n_0$ 时证明该命题，这一步称为基础；然后对 $n>n_0$ ，假设命题对 $n_0$ 与 $n-1$ 之间（包含它们在内）的所有值都已经被证明，再证明该命题对 $n$ 成立，这一步称为归纳。这一种证明办法仅用有限步就得到无限多个结果。用数学归纳法可以将上面的猜想进行证明，而不仅仅停留在 $n\le 6$。
基础是显然的：$T_0=2^0-1=0$
对$n>0$用归纳法就得出$T_n = 2T_{n-1}+1 = 2(2^{n-1}-1)+1 = 2^n-1$
在上面的河内塔问题研究中，我们经过了如下三个阶段：
- 研究小的情形，这有助于下面两个阶段的研究
- 对有意义的量求出数学表达式并给出证明。在河内塔问题中，即递归式
- 对数学表达式求出封闭形式并予以证明
事实上，我们关心的往往是第三阶段。通常情况下，我们没有聪明到可以猜想出正确的结果，这时候就需要一些普适性的、不需要超人洞察力的方法。
1.2 约瑟夫问题 THE JOSEPHUS PROBLEM
在犹太罗马战争期间，有41名犹太反抗者困在了被罗马人包围的洞穴中。这些反抗者宁愿自杀也不愿意被活捉，于是决定围成一个圆圈，并沿着圆圈每隔两人杀死一个人，直到剩下最后两个人为止。但是，约瑟夫和另一个未被告发的同谋者不希望无谓地自杀，于是他迅速计算出他和其朋友在这个圆圈中该站的位置，使得他们俩是最后被杀的两个人。
我们简化一下这个问题：从围成标有记号$1$到$n$的圆圈的$n$个人开始，每隔一个删去一个人，直到只有一个人幸存下来。例如n=10时，下图是起始图形：
消去的顺序是2，4，6，8，10，3，7，1，9，于是5幸存了下来。求：幸存者的号码$J(n)$
从上面的例子中可以看出，$J(10)=5$，那么我们可以猜想对偶数有$J(n)=\frac{n}{2}$，对几个小情形进行研究，便很容易发现这个猜想是错的
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| $J(n)$ | 1 | 1 | 3 | 1 | 3 | 5 |
从上面的表格中可以看出，$J(n)$似乎总是奇数，这一点不难解释：在第一圈中，所有偶数号码都被消除了。此外，如果$n$是偶数，那么除了人数仅剩下一半且他们的号码有变化之外，我们得到的是与一开始类似的情形。假设一开始有$2n$个人，经过一轮剩下的是：
3号就是下一个要离开的人，除了每个人的号码加倍并减去1外，这正像$n$个人开始时的情形。就是说：$$J(2n)=2J(n)-1 , n \ge 1$$
那么我们就可以很快地计算出$J(40)=2J(20)-1=2(2J(10)-1)-1=17$
对于奇数的情形，一开始有$2n+1$个人，所以标号为1的人会在标号为$2n$的人后面被删除，剩下的是：
这仍与$n$个人开始的情形很相似，但这一次他们的号码加倍并增加了1，从而有：$$J(2n+1)=2J(n)+1 , n \ge 1$$
综合$J(1)=1$我们得到了在所有情形下定义$J(n)$的递归式：
$$
\begin{array}{}
J(1)=1 \\
J(2n)=2J(n)-1 , \qquad n \ge 1 \\
J(2n+1)=2J(n)+1 , \quad n \ge 1
\end{array} \tag{1.8}
$$
有了这个递归式，我们很快就能算出$n$很大时$J(n)$的值，比如$J(1000000)$只需要19次计算就能得出。然而，这离我们想要的封闭表达式还有很大距离。不过，有了递归表达式，我们可以很快的给小的情形做一张表：
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | ||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $J(n)$ | 1 | 1 | 3 | 1 | 3 | 5 | 7 | 1 | 3 | 5 | 7 | 9 | 11 | 13 | 15 | 1 |
看来可以按照2的幂将表中的数据分组（表中用空格隔开），在每一组的开始$J(n)$总是等于1，并且组里的数据每次递进2。因此，如果我们将$n$写成$n=2^m+l$的形式，其中$2^m$是不超过$n$的2的最大幂，而$l$是剩下的数，那么递归式的解看起来是：
$$J(2^m+l)=2l+1 , \quad m \ge 0 , 0 \le l < 2^m \tag{1.9}$$
接下来要证明式(1.9)。对$m$用数学归纳法，当$m=0$时必然有$l=0$，故基础$J(1)=1$是成立的。接下来，归纳证明分两个部分，按照$l$是偶数还是奇数而定。如果$m>0$且$2^m+l=2n$，那么$l$是偶数，则有：
$$J(2^m+l)=2J(2^{m-1}+l/2)-1=2(2l/2+1)-1=2l+1$$
当$2^m+l=2n+1$为奇数时，则有：
$$J(2^m+l)=2J(2^{m-1}+(l-1)/2)+1=2(2(l-1)/2+1)+1=2l+1$$
这样，就完成了归纳法，证明了式(1.9)
推广研究
函数$J(n)$到底是什么？
在我们的求解过程中，2的幂起着重要的作用，所以不妨试试研究$n$和$J(n)$的以2为基数的表示。假设$n$的二进制展开式为：
$$n=(b_mb_{m-1} \cdots b_1b_0)_2$$
也就是说：
$$n=b_m2^m+b_{m-1}2^{m-1}+ \cdots +b_12+b_0$$
其中每个$b_i$为0或1，而首位数字$b_m$是1。注意$n=2^m+l$，我们依次就有：
$$\begin{aligned}{}
n=(1b_{m-1}b_{m-2} \cdots b_1b_0)_2 \\\
l=(0b_{m-1}b_{m-2} \cdots b_1b_0)_2 \\\
2l=(b_{m-1}b_{m-2} \cdots b_1b_00)_2 \\\
2l+1=(b_{m-1}b_{m-2} \cdots b_1b_01)_2 \\\
J(n)=(b_{m-1}b_{m-2} \cdots b_1b_01)_2
\end{aligned}$$
于是我们就证明了
$$J((b_mb_{m-1} \cdots b_1b_0)_2)=(b_{m-1}b_{m-2} \cdots b_1b_0b_m)_2 \tag{1.10}$$
用计算机程序设计的术语说就是，$n$向左循环移动一位就得到$J(n)$
重复运用$J$就会得到一列递减的值，它们最终到达一个”不动点”，在该点有$J(n)=n$。利用循环移位的性质可以看出，不动点将是：对函数迭代足够次数总是会产生全由1组成的形式，它的值是$2^{v(n)}-1$，其中$v(n)$是$n$的二进制表示中1的个数。于是，由于$v(13)=3$，我们有：
$$J(J(\cdots J(13)\cdots)) = 2^3-1=7$$
类似地有：
$$J(J(\cdots J( (101101101101011)_2 )\cdots)) = 2^{10}-1=1023$$
我们回到第一个猜测：当$n$为偶数时有$J(n)=\frac{n}{2}$，它在一般情形下显然并不成立，不过现在我们可以确定它在什么情形下成立：
$$\begin{array}{}
J(n)=\frac{n}{2} \\\
2l+1=(2^m+l)/2 \\\
l=\frac{1}{3}(2^m-2)
\end{array}$$
如果这个数$l=\frac{1}{3}(2^m-2)$是整数，那么$n=2^m+l$就是一个解这是因为$l$小于$2^m$。不难验证，当$m$为奇数时，$2^m-2$是3的倍数，但当偶数时则不然。于是方程$J(n)=\frac{n}{2}$有无穷多个解，前面几个解如下：
| $m$ | $l$ | $n=2^m+l$ | $J(n)=n/2$ | $n$ (二进制) |
|---|---|---|---|---|
| 1 | 0 | 2 | 1 | 10 |
| 3 | 2 | 10 | 5 | 1010 |
| 5 | 10 | 42 | 21 | 101010 |
| 7 | 42 | 170 | 85 | 10101010 |
进一步推广
如果新的问题产生了和(1.8)有些相似的递归式，我们应该怎么去解？我们可能没有很好的运气去猜出它的解，所以需要引入常数$\alpha$，$\beta$，$\gamma$，来试图求得一个普适的封闭形式的解。
$$\begin{array}{}
f(1)=\alpha \\\
f(2n)=2f(n)+\beta , \quad n \ge 1 \\\
f(2n+1)=2f(n)+\gamma , \quad n \ge 1
\end{array} \tag{1.11} $$
我们对较小的$n$值构造如下的表：
| $n$ | $f(n)$ |
|---|---|
| 1 | $\alpha$ |
| 2 | $2\alpha+\beta$ |
| 3 | $2\alpha \qquad + \gamma$ |
| 4 | $4\alpha+3\beta$ |
| 5 | $4\alpha+2\beta+\gamma$ |
| 6 | $4\alpha+\beta+2\gamma$ |
| 7 | $4\alpha \qquad +3\gamma$ |
| 8 | $8\alpha+7\beta$ |
| 9 | $8\alpha+6\beta+\gamma$ |
从上表可以看出，$\alpha$的系数是不超过$n$的2的最大幂。此外，在2的幂之间，$\beta$的系数递减1直到得到0，而$\gamma$的系数则从0开始递增1。于是，我们可以把$f(n)$表示成如下形式：
$$f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma \tag{1.13}$$
看起来有
$$\begin{array}{}
A(n)=2^m \\\
B(n)=2^m-1-l \\\
C(n)=l
\end{array} \tag{1.14}$$
如通常一样，这里有$n=2^m+l$以及$0 \le l < 2^m (n \ge 1)$
用归纳法证明(1.14)并不太困难，但是有更简单的办法：通过选取特殊的值，然后将它们组合起来。
先考虑$\alpha=1,\beta=\gamma=0$这一特殊情形，此时$f(n)$等于$A(n)$，递归式(1.11)就变成：
$$\begin{array}{}
A(1)=1 \\\
A(2n)=2A(n) , \quad n \ge 1 \\\
A(2n+1)=2A(n), \quad n \ge 1
\end{array}$$
足以肯定的是，$A(2^m+l)=2^m$为真（对$m$用归纳法）
接下来，从一个简单的函数$f(n)$出发，将$f(n)=1$代入(1.11)得到
$$\begin{array}{}
1=\alpha \\\
1=2\times 1+\beta \\\
1=2\times 1+\gamma
\end{array}$$
从而有：$A(n)-B(n)-C(n)=f(n)=1$
类似地，我们可以代入$f(n)=n$:
$$\begin{array}{}
1=\alpha \\\
2n=2\times n+\beta \\\
2n+1=2\times n+\gamma
\end{array}$$
当$\alpha=1,\beta=0,\gamma=1$时，这些方程对所有的$n$都成立，故则有$A(n)+C(n)=n$
所以，在一般情形解递归式(1.11)时，所得到的解中的函数$A(n)$、$B(n)$、$C(n)$满足方程
$$\begin{array}{}
A(n)=2^m \quad \text{其中$n=2^m+l$且$0\le l < 2^m$} \\\
A(n)-B(n)-C(n)=1 \\\
A(n)+C(n)=n
\end{array}$$
于是可以立刻解得$C(n)=l$，$B(n)=2^m-1-l$
这一做法描绘出对求解递归式有惊人效果的成套方法。首先我们来寻求一组已知其解的通用参数，这会给我们一整套可以求解的特殊情形。然后将特殊情形组合起来得到一般的情形。有多少个独立的参数，就与要多少个独立的特解。
推广的约瑟夫递归式
我们知道，原来的约瑟夫递归式有个奇妙的解，即
$$J((b_mb_{m-1} \cdots b_1b_0)_2)=(b_{m-1}b_{m-2} \cdots b_1b_0b_m)_2 \quad 其中b_m=1$$
如果令$\beta_0=\beta$以及$\beta_1=\gamma$，那么就可以将式(1.11)改写成：
$$\begin{array}{}
f(1)=\alpha \\\
f(2n+j)=2f(n)+\beta_j , \quad j=0,1 ,\quad n\ge 1 \end{array} \tag{1.15}$$
这个递归式按照二进制展开就是：
$$\begin{align*}
f((b_mb_{m-1} \cdots b_1b_0)_2)&=2f((b_mb_{m-1} \cdots b_1)_2)+\beta_{b_0} \\\
&=4f((b_mb_{m-1} \cdots b_2)_2)+2\beta_{b_1}+\beta_{b_0} \\\
& \qquad \qquad \vdots \\\
&=2^mf((b_m)_2)+2^{m-1}\beta_{b_{m-1}}+\cdots+2\beta_{b_1}+\beta_{b_0} \\\
&=2^m\alpha+2^{m-1}\beta_{b_{m-1}}+\cdots+2\beta_{b_1}+\beta_{b_0}
\end{align*}$$
解除二进制表示，允许任意的数字，而不仅仅是数字0和1，上述推导告诉我们
$$f((b_mb_{m-1} \cdots b_1b_0)_2)=(\alpha\beta_{b_{m-1}}\beta_{b_{m-2}}\cdots\beta_{b_1}\beta_{b_0})_2$$
再一步推广
将限制再放宽，我们可以进一步推广，递归式：
$$\begin{align*}
f(j)&=\alpha_j,&1\le j <d \\\
f(dn+j)&=cf(n)+\beta_j,\quad &0 \le j<d&, n\ge 1 \end{align*}$$
与上一个递归式是相同的，除了这里是从基数$d$的数着手，而产生的值是用基数$c$表示之外。这就是说，它有变动基数的解
$$f((b_mb_{m-1} \cdots b_1b_0)_d)=(\alpha_{b_m}\beta_{b_{m-1}}\beta_{b_{m-2}}\cdots\beta_{b_1}\beta_{b_0})_c$$
例如下面的递归式：
$$\begin{align*}
f(1)&=34 \\\
f(2)&=5 \\\
f(3n)&=10f(n)+76, \quad &n \ge 1 \\\
f(3n+1)&=10f(n)-2,&n \ge 1 \\\
f(3n+2)&=10f(n)+8,&n \ge 1
\end{align*}$$