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": LetP(n) be the statement "Any set ofncoins chosen from a box all have the same denomination."

P(1) is clearly true.

Suppose thatP(k) is true. Consider any set ofk+1 coins: Remove one coin. SinceP(k) is true, the remaining coins all have the same denomination: Now put that coin back, and remove a different coin. Again, sinceP(k) is true, the remainingkcoins all have the same denomination. Therefore, allk+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 alln.