What are the best examples of mathematical induction available at the secondary-school level—totally elementary—that do

notinvolve 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

notinstances of induction on the number of terms in a sum?

**Answer**

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).

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

**Attribution***Source : Link , Question Author : Michael Hardy , Answer Author : ShreevatsaR*