Page 349 - Discrete Mathematics and Its Applications

328 5 / Induction and Recursion

To uncover errors in proofs by mathematical induction, remember that in every such proof,
both the basis step and the inductive step must be done correctly. Not completing the basis step
in a supposed proof by mathematical induction can lead to mistaken proofs of clearly ridiculous
statements such as “n = n + 1 whenever n is a positive integer.” (We leave it to the reader to
show that it is easy to construct a correct inductive step in an attempted proof of this statement.)
Locating the error in a faulty proof by mathematical induction, as Example 15 illustrates, can
be quite tricky, especially when the error is hidden in the basis step.

EXAMPLE 15 Find the error in this “proof” of the clearly false claim that every set of lines in the plane, no
two of which are parallel, meet in a common point.

“Proof:" Let P (n) be the statement that every set of n lines in the plane, no two of which are
parallel, meet in a common point. We will attempt to prove that P (n) is true for all positive
integers n ≥ 2.

BASIS STEP: The statement P(2) is true because any two lines in the plane that are not parallel
meet in a common point (by the definition of parallel lines).
INDUCTIVE STEP: The inductive hypothesis is the statement that P(k) is true for the positive
integer k, that is, it is the assumption that every set of k lines in the plane, no two of which are
parallel, meet in a common point. To complete the inductive step, we must show that if P(k) is
true, then P(k + 1) must also be true. That is, we must show that if every set of k lines in the
plane, no two of which are parallel, meet in a common point, then every set of k + 1 lines in the
plane, no two of which are parallel, meet in a common point. So, consider a set of k + 1 distinct
lines in the plane. By the inductive hypothesis, the first k of these lines meet in a common point
p 1 . Moreover, by the inductive hypothesis, the last k of these lines meet in a common point p 2 .
We will show that p 1 and p 2 must be the same point. If p 1 and p 2 were different points, all
lines containing both of them must be the same line because two points determine a line. This
contradicts our assumption that all these lines are distinct. Thus, p 1 and p 2 are the same point.
We conclude that the point p 1 = p 2 lies on all k + 1 lines. We have shown that P(k + 1) is
true assuming that P(k) is true. That is, we have shown that if we assume that every k, k ≥ 2,
distinct lines meet in a common point, then every k + 1 distinct lines meet in a common point.
This completes the inductive step.
We have completed the basis step and the inductive step, and supposedly we have a correct
proof by mathematical induction.

Solution: Examining this supposed proof by mathematical induction it appears that everything
is in order. However, there is an error, as there must be. The error is rather subtle. Carefully
looking at the inductive step shows that this step requires that k ≥ 3. We cannot show that P(2)
implies P(3). When k = 2, our goal is to show that every three distinct lines meet in a common
point. The first two lines must meet in a common point p 1 and the last two lines must meet in
a common point p 2 . But in this case, p 1 and p 2 do not have to be the same, because only the
second line is common to both sets of lines. Here is where the inductive step fails. ▲

Guidelines for Proofs by Mathematical Induction

Examples 1–14 illustrate proofs by mathematical induction of a diverse collection of theorems.
Each of these examples includes all the elements needed in a proof by mathematical induction.
We have provided an example of an invalid proof by mathematical induction. Summarizing what
we have learned from these examples, we can provide some useful guidelines for constructing
correct proofs by mathematical induction. We now present these guidelines.