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
series provides a natural lead-in to mathematical induction, since all
the proofs presented, other than the standard one, use
induction, with the formula for each value of n depending on the
formula for the
of n. If you have not done so already I recommend reading at least
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 =
on the traveler. What allows us to apply the continuation argument to =
is the fact that each step follows from the previous one. It is a
explaining why a row of dominoes will fall down after pushing the first
showing that the fall of each domino causes the fall of the next
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.
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.
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<= EM>. Then write an inductive proof for the formula.
We can define the arithmetic
S0 = 0
Sk+1 = Sk + (k+1)
We want to prove that Sn
in this way
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 =
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.
To find the sum of the numbers from k to n, first find =
of the numbers from 0 to n and subtract the sum from 0 to m-1, to
[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.
that the formula holds for n
k = k + 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.