Question

Derive the recurrence for double tower of Hanoi problem. Find the closed form for it.

Answer 1

Let total number of plates be 2n

As per the hypothesis $T(n)=2^{n+1}-2$

For the base case n = 1

$T(1)=2^{1+1}-2= 4-2=2$

Induction hypothesis,

n=k

$T(k)=2^{k+1}-2$

Now, by induction step $n=k+1$

$T(k+1)=2^{k+2}-2$

$\Rightarrow T(k+1)=2T(k)+2$

$=2(2^{k+1}-2)+2$

$=2^{k+1+1}-4+2$

$=2^{k+2}-2$