Excellent uses of induction and recursion

A Classic: Fix a positive integer $n$. Show that it is possible to tile any $2^n \times 2^n$ grid with exactly one square removed using 'L'-shaped tiles of three squares.

It serves as a wonderful introductory example to proof by induction. Indeed, the proof can almost be represented with two appropriate figures. Yet, for those just learning induction, it is a significant problem where the application of the inductive hypothesis is far from obvious.

Tsirelson's space (1974) is a good example from Banach space theory. His space is the completion of a $c_{00}$ (all finitely supported scalar sequences) under an inductively defined norm. The base norm is the sup-norm $\|\cdot \|_0$.

For $n \in \mathbb{N}$ the norm $\|x\|_{n+1}$ norm is defined by

$ \|x\|_{n+1}= \sup\{\frac{1}{2} \sum^k_i \|E_ix\|_{n} \} $

where the supremum is taken over all sets $(E_i)_{i=1}^k$, where $E_i$ is a finite interval in $\mathbb{N}$, $\max E_i < \min E_{i+1}$ and $k \leq E_1$ (here $Ex$ denotes the restriction of $x$ to the coordinates of $E$). The Tsirelson norm is $\|x\|_T = \sup_n \|x\|_n$ and satisfies the following implicit equation

$ \|x\|_T= \max ( \|x\|_0 , \sup \frac{1}{2} \sum^k_i \|E_ix\|_T ).$

The space $T$ does not contain a copy of any $\ell_p$ or $c_0$. This solved a major open problem at the time (I should point out that Tsirelson actually defined the dual of $T$ which also has the property).

The, inductive, method he devised for producing this space eventually lead to the solutions of numerous problems in Banach space theory (way to numerous to mention). Moreover, the `necessity' of the inductive construction to produce spaces not containing any $\ell_p$ of $c_0$ is a problem that has been considered by Gowers as a polymath project (unfortunately not much progress here): http://gowers.wordpress.com/2009/02/17/must-an-explicitly-defined-banach-space-contain-c_0-or-ell_p/

Check out Boris Tsirelson's website for more info on his space: http://www.math.tau.ac.il/~tsirel/Research/myspace/main.html

The $n$-level Tower of Hanoi can be solved in $2^n - 1$ moves.

Not only does induction prove this, it actually shows you the solution!