All Cats Are Black? What is wrong with the following
“proof” by mathematical induction that all cats are black? Let
P(n) denote the statement “In any group of n cats, if one cat
is black, then they are all black.”
Step 1: The base case is clearly true for n=1.
Step 2: Suppose that P(k) is true, and show that P(k+1) is true.
Suppose we have a group of k+1 cats, one of
whom is black; call this cat “Tadpole.” Remove some
other cat (call it “Sparky”) from the group. We are
left with k cats, one of whom (Tadpole) is black, so
by the induction hypothesis, all k of these are black.
Now put Sparky back in the group and take out Tadpole. We again have a group of k cats, all of whom—
except possibly Sparky—are black. Then by the induction hypothesis, Sparky must be black too. So all k+1 cats in the original group are black.
Therefore, by Mathematical induction, P(n) is true for all n.
0 comments