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 topic 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.
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:
In order to make it easier to apply the induction argument to geometric series, the geometric series Sn(X) is defined as:
What we want to prove is:
(1 - X)*Sn(X) + Xn+1
= 1.
Using the method of mathematical induction we first show that the
above statement is true for n = 0.
(1-X)*S0 + X(0+1)= (1-X)*1 + X = 1
To apply the second step of a proof for mathematical induction we
want to show that:
if (1 - X)*Sk + Xk+1 = 1 then
(1 - X)*Sk+1 + Xk+1+1 = 1.
The method of proof is just a formalization of the proof given
previously.
(1 - X)*Sk + Xk+1 = 1 by assumption.
(1 - X)*Sk + Xk+1*((1-X)+X)) = 1
(1 - X)*(Sk+Xk+1) + Xk+1+1 = 1
(1 - X)*Sk+1 + Xk+1+1 =1 by the definition
of Sn,
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.
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:
S0 = 1 = (X(0+1) - 1)/ (X - 1).
Show that the formula holds for n = k+1 if we assume that it holds for n = k.
Sk+1 = Sk + 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 Sn .
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 Sn = 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 S0 and Sk+1. Then write an inductive proof for the formula.
We can define the arithmetic series Sn by:
S0 = 0
Sk+1 = Sk + (k+1)
We want to prove that Sn defined in this way
satisfies
Sn = n*(n+1)/2.
Applying mathematical induction, first prove the formula for n = 0:
S0 = 0 = 0*(0+1)/2.
Next, prove the formula for n = k+1 assuming that it holds for
n = k:
Sk+1 = Sk + (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.