Mathematical Induction

I actually posted on this very topic a few years ago.  However, I have refined how I think about doing proofs by mathematical induction.  And so I am writing one more time.

First, you might find it interesting to look at the Wikipedia article on mathematical induction.

The Principle of Mathematical Induction (PMI) is an axiom that describes the set of natural numbers, which is N = {1, 2, 3, 4, ...}.  From one point of view, the PMI says that if S is a set that (1) contains the number 1 and (2) guarantees that whenever any number n is in the set, then n+1 is also in the set, then the set S contains all of N.  From the perspective of proofs, however, we are really interested in showing that an infinite chain of logical statements is true.

Before we proceed with the idea of the PMI, let me be clear about a logical statement.  A logical statement is a well-constructed sentence that is definitively true or false. Two well-known but easily misunderstood examples of logical statements are equations and inequalities.  An equation "A=B" is a logical statement that declares two quantities (A and B) are equal (have the same value).  An inequality "Afalse, but the statement itself is logically complete.  (Here logical does not mean `makes sense' but it means `can be decided between True or False'.)

Related to this issue is a common misunderstanding by students that "=" is like an operation that means "has the value" or "find the answer" as it is often used on a calculator.  This is especially important in a proof, where each statement (usually an equation) must be clearly true rather than a statement of what you hope or what you are trying to calculate.

Okay, back to the Principle of Mathematical Induction.  This principle is about dealing with an infinite chain of logical sentences.  For example, consider the following chain of statements.  S(1) is the label for the first sentence, S(2) is the label for the second sentence, and so on:

S(1):     1 = 1(2)/2
S(2):     1+2 = 2(3)/2
S(3):     1+2+3 = 3(4)/2
S(4):     1+2+3+4 = 4(5)/2
S(5):     1+2+3+4+5 = 5(6)/2
S(6):     1+2+3+4+5+6 = 6(7)/2
...
(the pattern continues so that if n is any number n=1,2,3,..., we have):
S(n):     1+2+3+...+n = n(n+1)/2

On the left of each sentence is a summation.  On the right of each sentence is a simple formula involving n.  Using summation notation, we would have written this sentence:
S(n):    Σⁿ_k=1 k = n(n+1)/2

The pattern described by S(n) looks like a single sentence, but it is important to remember that it is describing the entire infinitely long chain of logical sentences.  If you add up the values on the left side of any single sentence and compare it to the value of the formula on the right, you will see that the answers are the same.  But this only verifies the formulas that you actually check.

The Principle of Mathematical Induction is a tool to prove that the entire chain of sentences are all true.  The PMI is much like an infinite chain of dominoes (see the earlier linked wikipedia article).  To knock over a chain, if you knock them down one at a time, you'll never finish.  But if you show that knocking any single domino down will guarantee the next domino also falls and you show that you can knock down the first domino, then this is enough to guarantee that the entire chain will fall down.

So here is the PMI:

Suppose S(n), n=1, 2, 3, ..., is a chain of logical statements and that (1) S(1) is true and (2) S(n) implies S(n+1) for any n=1, 2, 3, ..., then S(n) is true for every n=1, 2, 3, ....

Notice that there are two conditions to use PMI:

1. We must verify that S(1) (the first sentence) is true.
2. We must show that the sentence S(n+1) is true whenever the previous sentence S(n) is true.

A proof by induction is the process whereby we verify these two conditions and then apply the PMI to conclude that the entire chain is true.

To learn more about writing the proofs and an example with commentary, please continue by reading the next blog post.