The famous game $$Towers of Hanoi$$ asks you to move $3($more generally

n$)$ wooden disks from the left rod to the right rod such that a larger disk never

lands on top of a smaller disk$\mathrm{.}1$ The goal is to understand how many moves it

would take to perform the task. A move is considered an action that takes one

disk from any rod and puts it in any other rod. Let T$($n$)$ be the runtime of an

algorithm to complete the task if there were n disks in total $($play with n $=3$

first$).$ Provide such an algorithm whose runtime obeys: T$($n$)=2$T$($n $1)+1$

$($hint: recursion$/$induction$).$ Then, prove that T$($n$)=2$n $1,$n$.$ Bonus: As

algorithm designers, the next question here is $$can we do better?$$