basic induction probs Hello guys I have this problem which has been really bugging me. And it goes as follows:
Using induction, we want to prove that all human beings have the same hair colour. Let       S(n) be the statement that “any group of n human beings has the same hair colour”.
Clearly S(1) is true: in any group of just one, everybody has the same hair colour.
Now assume S(k), that in any group of k everybody has the same hair colour. If we replace any one in the group with someone else, they still make a total of k and hence have the same hair colour. This works for any initial group of people, meaning that any group of k + 1 also has the same hair colour. Therefore S(k + 1) is true.
I cant seem to figure out where the problem lies in this proof. I have tried a few things and I have concluded the base case is correct. But other than that I can't seem to disprove this proof.

The base case is correct.  
Inductive step:
Assume that the result is true for $n = k$, which is to say that everybody in a group of $k$ people has the same hair colour.  
For the proof to work, you now have to prove that $P(k)$ implies $P(k+1)$, but it doesn't. Just because it's true that for any group of $k$ people, everyone in the group has the same hair colour, it doesn't follow that for any group of $k+1$ people, everyone in the group has the same hair colour. One counterexample suffices to disprove the claim: take a group with one person in, who has red hair. Now add someone with blonde hair.
