What are the best examples of mathematical induction available at the secondary-school level—totally elementary—that do not involve expressions of the form ∙+⋯⋯⋯+∙ 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 2n×2n 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×2 grid with one box removed is exactly a L-tromino.
For n=2, consider the 4×4 grid. You can divide it into four 2×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×2 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×16 square, then in the form of a discussion between a teacher and a student works through the 2×2 and 4×4 and 8×8 cases, until it is obvious that we have in fact proved a theorem for any 2n×2n (‘It looks like we have a “wave of proofs running along the chain of theorems 2×2⟶4×4⟶8×8⟶ 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).