01 THE TOWER OF HANOI

开门见山，对于$n$个圆盘的汉诺塔[https://zh.wikipedia.org/wiki/%E6%B1%89%E8%AF%BA%E5%A1%94]是什么情况呢？怎么移动？需要多少步？
我们用记号$T_n$表示$n$个圆盘的情况下需要移动的次数。

我们先考虑很小的情况。$n=1,2$时，显然$T_1=1,T_2=3$。如果$n=0$呢？明显地，$T_0=0$，一次也不用。
思考一个很大的问题，从很小情况开始是非常有帮助的！同时，考虑极端情况，比如这里的$n=0$也是很有必要的。
$n=3$我们会怎么移动呢？利用已有的知识把上面两个移动到某一个柱子上，把最大的移动到第三个柱子上，再把两个小一点的移动到最大的上面。这个过程很容易扩展到$n$的情况。需要$T_{n-1}$步把$n-1$个小一点的圆盘移动到某个柱子上，然后移动最大的一个，最后再用$T_{n-1}$步把$n-1$个小一点的圆盘移动到嘴上的圆盘上面。所以 $$T_n\leq 2T_{n-1}+1,n>0$$ 这里使用小于等于而不是等于的原因很简单，因为我们只是找到了一种方法，说不定有更聪明的方法呢。下面说明$2T_{n-1}+1$是必须的。

我们迟早需要移动最大的圆盘，那么必须将$n-1$个小圆盘移动到某个柱子上，那么必须至少需要$T_{n-1}$步，同时，移动大圆盘至少需要一步（当然可以移动好几次），必须要移动$n-1$个小圆盘到大圆盘上，那么必须至少需要$T_{n-1}$步。所以 $$T_n\geq 2T_{n-1}+1,n>0$$ 综上，得到 $$\begin{aligned} &T_0=0\\ &T_n= 2T_{n-1}+1,n>0 \end{aligned}\tag{1.1}$$ 上面的公式和已知的$T_1=1,T_2=3$是一致的。这也是考虑$n$很小的情况的好处，可以用于核查以免犯低级的错误。
公式$(1.1)$是递推式（recurrence）。往往需要一个式子给出边界值，然后用前面结果给出一般值的式子。

利用递推式可以计算出$T_n$，不过$n$很大的时候，计算会很慢，也没人真的会这么做。递归式给出的是优雅的、局部的信息，我们希望有一个封闭形式，给定一个$n$，快速得到$T_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, n\geq 0\tag{1.2}$$ 至少，对于$n\leq 6$是成立的。

数学归纳法（mathematical induction）是证明某个命题对于所有满足$n\geq n_0$都成立的一般方法。首先证明最小值$n=n_0$时命题成立，这一步称为基础（basis）然后然后对$n>n_0$，假设命题对$n_0$和$n-1$之间的所有值都成立，再证明该命题对$n$成立，这一步称为归纳（induction）。用有限的两步就得到了无限多的结果。
递归式仿佛就是为了数学归纳法而建立的。很容易证明公式$(1.2)$是从$(1.1)$而来的。基础很明显，$T_0=0=2^0-1$。对于$n>0$ $$T_n= 2T_{n-1}+1=2(2^{n-1}-1)+1=2^n-1$$ 所以公式$(1.2)$对$n$也成立。

寻求$T_n$的封闭表达式的过程可以分为以下三阶段：
（1）研究小问题。有助于观察问题，同时对第二阶段和第三阶段很有帮助；
（2）对有意义的量求出数学表达式并证明；对于汉诺塔问题结果就是$(1.1)$，可以对任意$n$计算$T_n$；
（3）对数学表达式求出封闭形式并证明；对于汉诺塔问题就是求出公式$(1.2)$。
后面会集中讨论第三阶段。会频繁的跳过第一阶段和第二阶段，从给出数学表达式作为起点。即便如此，还是会深入各个子问题，寻求解会贯穿三个阶段。

对于汉诺塔问题，我们很幸运的猜测出了答案，这需要一定的洞察力。这本书的一个目的就是说明如果不具备超人洞察力如何求解递归表达式。比如，我们把$(1.1)$两边加1可以使之更简单 $$\begin{aligned} &T_0+1=1\\ &T_n+1=2T_{n-1}+2,n>0 \end{aligned}$$ 令$U_n=T_n+1$，那么 $$\begin{aligned} &U_0=1\\ &U_n=2U_{n-1},n>0 \end{aligned}\tag{1.3}$$ 那么很容易发现解是$U_n=2^n$，进而$T_n=2^n-1$。
这里有趣的点是我们通过对$(1.1)$两边加一而不是减一消去了等式右边的$+1$。