# How to teach mathematical induction?

Some students are not convinced that a proof by mathematical induction is a proof. I have given the analogy of dominoes toppling but still some remain unconvinced. Is there very convincing way of introducing mathematical induction? I need something which will have an impact. Are there any real life applications of induction?

I’m surprised everyone seems to be in general agreement that the domino analogy is good. It seems poor to me: what have dominos got to do with proving things? It’s a nice metaphor, but it has simply nothing to do with the issue at hand. I don’t remember it having been helpful when I came across it before understanding induction, either. Maybe I’m a special case in that regard.

Which brings me to my answer: I would look for theorems that admit a particularly simple inductive proof. I would also relate those proofs to the students in a more conversational language. Ie, rather than:

First, prove it for 0. Then, prove that if it is true for n, it is true for n + 1. So it must be true for all n.

There are two points here that may be confusing:

1. The notion of proving an “if then” statement. I suspect many students initially find it hard to see that an “if then” can even be considered a “statement” at all, people are more used to thinking of them as combinations of statements. The idea of proving “A if B”, without even considering whether A is true, seems bizarre. Supposing I proved that if there were a unicorn, it would like tea.
2. The use of a variable $n$ may be an unnecessary distraction for some students with low mathematical ability, many students remain uncomfortable with variables all the way through high school. This is admittedly a less important point.

To beat issue (1), work by example. State a simple theorem and propose to prove that it’s true for all numbers (don’t say “for all n”! Just point to the number in the statement, written on the board, and say “we’ll prove it’s true no matter what this is”). Prove it for zero. Then, without proving or stating the inductive step as a separate statement, go right ahead show “well because it’s true for 0, it must be true for 1, because…”. Then, “but because it’s true for 1, we can use the same argument to show it must be true for 2, after all…”. Repeat maybe once more. Finish up by pointing out that as the same argument works for any number, you can keep going as far as you need to and the statement is true for all numbers.

Imagine you had never been taught induction, that you were living in an age before abstract mathematics, and remember the principle meaning of the word proof. A proof is what you use to convince your fellow human that something must be true. If you were simply trying to do that, you wouldn’t be fussing around with separating out the inductive step as a proposition in its own right, you’d use the much more easily grasped (and much more convincing!) sort of proof by example above. The illustration of why that means it’s true for all $n$ is in the language of the proof itself: it’s true because we can keep doing the thing we just did two or three times.