Recurrences and how to solve them

In 1883 the French mathematician Édouard Lucas put a puzzle on sale: three pegs and a stack of discs of decreasing size. Move the whole stack to another peg, one disc at a time, never placing a larger disc on a smaller one. A legend that soon grew around it tells of priests moving 64 golden discs, with the world ending when they finish.

How long would that take? The answer comes from a recurrence. To move n discs, move the top n − 1 out of the way, move the largest, then move the n − 1 back on top: T(n) = 2T(n − 1) + 1. Solving it gives 2⁶⁴ − 1 moves, roughly 585 billion years at one move per second.