# Is this horse proof by induction okay? [duplicate]

Let $P(n)$ be the statement "all horses in a set of n horses are of the same colour."

Basis Step: Clearly, $P(1)$ is true.

Inductive Hypothesis: Suppose that $P(k)$ is true for some arbitrary integer $k\geq 1$; that is, all horses are of the same colour.

Inductive Step: We now prove that $P(k+1)$ is true.

Consider any $k+1$ horses. Number these horses as $1,2,3,...,k+1$. By the inductive hypothesis, horses $1,2,...,k$ have the same colour. Also, by the inductive hypothesis, horses $2,3,...,k+1$ have the same colour. Because the set of the first $k$ horses and the last $k$ horses overlap, all $k+1$ horses must be of the same colour and we have shown $P(k+1)$ is true.

Therefore, all horses in a set of $n$ horses are of the same colour, for all integers $n\geq1$.

## marked as duplicate by Old John, mdp, Cameron Buie, Bruno Joyal, Stefan HamckeNov 19 '13 at 23:44

• Your induction step clearly fails when deducing $P(k+1)$ if $k+1$ is 2 since there is no overlap. – Old John Nov 19 '13 at 21:23