How to teach mathematical 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.

I use the domino analogy myself, and I think it is the most useful I've seen.

As a different approach I also do the following, which is more difficult to understand, but does serve as a way of introducing certain other useful properties of systems of numbers. Consider the set of counterexamples: i.e. the set of positive integers $n$ such that $P(n)$ is false. If this set is non-empty, then it must have a smallest element. Why? At this point I usually find the youngest person in the crowd by running the "anyone younger than $x(\in\mathbb{N})$ years raise your hand"-algorithm once. After that you can pinpoint the exact point, where the induction had to fail but didn't. Then you can conclude that the contrapositive assumption that the set of counterexamples was non-empty is the culprit.

Of course:

• You also need to have explained proof by contradiction.
• You need to explain that no matter how large the crowd of counterexamples (even infinite!), the "raise your hand" -algorithm will terminate after finitely many steps. Nowadays many students have seen computers and algorithms in school, and actually seem to follow this - might not have worked nearly as well 40 years ago.
• You can also immediately start modifying the process, and discuss, why/how "raise your hand" algorithm might fail, if A) the number of participating people is infinite, and B) we count their ages with infinite precision instead of in full years. Alternately (may be better?) you can return to this "memorable" example, when you discuss the finer points of the order relation of real numbers.

Do it in many ways. One explanation may work for some, another for somebody else. Some may not get the point of any of them, but them's the breaks.

I quite like the domino analogy.

The problem with teaching induction - this is from a UK point of view but it probably applies everywhere - is that there is a formal way of setting it out which they have to use, but only makes sense if you're familiar with the construction of the natural numbers.

In particular the formal inductive argument is roughly as follows.
1. There is some set $S = \{n\in\mathbb N : P(n) \text{ is true}\}$.
2. $0\in S$.
3. $k+1\in S$ for every $k\in S$.
4. $\mathbb N$ is defined as the smallest set such that 2. and 3. hold. Therefore $S=\mathbb N$.

But because induction is used so often it's enough to do steps two and three and write induction somewhere on the sheet. In the UK students get a little proof template which they have to learn, but you can pass the exam without understanding it.

A more intuitive explanation of induction is as a contradiction.

Suppose that there is some $n\in\mathbb N$ such that $P(n)$ is false then there must be a smallest $k$ such that $P(k)$ is false. We can show that $k\neq 0$ by checking that $P(0)$ is true, therefore we must have $P(k-1)$ is true, but $P(k)$ is false. But we have shown that $P(k-1)\Rightarrow P(k)$ which is a contradiction.

Notice that for this version is similar to Euclid's proof that there are infinitely many primes, you can even turn that one into an induction, with $P(k)$ the statement that there are at least $k$ primes. You might use this as an introduction.

You should try to get across the idea that induction is shorthand for a deeper argument, rather than present it as an argument in itself. I can't remember all the good examples (I'm not a teacher) but there are some examples of a formulae that are quite tricky to work out, but once you've got them the proof by induction is very quick. So induction is good for lazy people.

Have you tried just showing how it works in special cases?

For example suppose you have proved the basis and induction steps for $P(n)$. Now we can show that $P(3)$ holds:

• $P(0)$ holds because that's the basis step.
• $P(1)$ holds because $P(0)$ holds and the induction step says that if $P(0)$ holds then $P(1)$ holds.
• $P(2)$ holds because of the induction step and because $P(1)$ holds.
• $P(3)$ holds because of the induction step and because $P(2)$ holds.

Do this for a few cases and you one should see that if you take any $n$ you can always "climb the ladder" from $0$ to $n$ this way.