Up: Recursion. Prev: How long it takes. Next: Exponentiation.

A closed-form solution

Let's figure out values of M for the first few numbers.

M(1)=1
M(2)=2M(1) + 1=3
M(3)=2M(2) + 1=7
M(4)=2M(3) + 1=15
M(5)=2M(4) + 1=31
By looking at this, we can guess that
M(n) = 2n - 1.
We can verify this easily by plugging it into our recurrence.
M(1) = 1 = 21 - 1
M(n) = 2 M(n - 1) + 1 = 2 (2n - 1 + 1) - 1 = 2n + 1
Since our expression 2n+1 is consistent with all the recurrence's cases, this is the closed-form solution.

So the monks will move 264+1 (about 18.45x1018) disks. If they are really good and can move one disk a millisecond, then they'll have to work for 584.6 million years. It looks like we're safe.

Now we'll look at a very different, very practical problem: Exponentiation.

Next: Exponentiation.