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 leadin 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.
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 S_{n}(X) is defined as:
What we want to prove is:
(1  X)*S_{n}(X)
+
X^{n+1}
= 1.
Using the method of
mathematical
induction we first show that the above statement is true for n =
0.
(1X)*S_{0}
+ X^{(0+1)}=
(1X)*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}*((1X)+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.
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_{0} = 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.
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_{0} and S_{k+1}<= EM>. Then write an inductive proof for the formula.
We can define the arithmetic
series S_{n}
by:
S_{0}
=
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*(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 noninductive 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 + (n1) + (n2) + (n3) + ... + (nk) + ... + 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 m1, to
get:
[n(n+1)  (m1)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.