Examples of mathematical induction

What are the best examples of mathematical induction available at the secondary-school level---totally elementary---that do not involve expressions of the form $\bullet+\cdots\cdots\cdots+\bullet$ where the number of terms depends on $n$ and you're doing induction on $n$?

Postscript three years later: I see that I phrased this last part in a somewhat clunky way. I'll leave it there but rephrase it here:

--- that are not instances of induction on the number of terms in a sum?

Solution 1:

Here is the first example I saw of induction, and I still think it's a beautiful one.

Problem: Prove that a $2^n \times 2^n$ sheet of graph paper with one box removed, can be tiled with L-shaped trominos.

Proof: For the $n=1$ case, there is nothing to prove: a $2 \times 2$ grid with one box removed is exactly a L-tromino.

For $n=2$, consider the $4 \times 4$ grid. You can divide it into four $2\times 2$ grids. The removed box is in one of those four sub-grids, so that sub-grid can be covered with an L-tromino (is an L-tromino, rather). What about the other 3 sub-grids? Put an L-tromino right in the center of the huge grid, which covers them!

Now the remaining part of each of them is a $2\times2$ grid with one box removed. I leave it to you to complete the proof, and teach it to the students as you best see fit.

The figures above are from Mathematical Circles: Russian Experience by Dmitri Fomin, Sergey Genkin, and Ilia Itenberg, specifically the chapter on Induction which is written by I.S. Rubanov. The book actually doesn't use a variable $n$, but asks for a $16\times 16$ square, then in the form of a discussion between a teacher and a student works through the $2\times 2$ and $4\times 4$ and $8\times 8$ cases, until it is obvious that we have in fact proved a theorem for any $2^n \times 2^n$ ('It looks like we have a "wave of proofs running along the chain of theorems $2\times2 \longrightarrow 4\times4 \longrightarrow 8\times8 \longrightarrow$ It is quite evident that the wave will not miss any statement in this chain.')

As an aside, this is a lovely book with quite a bit of non-trivial mathematics suitable for elementary school and high-school students (though I read in late high school).

This theorem and proof are also on the cut-the-knot website: Tromino Puzzle and Golomb's Inductive Proof.

Solution 2:

My favorite induction problem goes like this:

Consider a long circular road that has a number of fuel depots along the way. All in all, the depots contains just the right amount of fuel to get your car around. You start with an empty tank. Show that you can always find a depot at which to start so that it's possible to get all the way round. (You can make the road one-way if you like.)

Solution 3:

Some I can think of off the top of my head:

1. Number of moves to solve the Towers of Hanoi puzzle.

2. Factorization into primes (uses strong induction, though).

3. Also using strong induction, the winning strategy for a simplified game of nim described at the bottom of this answer.

4. Formula for combinations, using $\binom{n+1}{k} = \binom{n}{k}+\binom{n}{k-1}$.

I'll add more later if I think of any.