Problem #1

In the Tower of Hanoi problem, there are three posts, one of which has a stack of punctured disks of different sizes on it; the other two are empty. The disks are stacked in decreasing size from top to bottom. The goal is to move the stack to one of the empty posts in the least number of moves subject to two conditions:

Only one disk may be moved at a time.
A larger disk may not be placed on top of a smaller one.

For example, here is a sequence of moves for a stack of three disks:

This month's problem is a generalization of the Tower of Hanoi problem. The rules are the same as above except that now there are four posts (one with the stack of disks, the other three empty).

What is the least number of moves to move a stack of 8 disks? 10? 21?

Source: Henry Dudeney