HELP WITH THIS ONE QUESTION: In the game "Tower of Hanoi", there are three identical poles A$,$ B$,$ and C

laid on a table, and ninN discs $D_1,$dots,$D_n$ stacked on pole $A.$ The discs are

of increasing diameter, so that for every iin$[n-1]$ the diameter of $D_{i+1}$ is

larger than the diameter of $D_i.$ Here is a visual demonstration with $i=5$ :

Our goal is to move all the discs from pole A to one of the other poles,

under the following rules:

In each turn there are three stacks on each of the poles $($some

stacks may be empty$).$ We can choose the top disc from any of

the stacks, and move it to the top of another stack.

The only constraint is that we cannot place a disc with larger

diameter on top of a disc with smaller diameter. That is$,$ for any

$j,$iin$[n]$ such that $j>i,$ we cannot place $D_j$ on top of $D_i.$

Prove by induction that AAninN, the minimum number of turns

needed to solve the Tower of Hanoi with $n$ discs is at least $2^n-1.$