Subsection 8.10.9 Faulty Induction Proofs
Induction is subtle. When used as defined, it is sound. It cannot prove something that is false.
However, and this is a big however, it is easy to use it incorrectly. We must be careful.
Consider the claim that all M&Ms are the same color.
We’ll “prove” this claim by induction. Define:
P(n) “In an arbitrary set of n M&Ms, all candies are the same color.”
Base case: For n = 1, there is only one M&M, which must be the same color as itself.
Induction step: We must prove:
(In an arbitrary set of n M&Ms, all candies are the same color)
\(\rightarrow \)
(In an arbitrary set of n+1 M&Ms, all candies are the same color)
Suppose that we have n+1 candies. Remove one. We now have a set of n candies. By the induction hypothesis, they are all the same color.
Now place the removed candy back in the pile and remove a different one. Again we have a set of n candies and they are all the same color.
And they are the same color as the newly removed one since we already have that it shared the pile’s color before it was removed. Thus all n+1 candies are the same color. Q.E.D.
If we had stopped to do a plausibility check before trying to write a proof, we might not even have tried. But we did try. And we got this. It looks like a proof. But it can’t be. It’s demonstrably ridiculous to claim that all M&Ms are the same color. We know, in fact, that they keep adding new colors. So what is wrong? See if you can figure it out.
Exercises Exercises
1.
Consider the following claim:
For any integer n ≥ 0, 2n = 0.
What is wrong with the following inductive proof of this claim?
The proof is by strong induction. Define:
P(n) ≡ (2n = 0)
Base case: P(0) is true since 2⋅0 = 0.
Induction step: Assume P is true for all nonnegative integers ≤ n. We show that it must also be true of n + 1. We can rewrite n + 1 as the sum of two smaller numbers, i and j. Specifically, there must exist integers i and j such that n + 1 = i + j and 0 ≤ i, j < n+1. (For example, if n + 1 = 5, then we could rewrite it as 2 + 3.) So we have:
n + 1 = i + j
2 (n + 1) = 2 (i + j)
= 2i + 2j
= 0 + 0 Induction hypothesis
= 0
2.
Let’s consider another postage stamp problem. This time assume that there are 3¢ and 4¢ stamps.
Consider the claim that it is possible to form any amount of postage of at least 3¢ using only 3¢ and 4¢ stamps. What is wrong with the following inductive proof of this claim?
The proof is by strong induction. Define:
P(n) ≡ “It is possible to form n¢ using just 3¢ and 4¢ stamps.
Base cases: It is possible to form 3¢ using just a single 3¢ stamp.
It is possible to form 4¢ using just a single 4¢ stamp.
Induction step: We assume that it is possible to form all amounts up to n¢ with 3¢ and 4¢ stamps. We must now show that it is possible to form (n + 1)¢. This can easily be done by either replacing one 3¢ stamp with a 4¢ one or by replacing two 4¢ stamps (totaling 8¢) with three 3¢ stamps (totaling 9¢).
