Knocking Down Dominoes

The natural numbers, $\mathcal{N}$, is the set of all non-negative integers:

\begin{displaymath}\mathcal{N} = \{0, 1, 2, 3, \ldots\}. \end{displaymath}

Quite often we wish to prove some mathematical statement about every member of $\mathcal{N}$. As a very simple example, consider the following problem:

Show that

\begin{displaymath} 0 + 1 + 2 + 3 + \cdots + n = {n(n+1)\over 2}. \end{displaymath} (1)

for every $n\ge 0$.

In a sense, the above statement represents a infinity of different statements; for every $n$ you care to plug in, you get a different ``theorem''. Here are the first few:

\begin{eqnarray*} 0 &=& 0(1)/2 \ = \ 0 \\ 0 + 1 &=& 1(2)/2 \ = \ 1 \\ 0+1+2 &=& 2(3)/2 \ = \ 3\\ 0+1+2+3 &=& 3(4)/2 \ = \ 6 \end{eqnarray*}



and so on. Any one of the particular formulas above is easy to prove--just add up the numbers on the left and calculate the product on the right and verify that they are the same. But how do you show that the statement is true for every $n\ge 0$? A very powerful method is known as mathematical induction, often called simply ``induction''.

A nice way to think about induction is as follows. Imagine that each of the statements corresponding to a different value of $n$ is a domino standing on end. Imagine also that when a domino's statement is proven, that domino is knocked down.

We can prove the statement for every $n$ if we can show that every domino can be knocked over. If we knock them over one at a time, we'll never finish, but imagine that we can somehow set up the dominoes in a line and close enough together that when domino number $k$ falls over, it knocks over domino number $k+1$ for every value of $k$. In other words, if domino number $0$ falls, it knocks over domino $1$. Similarly, $1$ knocks over $2$, $2$ knocks over $3$, and so on. If we knock down number $0$, it's clear that all the dominoes will eventually fall.

So a complete proof of the statement for every value of $n$ can be made in two steps: first, show that if the statement is true for any given value, it will be true for the next, and second, show that it is true for $n=0$, the first value.

What follows is a complete proof of statement [*]:

Suppose that the statement happens to be true for a particular value of $n$, say $n=k$. Then we have:

\begin{displaymath} 0 + 1 + 2 + \cdots + k = {k(k+1)\over 2}. \end{displaymath} (2)

We would like to start from this, and somehow convince ourselves that the statment is also true for the next value: $n=k+1$. Well, what does statement [*] look like when $n=k+1$? Just plug in $k+1$ and see:
\begin{displaymath} 0 + 1 + 2 + \cdots + k + (k+1) = {(k+1)(k+2)\over 2}. \end{displaymath} (3)

Notice that the left hand side of equation [*] is the same as the left hand side of equation [*] except that there is an extra $k+1$ added to it. So if equation [*] is true, then we can add $k+1$ to both sides of it and get:

$\displaystyle 0+1+2+\cdots+k+(k+1) = {k(k+1)\over 2} + (k+1) = {k(k+1) + 2(k+1)\over 2} = {(k+1)(k+2)\over 2}.$     (4)

showing that if we apply a little bit of algebra to the right hand side of equation [*] it is clearly equal to $(k+1)(k+2)/2$ -- exactly what it should be to make equation [*] true. We have effectively shown here that if domino $k$ falls, so does domino $k+1$.

To complete the proof, we simply have to knock down the first domino, domino number 0. To do so, simply plug $n=0$ into the original equation and verify that if you add all the integers from 0 to 0, you get $0(0+1)/2$.

Sometimes you need to prove theorems about all the integers bigger than some number. For example, suppose you would like to show that some statement is true for all polygons (see problem [*] below, for example). In this case, the simplest polygon is a triangle, so if you want to use induction on the number of sides, the smallest example that you'll be able to look at is a polygon with three sides. In this case, you will prove the theorem for the case $n=3$ and also show that the case for $n=k$ implies the case for $n=k+1$. What you're effectively doing is starting by knocking down domino number 3 instead of domino number 0.