我意思说hanoi tower的recursion不是重点，induction是重点，而你依然在和我讨论recursion的问题，我给一下我大一时候做hanoi tower的时候的证明（凭记忆再写一下）：

假设H(n) n其中n是蝶的过程，则显然 H(1)= 1， 只要移动1步即可。

那么显然 H(k+1)= 2*H(k)+1 , 因为显然(k+1)th的碟子必然要再上面k个碟子移走后，才能把(k+1)th移到第三柱，然后还有通过k个碟子的转移过程才能完成，即，2次k个碟子转移+(k+1)th底碟的转移 ，这个是Hainoi Recursion的定义式，好了，我的意思是recursion定义式不是重点，重点在于induction部分。

Hanoi的问题关键是要证明 2^n-1这个移蝶步骤，证明如下：

当n=1时，显然只要一步就可以完成，所以H(1)=1, 符合2^1-1=1的这个式子

假设当n=k时 H(k)=2^k-1成立

证明n=k+1时 H(k+1)是否还是成立？

H(k+1) 根据recursion定义则可以知道 H(k+1)=2*H(k)+1

=2*(2^k-1)+1 (根据induction 的kth假设）

=2^(k+1)-1

则显然2^n-1这个式子是成立的，并且是Hanoi tower的非递归解。

大部分recursion的问题，在数学上必须抛弃recursion定义，采用“线性”式子表达才是其本质。

比如BST(binary search tree)的复杂度问题，复杂度定义都是recursion,但结论都是 类似于 n Log n的非recursiond的"线性"解，这是我的上贴的意思。