I'm a freshman in college this semester without any previous experience in rigorous proofs or such, however I am interested in the learning more about mathematics and for that reason I picked up the book Concrete Mathematics.
I'm doing the warmup exercises on the first chapter right now, its taken me hours to do up to question 4. The problem is:
Are there any starting or ending configurations of n disks on three pegs that are more than $2^n -1$ moves apart in the Tower of Hanoi problem
My thought process so far has been:
For any $k$ disks in a stack of $n$ disks it takes $T(k-1)$ moves to clear the top. Then it takes one move for the $k$-th disk and then $T(k-1)$ moves again at most to move any number of the remaining disks back to the moved pile of $k$ disks.
Therefore, all the possible legal configurations can be achieved with at most $2(T(k-1)) + 1$ moves. Which in closed form is $2^{k}+1$.
While this argument may make sense to me, I know that it isn't rigorous, it might even be false. I would like to know of a way to make a more rigorous argument here.