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 ++ 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?

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.
L-tromino
L-tromino, blue

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!

n=2

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×24×48×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

Leave a Comment