Table of Contents   |   Proof Methods   |   Glossary

Understanding Mathematical Induction

The Principle of Mathematical Induction can be informally stated by saying:

"We can establish the truth of a proposition if we can show that it follows from smaller instances of the same proposition, as long as we can establish the truth of the smallest instance (or instances) explicitly."  (Grossman, 1990, p. 334)

In induction, the truth percolates up through the layers to prove the whole proposition.  If we know the first instance of a proposition is true and the second one is derived from the 1st one, making it true, and the pattern repeats itself, then we know that our final result will also be true.  But if the first, or any of the other instances following the first, turn out to be false then the final result will be wrong.  

Falling Dominoes

If you've never heard of dominoes before, click here for a short explanation.

Let's look at a row of dominoes, lined up and ready to be pushed over.

We know from experience that if we push over one domino, the rest of the dominoes will fall over.

How can we prove this?

A.  We know from experience that if we push over one domino, it should fall over.

B.  We also know that if a domino is falling and has been placed correctly, it will knock over its neighbor.

Intuitively, it should be very clear that the fall should cascade all the way up to the last domino.  That is, if the next to the last domino falls, the last domino also falls.

But now we need to think about increasing the rigor of this argument by doing a real proof.  

A Formal Proof

Let's look at the behavior of the dominoes.  

  1. Assume that there's some domino k which doesn't fall over.  i.e. k is the first domino which doesn't work right (maybe it's out of line, too far away, or has a different gravitational constant).
  2. Since k is the first such domino, the domino right before k must have fallen over.
  3. But we know from B that a falling domino always knocks its neighbor over.
  4. So domino k will fall over and we have a contradiction.

What we have shown above is that because

  1. We can knock over the first domino.

  2. and a falling domino knocks over its neighbor.

  3. then all the dominoes will fall over.

Now, if we think of each domino as an instance of a proposition.  If a given instance is true, the corresponding domino will fall over.  Given a sequence of instances (row of dominoes):

If we can prove:  

  1. The proposition is true in the first instance.

  2. And if a given instance is true,

         the next one in the sequence will also be true.


  3. Then the proposition will be true in all instances.

This is called a Proof By Induction.

Go to:

Top of Page   |   Table of Contents   |   Proof Methods   |   Glossary