I have a doubt concerning an exercise from Chapter 1 of "Concrete Mathematics". Actually, my doubt is in one exercise (exercise 3), but, since it depends on the previous exercise (2), I'm including it here too, with the respective solution that I found.
Yes, I know that I could simply check the answer in Appendix A, since "Concrete Mathematics" gives answers to practically every exercise. But here's why I don't want to do this: I don't know how far my own attempt is from the correct answer. So, I would like someone to check if my attempt makes sense and give hints if there is something wrong or incomplete. If I checked the official solution right away, and it was very far from what I did, I would possibly end up missing the opportunity to find the correct answer (and I would also be unsure on whether my own attempt is also valid).
2. Find the shortest sequence of moves that transfers a tower of n disks from the left peg A to the right peg B, if direct moves between A and B are disallowed. (Each move must be or to or from the middle peg. As usual, a larger disk must never appear above a smaller one.)
Note: I have no doubt in this particular exercise, but I included it because the exercise in which I have doubt depends on this one. I'm including the full detailed solution just for the sake of showing my work.
First, the simplest case: if there are 0 disks, we need $T_0 = 0$ moves. For $T_n$, we need to move the largest disk to peg B. For this, first we have to move the upper $n – 1$ disks to peg B, which requires $T_{n-1}$ moves. Then, we move the largest disk to the middle peg (1 move). Then, we can move the $n – 1$ disks back into peg A ($T_{n-1}$ more moves). Then, we move the largest disk to peg B (one more move). Finally, we can move the $n-1$ disks to peg B ($T_{n-1}$ more moves).
So, we get the following recurrence relation:
$T_0=0$
$\\ T_n = 3T_{n-1}+2 \ \ \ \ \text{for } n\geq1$
So, we have that $T_0 = 0$, $T_1 = 3T_0 + 2 = 2$, $T_2 = 3T_1 + 2 = 8$, $T_3 = 3T_2 + 2 = 26$, etc. Working with these numerical examples, we can eventually see that $T_n = 3^n – 1$. This can be proven by induction; for the base case: $T_0 = 3^0 – 1 = 0$. For the inductive step, assume that it is true that $T_{k} = 3^k – 1$ for some k; given this, we want to show that $T_{k+1} = 3^{k+1} – 1$. This is true, because: $T_{k+1} = 3T_{k} + 2 = 3(3^{k} – 1) + 2 = 3^{k+1} – 3 + 2 = 3^{k+1} – 1$.
3. (This is the exercise that I want someone to verify.) Show that, in the process of transferring a tower under the restrictions of the preceding exercise, we will actually encounter every properly stacked arrangement of n disks on three pegs.
I manually tested some basic cases ($n = 1$, $n = 2$) by using the recurrence relation of the previous exercise, and concluded that the steps necessary to move the n disks from peg A to peg B really generate all the arrangements, and every possible configuration of the n disks in the 3 pegs arises, including the initial configuration (that is, when all disks are on peg A).
Now, I will try to explain why this recurrence relation gives all the arrangements of n disks. My explanation may not be very clear, and it may be confusing.
First of all, the initial configuration (that is, all disks are on peg A) is one possible arrangement. Let's use the following reasoning: there are only two things: the largest disk is one thing and the top $n-1$ disks are another thing. Let's consider the top $n-1$ disks as one indivisible block (as if it were only one disk). Then, applying the recurrence relation, we can see that:
1) When the largest disk is on peg A, the top $n-1$ disks are moved successively from peg A to pegs M (middle peg) and then B. This will give all possible arrangements between the largest disk and the top $n-1$ disks (visualized as a block) where the largest disk is on peg A.
2) When the largest disk is on peg M, the top $n-1$ disks are moved from peg B to peg M, then to peg A. This will give all possible arrangements where the largest disk is on peg M.
3) When the largest disk is on peg B, the top $n-1$ disks are moved from peg A to peg M, then to peg B. This will give all possible arrangements where the largest disk is on peg B.
Since this is a recursive function, the same argument above will apply recursively to the movements of the top $n-1$ disks; that is, the largest of the $n-1$ disks will be one thing and the top $n-2$ disks will be another thing. And so on, recursively. From here, we can conclude that all the possible arrangements will be obtained.
To finish this answer, I will calculate the number of arrangements, in the following way: for each of the $n$ disks, in decreasing order of size (from the largest to the smallest), choose one of the 3 pegs and put the disk in the peg. So, for each disk, there are 3 choices of peg. Therefore, the number of arrangements is $3^n$. This makes sense, because the number of moves is $3^n-1$. The number of arrangements is one plus the number of moves, because it includes the initial configuration (where all disks are on peg A).
Best Answer
This is correct, thought it could be stated a little better, and there is a shorter argument.
To state it better, note that you're really just doing an induction on $n$: you're showing that if the transfer of $n-1$ disks goes through all possible arrangements, then so does the transfer of $n$ disks.
The short argument is simply to count the arrangements, as you did, and note that the optimal sequence of moves never repeats a position. (If it did, it couldn't be optimal.) Thus, it must go through every possible arrangement.