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:
- When the first domino falls, it will hit the second domino.
- Make sure that each domino will hit the domino next to it and that each hit domino will fall.
- 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.
What about the math?
Mathematical Induction states that if is a condition and is true, and for a natural number , if then is true, then is true for every positive integer.
For example, we want to add the first natural numbers, we may observe that
If we continue, we might observe that
and we might be tempted to guess that
You may want to try a few more cases.
Note that the … sign means all the way through . This means that we want to add all the integers from through .
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 , or , or . 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 , and once it is true for any natural number , it is also true for , 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 ), it hits the next domino and the second domino falls. Now, if for each if the hit domino falls (this is our ) and hits the next domino and again that domino (this is our ), 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 to any number say , or written as
Note that n is any positive integer. We check if the condition is true for .
Yes, that is true. The right hand side of the equal sign, indeed equals .
Assuming is true, then
We must show that is also true. That is we must show that
Note that since , we just replace all by in the right hand of side of the equation.
Simplifying the right hand side, we have
and we are done.
Photo Credit: Wikimedia Commons