## Wednesday, September 14, 2011

### Proof by Induction and Summations

The two previous blog entries introduced the idea of the Principle of Mathematical Induction followed by a discussion of a typical example of a proof by induction.  Be sure you read those two entries before you look at this one.  This blog post extends these ideas by talking about how proof by induction applies to summations.

(I apologize right now about the formatting of summation notation, or sigma notation.  I do not know how to get the math to look like math in a blog setting.)

Recall that the second condition of the PMI is that an arbitrary statement S(n) in the chain of statements being proved will guarantee that the next statement S(n+1) in the chain is also true.  In a proof by induction, this step always involves using a recursive relation between something in the sentence S(n) with a corresponding object in the sentence S(n+1).

For summations, this recursive relation is always that a summation for statement S(n+1) exactly corresponds to the summation appearing in statement S(n) with some additional term(s).

For example, think back to our motivating example of a chain of statements:
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
...
Notice that the sum appearing on the left hand side of any given sentence appears in the sum on the very next sentence, but one more term has been added.  Using parentheses to emphasize where the sum from the previous sentence appears in the new sentence, here is the same chain:

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
...

Summation (Sigma) notation gives us a handy way to describe sequences of sums like we see in the chain above.  The terms of the sum follow a simple pattern.  In this example, the pattern is the sequence of terms (1, 2, 3, 4, 5, ...).  This sequence can be explicitly described as ak = k for k=1, 2, 3, ....  In the symbolism (notation) of summation notation, we write:

Σ1k=1(k) = 1
Σ2k=1(k)  = 1+2
Σ3k=1(k) = 1+2+3
or
Σnk=1(k) = 1+2+3+...+n
(Notice that the formula in the parentheses (k) is the explicit formula of the sequence of terms in terms of the index which is listed at the bottom of Σ along with the first index of the sequence used in the sum.  The index of the last term in the sum appears at the top of Σ.)

The pattern that we described above to illustrate the recursive relation between the sums of consecutive sentences in the chain of statements we wish to prove can also be written in terms of summation notation:
Σn+1k=1(k) = Σnk=1(k) + (n+1)
When writing a proof by induction, we use this recursive relation.

Example:  Prove that Σnk=1(k) = n(n+1)/2  for n=1, 2, 3, ...

In the proof, we will write S(n) to represent the sentence: Σnk=1(k) = n(n+1)/2.

Proof:
(1) We first need to think about the sentence where n is replaced by 1.  That is, we need to prove that Σ1k=1(k) = 1(1+1)/2.
Σ1k=1(k) = 1   (Interpretation of summation notation)
(We are creating a true statement involving the summation symbol that appears on the left side of the equation we are proving. The sequence of terms is 1, 2, 3, 4, 5, ..., and the sum starts and ends with the 1st term.)
1(1+1)/2 = 1(2)/2 = 1   (Algebra)
(We now create an equation involving the formula on the right side of the equation we are proving, and we just showed it has the same value as the summation symbol.)

So Σ1k=1(k) = 1(1+1)/2.
(We obtained evidence above that the summation and the formula both represented the same value, so we conclude that they are equal.)

(2) We now need to show that S(n) implies S(n+1) for n=1, 2, 3, ....  We will assume S(n), i.e. Σnk=1(k) = n(n+1)/2.  Using the recursion connecting the sums, we will show S(n+1), i.e., Σn+1k=1(k) = (n+1)((n+1)+1)/2.

Assume    Σnk=1(k) = n(n+1)/2    for some n=1, 2, 3, ...
Σn+1k=1(k) = Σnk=1(k) + (n+1).     (Recursive relation on summation of terms ak = k)
Σn+1k=1(k) = n(n+1)/2 + (n+1)     (Substitution: summation replaced by formula)
Σn+1k=1(k) = n(n+1)/2 + 2(n+1)/2     (Find common denominator)
Σn+1k=1(k) = (n2+n+2n+2)/2     (Distribution and adding fractions)
Σn+1k=1(k) = (n2+3n+2)/2     (Combining terms)
(Notice that each equation was based on the previous equation.  The key step was when we replaced Σnk=1(k) by the formula n(n+1)/2 that was provided by the assumed hypothesis.  At this stage of the proof, we have a formula representing the value of the summation symbol with n+1 that is the left hand side of the equation in the sentence S(n+1).  We now need to check the formula that appears in the right hand side of our sentence.)
(n+1)((n+1)+1)/2 = (n+1)(n+2)/2    (Arithmetic: 1+1=2)
(n+1)((n+1)+1)/2 = [n(n+2)+1(n+2)]/2     (Distributive law)
(n+1)((n+1)+1)/2 = [n2+2n + n+2]/2     (Distributive law again.)
(n+1)((n+1)+1)/2 = [n2+3n+2]/2     (Combining terms)
(Notice that each equation was based on the previous equation.  Notice that the second and third steps (distributive law) are the formal steps in the idea commonly taught as FOIL when multiplying to binomial expressions together.  The key is that we took the formula with n replaced by n+1 of the right hand side and discovered that it equals the same formula that we found for the summation above.)
So we have Σn+1k=1(k) = (n+1)((n+1)+1)/2.
Consequently, S(n) implies S(n+1) for n=1, 2, 3, ....

By the PMI (since S(1) is true and S(n) implies S(n+1)), we have S(n) is true for n=1, 2, 3, ...

### 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)2=x2+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)2 = (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) = x2+x + x+1   (distributive law again)
• x2+x + x+1 = x2+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)2=x2+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 xk+1=xk+2 for k=1, 2, 3, ..., prove that xk=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 xk=1+2k, where xk 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:  x1=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.

x1=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 x1=1+2(1).   (Equivalence)
(Earlier, we showed x1=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 xk+1 we will demonstrate that S(k+1) is also true.  Note: S(k+1) is the statement xk+1=1+2(k+1).

Assume xk=1+2k is true for some k=1, 2, 3, ....
xk+1=xk+2   (Given recursive definition of sequence)
(The statement we are trying to prove involves the symbol xk+1 so we need to create equations based on that symbol.)
xk+1=(1+2k)+2   (Substitution:  xk=1+2k from assumed hypothesis)
(This is the key step:  we use the recursive connection between xk+1 and xk to establish a formula for xk+1.)
xk+1=3+2k    (Algebra)
(We now have a simple formula for xk+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 xk+1.)
So xk+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, xk=1+2k for k=1, 2, 3, ...

### 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):    Σnk=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.