Mathematical Induction (part 2)

My previous blog post introduced the basic idea of what mathematical induction is about.  This post focuses more on the mechanics of writing a proof.

A proof is the mathematical form of argument or persuasion.  A proof consists of a sequence of logical statements, each of which is shown to be a true sentence based only on information previous to that sentence.  Examples of sentences that might appear in a proof are equations or inequalities for which there is clear reason that it is true, and never based on what we hope is true or will later show is true.

For example, suppose I needed to prove (x+1)²=x²+2x+1.  In a proof, I can not write down this equation as the first statement because it is not something I know (yet).  Instead, I can write down equations known to be true based on basic principles:

• (x+1)² = (x+1)(x+1)     (meaning of power 2)
• (x+1)(x+1) = x(x+1) + 1(x+1)   (distributive law)
• x(x+1) + 1(x+1) = x²+x + x+1   (distributive law again)
• x²+x + x+1 = x²+2x+1   (collecting like terms)

Notice that each of the sentences is a statement of equality.  Although they to suggest that the "=" sign is being used in a computational sense (i.e., it looks like it is being used to say apply a rule), we really are seeing these sentences as declaring that the result of applying a rule demonstrates that the sentence is actually true.  (This is a subtle distinction that you need to fight your mind until it sinks in.)  Technically, our proof is not yet complete.  Each sentence on its own is a complete, true sentence.  However, we need to end by stating that the sentence we were trying to prove is actually true:

• (x+1)²=x²+2x+1   (equivalence of equal quantities, or substitution)

Now, you should read the above paragraphs as illustrating the ideas of a proof in that it illustrates how sentences (equations) are listed as statements that are demonstrated to be true.  But so far, we have not dealt with the idea of implication.

Recall that the Principle of Mathematical Induction (PMI) involves verifying the two conditions:

1. Show that the first statement in the chain, which we call S(1), is true.
2. Show that if any single statement in the chain, which we call S(n), is true, then this implies the next statement, which will be S(n+1), is also true.

So the structure of every proof by induction involves two subproofs (showing S(1) is true; showing S(n) implies S(n+1)) followed by an application of the PMI.  The subproofs are the method we verify that the two conditions of the PMI have been satisfied.

Here is what to look for in the subproofs.

1. S(1) is almost always very easy to show.  However, you still need to be clear that you follow the pattern of a proof described above.
2. Showing S(n) implies S(n+1) will consist of assuming that S(n) is true for some n (don't forget that this is a specific but unspecified value, so you must leave n or k, depending on the label being used, as a symbol and not an actual number).  Then the proof will almost always rely on some type of recursive relation between a quantity involved in the statement S(n) and a similar quantity in the statement S(n+1).
3. After the subproofs are complete, you must invoke the PMI and then declare that the statements are true for every n=1, 2, 3, ....

Example:  Given a sequence defined by x1=3 and the recursive relation x_k+1=x_k+2 for k=1, 2, 3, ..., prove that x_k=1+2k for k=1, 2, 3, ....

Notice what the chain of statements we are trying to prove will be.   The sentence S(k) is the statement x_k=1+2k, where x_k is the value of the sequence defined recursively, and 1+2k is just a formula involving k.  It is very important to remember that the "=" sign in this equation is not defining the value of the sequence, but is simply stating that the two quantities (the sequence value and the formula value) happen to always be equal.

Everything in italics is not part of the proof.

Proof:
(1) We first write a subproof that S(1) is true:  x₁=1+2(1).  To do this, we need to create a sequence of equations that we know are true based on the symbols themselves, and not the equation above.

x₁=3   (Given)
(We looked at the given information and saw this was provided.)
1+2(1) = 1+2 = 3   (Arithmetic)
(We needed an equation involving 1+2(1) so we wrote down an equation that was based on the rules of evaluating this formula.)
So x₁=1+2(1).   (Equivalence) 
(Earlier, we showed x₁=3 and then we showed 1+2(1)=3, so this means the two quantities are equal.  This ends the subproof since we just finished writing the statement corresponding to S(1) being true.)

(2) We next write a subproof that S(k) implies S(k+1) for k=1,2,3,...  To do this, we will start by assuming S(k) is true for some unspecified k.  Using the recursion to compute x_k+1 we will demonstrate that S(k+1) is also true.  Note: S(k+1) is the statement x_k+1=1+2(k+1).

Assume x_k=1+2k is true for some k=1, 2, 3, ....
x_k+1=x_k+2   (Given recursive definition of sequence)
(The statement we are trying to prove involves the symbol x_k+1 so we need to create equations based on that symbol.)
x_k+1=(1+2k)+2   (Substitution:  x_k=1+2k from assumed hypothesis)
(This is the key step:  we use the recursive connection between x_k+1 and x_k to establish a formula for x_k+1.)
x_k+1=3+2k    (Algebra)   
(We now have a simple formula for x_k+1 and now we turn our attention to the other half of the statement S(k+1), namely the formula 1+2(k+1).)
1+2(k+1) = 1 + 2k + 2   (Distributive law)
(We are creating a true equation involving the formula by considering the results of applying mathematical laws.)
1+2(k+1) = 3+2k    (Algebra from above: 1+2=3)  
(Our target should always be that the formula with k+1 in place of k will match whatever we found by the recursion to compute a value for x_k+1.)
So x_k+1=1+2(k+1)    (Equivalence or Substitution)
That is, S(k) implies S(k+1) for k=1, 2, 3,....
(This ends the second subproof because we just finished writing the statement we were trying to prove in this part.  We are now ready to invoke the PMI.)

Since S(1) is true and S(k) implies S(k+1) for k=1, 2, 3, ..., the Principle of Mathematical Induction guarantees S(k) is true for every k=1, 2, 3, ....  That is, x_k=1+2k for k=1, 2, 3, ...
♦