Number the disks in order of decreasing size from 1 to N. So the starting condition has all the odd disks in position 1, all the even disks on position 2, and position 3 standing free.
Let F(N) be the smallest number of steps needed to solve the N-disk case. We will come up with an expression for F(N) using a generating function, recursion and induction.
We get to the final position by following four procedures:
1. First, we stack disks 3 through N on position 3, leaving disks 1 and 2 alone in their original positions. Notice that this is done by implementing the solution to the N-2 disk problem for disks 3-N, essentially acting as if disks 1 and 2 weren't there. Therefore, the number of steps required for this procedure is F(N-2)
2. Second, we move the disks 3 through N, stacking them in position 2, on top top of disk 2. This amounts to solving the traditional Tower of Hanoi problem for the N-2 disks (3 through N). Let H(N) be the minimal number of needed to solve the traditional Tower of Hanoi problem, i.e., moving a stack of N disks from one position to another. Then this step requires H(N-2) steps.
3. Third, move disk 1 from position 1 to position 3. One step.
4. Fourth and finally, move he stack of disks 2 through N from position 2 to lie on top of disk 1 on position 3. This requires H(N-1) steps and completes the configuration.
Counting the steps for each procedure, we get
F(N) = F(N-2) + H(N-2) + 1 + H(N-1)
Let's develop a formula for H. To solve the N-disk Tower of Hanoi problem, we first move disks 2,..,N to position 3. This takes H(N-1) steps. Next we move disk 1 to a position 2 (1 step). Finally, we again move 2,..,N on top of disk 1 (again, H(N-1) steps. Hence:
H(N) = 2H(N-1) + 1
Since H(1) = 1, we get the series 1, 3, 7, 15.. So H(N) = 2^N - 1, by induction. So we can write:
F(N) = F(N-2) + 3*2^(N-2) - 1
Now F(1) = 1 and F(2) = 2 and define the generating function T(x) = F(1) + xF(2) + x^2F(3) + ... Then
T - x^2 T = 1 + 2x + x^2 [1 + 2x + (2x)^2 + ...] + x^2 [1 + x + x^2 + ...]
(1 - x^2)T = 1 + 2x + x^2/(1 - 2x) + x^2/(1 - x)
Expanding this rational function as a series in x, and remembering that F(N) is the coeficient of x^(N+1), we get
F(N) = (3 + (-1)^N + 2^(N+1) + 6N) /12
The first few terms of which give
F(1) = 1, F(2) = 2, F(3) = 3, F(4) = 5, F(5) = 8, F(6) = 14
Solution with explanation
