Thread: Analyzing an Induction Proof

Consider the statement:
Any set of coins chosen from a box will have the same denomination.

This is obviously not a true statement, since in general a set of coins will contain more than one denomination. Yet I have an argument that seems to prove the statement is true by mathematical induction. What is the flaw in the "Proof"?

"Proof": Let P(n) be the statement "Any set of n coins chosen from a box all have the same denomination."

P(1) is clearly true.

Suppose that P(k) is true. Consider any set of k+1 coins: Remove one coin. Since P(k) is true, the remaining coins all have the same denomination: Now put that coin back, and remove a different coin. Again, since P(k) is true, the remaining k coins all have the same denomination. Therefore, all k+1 coins have the same denomination, that is, P(k+1) is true. Thus, by the principle of mathematical induction, P(n) is true for all n.

the argument that P(k) -->P(k+1) uses the fact that there are at least 2 coins in the box ("...and remove a different coin...."). so the proof is not complete unless we can prove P(2). but P(2) is clearly false, since we might have two different denominations in the box.

to put it another way, the proof shows that if we form two different subsets of k coins, A and B, from a set of k+1 coins, and each has all coins of the same denomination, then the "base case" is actually where removing one coin leaves one coin. that is, we have two coins. and the base case fails.

Think of an infinite row of dominoes. If you push the first one, then any domino will push the next one over.

Mathematical Induction works the same way. The Inductive Step is the proof that the pushing of any domino will push the next one over. But NONE of them will fall unless the Base Step is satisfied as well, in other words, that the first domino is pushed in the first place.