Mathematical Induction

Mathematical induction is a very powerful tool for creating proofs. Because the technique can be a little mystifying when first presented, it helps to have a clear example to illustrate it.

I found that what I wrote about geometric series provides a natural lead-in to mathematical induction, since all the proofs presented, other than the standard one, use mathematical  induction, with the formula for each value of n depending on the formula for the  previous value of n. If you have not done so already I recommend reading at least the  introduction to the topic "Teaching Geometric Series" and the section = entitled "Geometric Series Derivation from Seemingly Unrelated Problem". Teaching Geometric Series

In the proofs given in the geometric series there are statements like "we can continue in this way" and "we can generalize for all n". Such statements are okay for informal proofs. However, for formal proofs something more is needed. For example, suppose I used the  following  argument to show that 120 is the largest number: "Since 120 is divisible by 1, 2, 3, 4, 5 and 6 we can continue in this way to show that it is divisible by all numbers". We need a way to separate such nonsense from valid arguments  by providing a way of showing how the proof for each value of n can be derived from the previous value of n. What will be shown is that the method for stating such proofs turns out to be a powerful tool for = generating proofs.

How to Get a Proof to Say "And So On"

Let us consider the second proof in the geometric series topic, the = one based on the traveler. What allows us to apply the continuation argument to = this proof is the fact that each step follows from the previous one. It is a little like explaining why a row of dominoes will fall down after pushing the first = one by showing that the fall of each domino causes the fall of the next one.

Specifically, the technique of mathematical induction says that = a statement is true for all n if the following two statements can be = shown:

1. The statement is true for n = 0
2. If the statement is true for n = k then it is true for n = k+1

Geometric Series Proof Using  Mathematical Induction

In order to make it easier to apply the induction argument to  geometric series, the geometric series S_n(X) is defined as:

1. S₀(X) =1
2. S_k+1(X) = S_k(X) + X^k+1 

What we want to prove is:
(1 - X)*S_n(X) + Xⁿ⁺¹ = 1.

Using the method of  mathematical  induction we first show that the above statement is true for n = 0.

(1-X)*S₀ + X⁽⁰⁺¹⁾= (1-X)*1 + X = 1

To apply the second step of a proof for mathematical induction we want to show that:

if (1 - X)*S_k + X^k+1 = 1  then
(1 - X)*S_k+1 + X^k+1+1 = 1.
The method of proof is = just a formalization of the proof given previously.

(1 - = X)*S_k + X^k+1 = 1 by assumption.
(1 - X)*S_k + X^k+1*((1-X)+X)) = 1
(1 - = X)*(S_k+X^k+1) + X^k+1+1 = 1
(1 - X)*S_k+1 + X^k+1+1 = =1 by the definition of S_n,
which verifies the formula for n = k+1.

We have shown that the formula for geometric series holds = for n = 0 and we have shown that if the formula holds for n = k then it holds = for n = k+1. We can therefore state that it holds for all n. To appreciate the power  of mathematical induction, we will see in the next section how to create a = proof for the geometric series formula in a somewhat mechanical manner.

How to Write a Proof Without Really Thinking

Suppose that we knew the formula for geometric series but had no idea of how to prove it. We could use mathematical induction as follows:

Show the formula holds for n = 0:

S₀ = 1 = (X⁽⁰⁺¹⁾ - 1)/ (X - 1).

Show that the formula holds for n = k+1 if we assume that it holds = for n = k.

S_k+1 = S_k + X^(k+1)  =  (X^(k+1) - 1)/ (X - 1) + X^(k+1) =
(X^(k+1) - 1)/ (X - 1) = + (X^(k+2) - X^(k+1) ) / (X - 1) = 
(X^(k+2) - 1)/ (X - 1), which is the formula for n = k+1.

Although this proof seems to write itself this is certainly not  always the case of induction proofs, but it does give an idea of how useful a tool  that induction is.

You may feel that this example is unrealistic because we had to know  the formula before proving its validity. Actually, it is not unusual in  mathematics to come up with a result by intuition or by making assumptions that have = not yet been proven to be correct. In the next section a simple example is given = where a formula is arrived at through intuition and then proved using = mathematical induction.

Arithmetic Series

Consider the sequence of numbers below and, without doing any  calculations, guess what the average is:

0 1 2 3 4 5 6.

If you guessed 3, you are absolutely right. To test this out, just = add the numbers to get 21 and divide by the number of terms, which is 7. We could generalize this result to find the sum of consecutive numbers from 0 to n, which is an arithmetic series S_n .

See if you can write the formula for arithmetic series by writing = a formula for the average and then multiplying by the number of = terms.

The average is (0 + n)/2 and the number of terms is (n+1), so S_n = n*(n+1)/2. Verify = this formula for several values of n. Notice that for odd n, n/2 is not an = integer. Make sure to test the formula for an odd value of n.

Although testing the formula increases our confidence that it is = valid, this does not constitute a proof. Using what was done for geometric = series as a guide, define arithmetic series by writing expressions for S₀ and S_k+1<= EM>. Then write an inductive proof for the formula.

We can define the arithmetic series S_n  by:
S₀ = 0
S_k+1 = S_k + (k+1)

We want to prove that S_n defined in this way satisfies
S_n = n*(n+1)/2.

Applying mathematical induction, first prove the formula for n  = 0:

S₀ = 0 = 0*(0+1)/2.

Next, prove the formula for n = k+1 assuming that it holds for n  = k:
S_k+1 = S_k + (k+1) = k*(k+1)/2 + (k+1) =
(k*(k+1) + 2*(k+1))/2 =
(k+1)*(k+2)/2, which is the formula for n =  k+1.
This concludes the proof.

For the sake of completeness, here is a simple non-inductive proof = for the arithmetic series formula.

Write the terms of the series in reverse order below the terms of the = series and then add the columns:

0 +   1   +   2   +  3 + ...   +   k    + ... + n
n + (n-1) + (n-2) + (n-3) + ... + (n-k) + ... + 0
__________________________________________________
n +   n +     n +    n + ... .......n + ......+ n

Adding the series twice produces (n+1) copies of n so the value is 1/2*(n+1)*n.

Problem: Use the formula for arithmetic series to find the sum  of the numbers from m to n, where m ≤ n.

Answer: To find the sum of the numbers from k to n, first find = the sum of the numbers from 0 to n and subtract the sum from 0 to m-1, to get:
[n(n+1) - (m-1)m]/2. Another approach would be to take the average = of the first and last numbers, (n + m)/2, and to multiply by the number of = terms, n - (m - 1), to get (n + m)(n - m + 1)/2. Show that the two formulas are the = same.

A Word of Caution

What is wrong with the following argument?

To show: For all n, n = n+1.

Assume that the formula holds for n  = k:
k = k + 1

Adding 1 to both sides:
k + 1 = (k + 1) + 1

We have shown that if the formula hold for  n = k then it hold for n =  k + 1 and therefore the formula holds for all n (?)

An inductive proof has two parts. The second  part is usually more difficult to prove than the first and sometimes in the  effort to prove the second part students neglect the first. As the above example  shows, this is a bad habit to get into. Castles and inductive proofs can not be  built in the air. It only takes a single initial case to kick off the  inductive chain reaction but that initial case must be proved.