Question $2$

Tower of Hanoi is a mathematical puzzle where we have three rods and $n$ disks.

Only one disk can be moved at a time. $2)$ Each move consists of taking the upper disk from one of the stacks and placing it on top of another

stack i$.$e$.$ a disk can only be moved if it is the uppermost disk on a stack. $3)$ No disk may be placed on top of a smaller disk.

The recurrence solution can be derived and is given by the following :M$($n$)=2*$M$($n$-1)1,T(0)=0$

a$)$ Derive the explicit solution to the above recurrence equation

Hint sum of geometric $(1+2^1+2^2+$dots$+2^n)=\frac{2^{n+1}-1}{2-1}$

b$)$ Check your solution by excel as shown below