Question

What is wrong with this “proof” that all horses are the same color? Let $\mathit{P}\mathbf{\left(}\mathit{n}\mathbf{\right)}$be the proposition that all the horses in a set of n horses are the same color.

Basis Step: Clearly,$\mathit{P}\mathbf{\left(}\mathbf{1}\mathbf{\right)}$ is true

Inductive Step: Assume that $\mathit{P}\mathbf{\left(}\mathit{k}\mathbf{\right)}$is true, so that all the horses in any set of k horses are the same color. Consider any $\mathit{k}\mathbf{+}\mathbf{1}$horses; number these as horses $\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{3}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathit{k}\mathbf{,}\mathit{k}\mathbf{+}\mathbf{1}$. Now the first k of these horses all must have the same color, and the last k of these must also have the same color. Because the set of the first khorses and the set of the last k horses overlap, all $\mathit{k}\mathbf{+}\mathbf{1}$ must be the same color. This shows that $\mathit{P}\mathbf{(}\mathit{k}\mathbf{+}\mathbf{1}\mathbf{)}$ is true and finishes the proof by induction.

Short answer

The error is in the statement the set of the first k horses and the set of the last k horses overlap.

Step-by-step solution

Mathematical Induction

The principle of mathematical induction is to prove that $P\left(n\right)$is true for all positive integer n in two steps.

1. Basic step : To verify that $P\left(1\right)$is true.

2. Inductive step : To prove the conditional statement if $P\left(k\right)$is true then $P(k+1)$is true.

Wrong in the proof

Let $P\left(n\right)$ be the statementthat all the horses in the set of n horses are of same colour.

It is given that the first k of these horses all must have the same color, and the last k of these must also have the same color. Because the set of the first k horses and the set of the last k horses overlap.

Take two horses, a white one and a black one then the possibility for the k+1 horse is 2 elements.

If the first k are all white and the last k are all black then the subsets do not overlap.

Thus, the proof is not true for all possibilities.

Therefore, the statement ‘the set of the first k horses and the set of the last k horses overlap’ is wrong.