# Dominoes and Mathematical Induction

Dominoes are Falling Down

If you queued ten thousand dominoes on a very long table and you want to let them all fall just by letting the first domino fall, then how would you queue it?

The best idea probably is to queue them such that:

1. When the first domino falls, it will hit the second domino.
2. Make sure that each domino will hit the domino next to it and that each hit domino will fall.
3. If conditions (1) and (2) are satisfied, then all the dominoes will fall.

In fact, no matter how many dominoes we put on the table, as long as conditions (1) and (2) are satisfied we are sure that all the dominoes will fall.

Mathematical Induction states that if $P$ is a condition and $P(1)$ is true, and for a natural number $n$, if $P(n)$  then $P(n+1)$ is true, then $P$ is true for every positive integer.

For example, we want to add the first $n$ natural numbers, we may observe that $1 = 1$

If we continue, we might observe that $1 + 2 = \displaystyle\frac{(2)(3)}{2}$

and $1+2+3=\displaystyle\frac{(3)(4)}{2}$

and we might be tempted to guess that $1+2+3+\ldots+99+100=\displaystyle\frac{(100)(101)}{2}$.

You may want to try a few more cases.

Note that the … sign means all the way through $100$. This means that we want to add all the integers from $1$ through $100$.

Our guess above is actually correct (Why?), but we do not  know if this formula or strategy always works for all positive numbers.  For instance,  how do we know if  the formula works if the largest number is $500$, or $2000$, or $1,000,000$. Of course, we cannot enumerate all the counting numbers, so we need to have a justification or proof of our conjecture above. The strategy used for proving such conjectures is called proof by mathematical induction.

In mathematical induction, if our condition is true for the natural number $n = 1$, and once it is true for any natural number $n = k$, it is also true for $n = k + 1$, then the condition is true for all positive integers. If it is a little unclear, take this analogy:

Suppose we have an infinite number of dominoes queued, and once we push the first domino (this is our $n = 1$), it hits the next domino and the second domino falls. Now, if for each if the hit domino falls (this is our $n = k$) and hits the next domino and again that domino (this is our $n = k + 1$), then we are sure that all the standing dominoes will fall no matter how long their queue is.

Now, for our problem, we want to show that the sum of the numbers from $1$ to any number say $n$, or written as $1+2+3+\ldots+n=\displaystyle\frac{(n)(n+1)}{2}$

Note that n is any positive integer. We check if the condition is true for $n = 1$. $1 = \displaystyle\frac{(1)(1+1)}{2}$

Yes, that is true. The right hand side of the equal sign, $1(1+1)/2$ indeed equals $1$.

Assuming $n = k$ is true, then $1+2+3+\ldots+k=\displaystyle\frac{(k)(k+1)}{2}$.

We must show that $n = k+1$ is also true. That is we must show that $1+2+3+\ldots+k+(k+1)=\displaystyle\frac{(k + 1)(k+2)}{2}$

Note that since $n = k + 1$, we just replace all $n$ by $k+1$ in the right hand of side of the equation.

So, $1+2+3+\ldots+k+(k+1)=\displaystyle\frac{(k)(k+1)}{2}+(k+1)$

Simplifying the right hand side, we have $\displaystyle\frac{k(k+1)}{2} + (k+1) = \displaystyle\frac{(k+1)(k+2)}{2}$,

and we are done.

***

Photo Credit: Wikimedia Commons