A Quick Explanation of Mathematical Induction

By

Home / A Quick Explanation of Mathematical Induction

"Giant Domino Cascade" by zigazou76

“Giant Domino Cascade” image by zigazou7: a physical metaphor for Mathematical Induction.

Two of my previous articles had proofs using mathematical induction. After publishing the second article, I realized that some might not know exactly what mathematical induction is, or how it normally is used.

The least technical description would be that it is like a row of standing dominoes. First, demonstrate that one standing domino falls after it is pushed. Second, demonstrate that pushing over one standing domino will knock down the second. Essentially, that proves that a row of standing dominoes will fall if the first is pushed.

Mathematical induction is useful when dealing with proofs about “natural numbers”: the set {1, 2, 3…}. This is exactly the set of positive integers.

The “Principle of Mathematical Induction” itself is an axiom of mathematics. It is a statement assumed to be true, so it can be a building block in a mathematical system.

The Definition of Mathematical Induction

Peano’s Fifth Axiom is the “Principle of Mathematical Induction”, which has two practical steps. A proof using mathematical induction must satisfy both steps. The principle also starts with a quick definition.

Let P(n) be the function or relationship about the number “n” that is to be proven.

[1] Prove that “P(1) is true”.

[2] Prove that “If P(N) is true, then P(N+1) is true”.

In practice, some proofs have different starting values. My article about the Fibonacci series, for example, said that the series started as {0, 1, 1, 2, 3, 5, 8, 13…}. So F(1) = zero, F(2) = 1, F(3) = 1, F(4) = 2 and so on. The definition of the Fibonacci sequence itself has to say F(1) = zero and F(2) = 1 before the rule could be applied that F(N) = F(N-2) + F(N-1). (That page used the notation “x = x[n] + x”).

"Leonardo Fibonacci" by zoonabar

“Leonardo Fibonacci” image by zoonabar

One Example of Proof by Mathematical Induction

The “Cut the Knot” organization’s example is simple and helpful. The relationship to be proven, P(n), is: for any positive integer “n”, 1 + 3 + 5 +…+ (2*n – 1) = n*n.

Step One for This Proof

The proof starts with n=1: 1 = 1*1. (You are allowed to say “Big deal” at this point).

Step Two for This Proof

The next step is more interesting. We are to assume that P(n) is true for an arbitrary value of n=N. So we can say “1 + 3 + 5 +…+ (2*N – 1) = N*N” is true for some positive integer “N”.

Now the statement to be proven is P(N+1): “1 + 3 + 5 +…+ (2*(N+1) – 1) = (N+1)*(N+1)”.

My usual approach is to rewrite both sides of the equation, looking for something familiar from the case of P(N). On the left side, let’s start by showing that previous term, “(2*N – 1)”. On the right side, let’s multiply out the two factors.

“( 1 + 3 + 5 +…+ (2*N – 1) ) + (2*(N+1) – 1) = N*N + N + N + 1″.

Now the left side starts with the left side of the statement about P(N), “1 + 3 + 5 +…+ (2*N – 1)”, plus a new term “(2*(N+1) – 1)”. The right side also starts with a familiar “N*N”, plus “N + N + 1″.

Since we were allowed to assume that P(N) is true, we can subtract “( 1 + 3 + 5 +…+ (2*N – 1) )” and “N*N” from both sides, leaving the following.

“(2*(N+1) – 1) = N + N + 1″

Let’s multiply out the left side and add up the right side of this equation.

“2*N + 2 – 1 = 2*N + 1″

We notice that “2 – 1″ = 1 on the left, so we have.

“2*N + 1 = 2*N + 1″.

That is an obviously true statement. (You are allowed to say “Wow, that’s impressive” at this point, if you think that four lines of mathematics is impressive. Or, “Big deal again” if you just look at this one line).

At this point, a mathematician such as yourself would say “Therefore we have proven that P(N) implies P(N+1)”.

Completing a Proof by Mathematical Induction

The proof is completed by the statements “The relationship P(n) has been proven for the initial case P(1), and it has been proven that, P(N) implies P(N+1). Therefore it is true for all “n” greater than zero”.

Common Mistakes in Mathematical Induction

Usually a mistake in a proof by mathematical induction takes one of two forms.

Omit the Initial Case

Perhaps the most common error is to omit proving the initial case. Consider “Let P(n) state that “n = n+3 for all positive integers”.

If we assume P(N) is true, then “N = N+3″. Given that assumption, would P(N+1) hold?

Yes, since P(N+1) states that “(N+1) = (N+1)+3″. Subtract “1” from each side, to find “N = N+3″ as in the assumption.

The problem, of course, is that we did not prove this for P(1): “1 = 1+3″ is clearly false. Not all cases are this obvious, however.

Make a Mistake in Simplifying Equations

Few people would accidently miss the Step Two, since it usually is the largest, but it is possible to make an error in the algebra.

The Value of Mathematical Induction

Some theorems can be proven more easily and directly by induction than by any other process. Certainly proving the base case is a very helpful starting point for finding a flaw before developing a proof any farther.

For those wondering, the other article that mentioned “mathematical induction” was “How to Change Triangular Numbers into Square Numbers“. Ten-pin bowling is named for the fourth triangular number.

"Ten Pin Bowling" by DJ-Dwayne

“Ten Pin Bowling” image by DJ-Dwayne illustrates 10, the fourth triangular number.

References:
Alexander Bogomolny. Cut the Knot. “Mathematical Induction.” 1996-2011. referenced June 19, 2011.
Dept. of Mathematics, University of Toronto. “Principle of Mathematical Induction.” PDF referenced June 19, 2011.
Lingli Zhang. University of California at Santa Barbara. “(CS40) Review of (section) 3.2.” 2004. PDF referenced June 19, 2011.
Creic Weisstein (curator). Wolfram Mathworld. “Peano’s Axioms.” 1999-2011. referenced June 19, 2011.

Leave a Comment