1.河内塔的来源
河内塔是有国数学家爱德华·卢卡斯于1883发明的．给定一个由8个圆盘组成的塔，这些圆盘按照大小递减的方式套在三根桩柱中的一根上．
image.png
2.如何解释
我们先以最少的大小两个圆盘来说
- step1 将最小圆盘的移动到中间桩柱
- step 2 将最大圆盘的放到目标桩柱（B）
- step 3 将最小圆盘移动至目标桩柱（B）
两个盘移动的步骤为3步。我们暂且用T表示最终的结果，这样就有：
T2=3
移动3个圆盘的试验表明，获胜的思路是将上面两个圆盘移动到中间的桩柱上，然后移动第三个圆盘，
接着再把其余两个放到它上面．这就为移动n个圆盘提供了一条线索：首先把n -1个小的圆
盘移动到一个不同的桩柱上（需要 Tn-1) 次移动），然后移动最大的圆盘（需要一次移动），最
后再把那n-1个小的圆盘移回到最大圆盘的上面（这需要另外的 Tn-1 次移动）．这样，至多
需要2Tn-1+1次移动就能移动n（n > 0）个圆盘了：
Tn=2Tn-1+1
3.公式演算
T0=0
Tn=2Tn-1+1
正常的递归公式已经完成。我们可以进一步进行公式演算(数学归纳法)
T0+1=1
Tn+1=2Tn-1+2
如果令Un=Tn+1,那么就有
Un=2Un-1 =>Un=2n
如是推导出
