Solution to Tower of Hanoi variant

See the original puzzle

Hint: The number of disks you can move increases exponentially as you add more rods.

Still give up?

It's relatively easy to simply show the steps when there are only five rods, but I want to generalize.  This requires some recursive algorithms.  Advanced puzzle solving ahead!

First, let's define a function G(N), which is the tallest tower we can move if there are N empty rods.  In the puzzle, I asked for the tallest tower we can move when there are five rods.  Four of those rods are empty, so I basically asked for the value of G(4).  I'll give it away right now, G(4) = 15.

But what happens if we have a tower with sixteen disks?  We can't simply move the top fifteen disks, and ignore the bottom one.  The bottom disk gets in the way, and can't be treated like an empty rod.  Therefore, I need to define another function F(N), which is the largest stack of disks we can move from an infinitely tall tower to an empty rod when there are N available empty rods.

Procedure 1: Moving F(N) disks from a big tower to an empty rod, when there are N available empty rods
If N=1, simply move one disk and you're done!
Otherwise...
1. Use Procedure 1 to move F(N-1) disks from the big tower to the first empty rod.
2. Use Procedure 1 to move F(N-2) disks from the big tower to the next empty rod.
3. Continue as above until we get to F(1)
4. Move one disk to the last empty rod.
5. Use Procedure 1 in reverse order to move F(1) disks from the second to last rod onto the last rod.
6. Use Procedure 1 in reverse order to move F(2) disks from the third to last rod onto the last rod.
7. Continue as above until we get to F(N-1).

This procedure allows you to move F(N) = 1 + F(1) + F(2) + ... F(N-1) disks.  F(N) is given by this recursive function, but we can also figure out an explicit formula.  F(N) = 2^(N-1).

Procedure 2: Moving a tower with G(N) disks to another rod, when there are N available empty rods.
1. Use Procedure 1 to move F(N) disks from the big tower to the first empty rod.
2. Use Procedure 1 to move F(N-1) disks from the big tower to the first empty rod.
3. Continue as above until we get to F(1).  By now we should have depleted the big tower of disks.
4. Reverse steps 1 through 3, only now we build the tower on the last rod instead of where it was before.

This procedure allows you to move G(N) = F(1) + F(2) + ... F(N) disks.  So G(N) = (2^N) - 1.

G(4) = 15
G(5) = 31
G(6) = 63
etc.

I am sure that this is the best you can do, but I will not provide a proof.