What would be the recursive algorithm for solving the Tower of Hanoi problem (with n disks and 3 pegs) in maximal number of moves (i.e. going through all possible disks/pegs combinations).
[Math] Modeling the maximum number of moves in Tower of Hanoi problem
algorithmsrecursion
Related Solutions
I will show it by induction on $n$ (the number of disks). Let $T(n)$ be the number of moves needed to go from an arbitrary configuration to another arbitrary configuration. Let $P(n)$ be the proposition "$T(n)\leq 2^n-1$". That is, $P(n)$ is the proposition "All starting and ending configurations of $n$ disks are at most $2^n-1$ moves apart.". I want to show that $P(n)$ is true for every natural number $n$.
For the base case, $P(0)$ is true, because it is clear that $T(0)=0\leq 2^0-1=0$.
For the inductive hypothesis, let's assume that $P(n-1)$ is true; that is, let's assume that it is true that $T(n-1)\leq 2^{n-1}-1$. Now, I will show that $P(n-1)$ implies $P(n)$.
First method
Suppose I have a configuration of $n-1$ disks. By the inductive hypothesis, we know that $T(n-1)\leq 2^{n-1}-1$. Now, let's consider what will change if we add one more disk (an $n^{th}$ disk), smaller than every other disk in the configuration, so that we have a situation where there are $n$ disks. Since this $n^{th}$ disk is the smallest one, it will always be on top in one of the three pegs, due to the rules of the problem.
The bottom $n-1$ disks will make $T(n-1)$ moves. For each move of the $n-1$ disks, in the worst case, the new smallest disk will be either on top of the disk that wants to move, or on top of the peg to which the disk wants to move. So, the new disk will have to make at most one move for each move of the other $n-1$ disks, that is, the new disk will make at most $T(n-1)$ moves. At last, when the $n-1$ disks are already at their correct positions in the end configuration, the new disk may have to make one more move to reach its correct position in the end configuration.
So, there will be at most $T(n) = T(n-1) + T(n-1) + 1 \leq 2^{n-1}-1+2^{n-1}-1+1 = 2^n - 2 + 1 = 2^n - 1$ moves. Therefore, $T(n) \leq 2^n - 1$, which shows that $P(n)$ is true.
Second method
I can also build the inductive step by considering that the new disk is the largest disk (instead of being the smallest one), as explained in the comments below.
Suppose we have a configuration of $n-1$ disks. By the inductive hypothesis, these $n-1$ disks need $T(n-1) \leq 2^{n-1}-1$ moves to reach any other configuration. Now, let's add an $n^{th}$ disk, which is the largest disk. We have two cases:
(1) If the largest disk doesn't move from the starting configuration to the end configuration, then we can just move the top $n-1$ disks as if there were only $n-1$ disks; so, in this case, it takes at most $2^{n-1} - 1$ moves. Therefore, it is true that $T(n) \leq 2^{n} - 1$. So, $P(n)$ is true in this case.
(2) If the largest disk moves, so we first have to move it to its end configuration. For this, we may have to move the top $n-1$ disks to a peg so that they are out of the way; by the inductive hypothesis, this takes at most $2^{n-1} - 1$ moves. Then, we move the largest disk to its correct position in the end configuration (1 more move). Then, we move the top $n-1$ disks to their correct positions in the end configuration (at most $2^{n - 1} - 1$ moves). The whole procedure takes at most $2^{n-1} - 1 + 1 + 2^{n-1} - 1 = 2^n - 1$ moves. So, $T(n) \leq 2^n - 1$. This shows that $P(n)$ is true in this case.
Interestingly enough, it seems that we don't actually know!
From Wikipedia:
Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem.
There is, however, a presumed optimal solution for the puzzle with Four Spindles, also to be found in the same Wikipedia article.
Best Answer
In the initial position there are three towers, that I will call A,B,C, and assume the problem we want to solve recursively is:
The recursive solution is as follows:
For $n=k+1$ disks:
With this, the number of moves is recursively defined as:
$$\begin{cases}M_1=1\\ M_{k+1}=2M_k+1\end{cases}$$ which have the following general formula:
$$M_n=1+2+\ldots+2^{n-1}=2^n-1$$