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?
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.
Maybe it would be good to start with something that the students already know is obviously true. For example, you could develop an inductive proof that $2n$ is always even.

I think this would make it easy for them to see what the base case, inductive hypothesis and inductive steps mean.

For the base case we show our statements holds for the smallest possible $n$. In this case it is $0$ and $2(0)=0$, which is even.

For the inductive step we have to show that $2(n+1)$ is even but we get to use the inductive hypothesis: $2n$ is even. Then it's just a matter of the distributive property to get $2n+2$ and the common knowledge that adding $2$ to an even number gets another even number.

Other candidates could be anything shown with straightforward structural induction on Peano numbers.