Induction is the process of taking a pattern and extending it into a generalization. In daily life, it can lead to important observations or unfortunate stereotypes. On the mathematical spectrum, induction is an important tool for understanding the infinite world of numbers.
What is Mathematical Induction
Induction in mathematics is actually a form of deduction, contrary to popular reasoning. Because the world of numbers is infinite, it isn’t easy to prove something about infinite things at first. For instance, suppose you had to prove that ” x + 1 > x.” Ignoring the fact that that is obvious, a formal proof might start with the idea that “1+1 > 1, 2+1 > 2, 3+1 > 3…” but that list will be destined to go on forever. To formalize that concept, we allow the use of inductive reasoning.
Inductive reasoning, in plain English, says that if you can prove a starting point, and that everything that has the property will have the property if you take the next step, you are fine, then you can build an infinite set of theorems for each number by building it up from that starting point.
The Starting Point
An example of an theorem that you can use induction for might be that “for all whole n > 1, n23.” As a natural starting point, we will choose n = 2, since the problem technically starts at two. “223,” is true since 4 is less than 8. That gives us our starting point. Starting points are usually the toughest part, but remember to pick a starting point that will capture all the set. If we started with n = 3, we would need to still prove it for n = 2, since that is still part of the set we care about.
Taking a Step
Taking your steps and proving that part tends to be a bit trickier. This will require either some complicated algebra or some clever thinking. Sometimes it takes both. When doing this, start with the original math statement (n23) and replace n with (n+1). Sometimes there are tricks, and this problem responds very well to a few tricks, but I will skip them in this case and just factor it completely. Remember, for the purposes of induction, you already trust the “nth step,” and you are trying to prove step n+1.
Step one:(n+1)23 Step two, expand: n2+2n+1 3+3n2+3n+1 Step three, eliminate a few terms from both sides: n23+ 3n2+ n Step four, use the fact that 3n2+n is positive since n > 0 to eliminate it: n23 3+3n2+n Step five, arrive back at the thing we already trusted: n23
Thus, if we know that n23, then (n +1)2 will be less than (n+1)3 as long as n > 1. So if we have a starting step, we can keep stepping up by 1 forever. This proof was trivial, and it really didn’t need induction to prove it. Some other proofs are best done with induction however.
Some people prefer to do the exact same steps backwards. They will start with the n-step and derive the (n+1)-step. On some problems, that might be more natural. In this case, it is equivalent. In fact, in this problem, step four really requires some extra justuification in the given direction, while in the other it is a perfectly natural step (you add a positive quantity to the greater side, maintaining the “greater than” relationship).
Reverse Induction
Reverse induction is just backwards. You start at a high step and step down using n-1. it is less common, but helpful in some instances. It causes some odd inferences in language however. For instance, “If I remove a single grain of sand from the beach, it is still a beach,” taken mathematically will imply that a single grain of sand is a beach since you keep removing a single grain of sand until only one is left.
Sources:
Purplemath.com: Induction Proofs
City University of New York: Proofs by Induction