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 a_k = k for k=1, 2, 3, ....  In the symbolism (notation) of summation notation, we write:

Σ¹_k=1(k) = 1
Σ²_k=1(k)  = 1+2
Σ³_k=1(k) = 1+2+3
 or
Σⁿ_k=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:
Σⁿ⁺¹_k=1(k) = Σⁿ_k=1(k) + (n+1)
When writing a proof by induction, we use this recursive relation.

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

In the proof, we will write S(n) to represent the sentence: Σⁿ_k=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 Σ¹_k=1(k) = 1(1+1)/2.
Σ¹_k=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 Σ¹_k=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. Σⁿ_k=1(k) = n(n+1)/2.  Using the recursion connecting the sums, we will show S(n+1), i.e., Σⁿ⁺¹_k=1(k) = (n+1)((n+1)+1)/2.

Assume    Σⁿ_k=1(k) = n(n+1)/2    for some n=1, 2, 3, ...
Σⁿ⁺¹_k=1(k) = Σⁿ_k=1(k) + (n+1).     (Recursive relation on summation of terms a_k = k)
Σⁿ⁺¹_k=1(k) = n(n+1)/2 + (n+1)     (Substitution: summation replaced by formula)
Σⁿ⁺¹_k=1(k) = n(n+1)/2 + 2(n+1)/2     (Find common denominator)
Σⁿ⁺¹_k=1(k) = (n²+n+2n+2)/2     (Distribution and adding fractions)
Σⁿ⁺¹_k=1(k) = (n²+3n+2)/2     (Combining terms)
(Notice that each equation was based on the previous equation.  The key step was when we replaced Σⁿ_k=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 = [n²+2n + n+2]/2     (Distributive law again.)
(n+1)((n+1)+1)/2 = [n²+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 Σⁿ⁺¹_k=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, ...
♦