The Student Room Group

All horses are in fact the same colour - A Level further maths proof.

Let us consider a group of nn horses. I claim that every horse in a group of nn horses are the same colour.

Step 1: the basis case n=1n=1 is trivially true. That is, in a group of 1 horses, all horses are the same colour.

Step 2: assume that every horse in a group of n=kn=k horses are the same colour.

Step 3: we will prove the proposition for n=k+1n=k+1. Line the k+1k+1 horses up. Take the first horse out of the group so we are left with kk horses, which are all the same colour by step 2. Then put the first horse back in the group, and take the last horse out of the group so we are left with kk horses once again, which all are the same colour by step 2 again. Hence, every horse in this group of k+1k+1 horses are the same colour, because the first horse is the same colour as the middle horses, and the last horse is the same colour as the middle horses, so the first and last horses are the same colour.

Step 4: since the proposition is true for n=1n=1, and if true for n=kn=k then true for n=k+1n=k+1, then the proposition is true for n=1,2,3,...n=1,2,3,... or in other words, all horses are the same colour.

Is there a mistake? Or do you philosophically disagree with induction?
A classic.
Nicely done
Original post by ghostwalker
A classic.


One of my favourite moments in school was the debate this caused when my maths teacher showed this to us. Definitely a good one for the classroom, especially after just teaching induction to students.
There must be a mistake because it clearly doesn't hold true for n=2
I've come across this before. It would probably confuse a lot of students but if you understand that induction is basically like a domino effect, and consider the case n = 2, then the whole thing falls apart.
Original post by Quantum Horizon
:smile:


I like that you are articulating the reason!

I would only add the conclusion to your middle paragraph, that since a group of two horses doesn't have "middle horses", we can't apply the ending argument in step 3 and say the first and the last horses are the same colour by transitivity with the (non-existent) middle horses.

Essentially, this issue boils down to the fact that the inductive hypothesis about the kk horses (being the same colour) is not the only assumption we're making about them - we have the implicit assumption in step 3 that such a group has "middle horses", which of course is not the case in n=2n=2.

Edit: oh, did you remove your post?
Original post by I hate maths
I like that you are articulating the reason!

I would only add the conclusion to your middle paragraph, that since a group of two horses doesn't have "middle horses", we can't apply the ending argument in step 3 and say the first and the last horses are the same colour by transitivity with the (non-existent) middle horses.

Essentially, this issue boils down to the fact that the inductive hypothesis about the kk horses (being the same colour) is not the only assumption we're making about them - we have the implicit assumption in step 3 that such a group has "middle horses", which of course is not the case in n=2n=2.

Edit: oh, did you remove your post?


Sorry! I deleted it before seeing your reply.

Anyway, hats off to your reasoning.
It's a good problem to ask students to test their understanding of how induction actually works. These kind of oversights can even happen at very high levels of maths so it's important to always have a precise understanding of each step of your proofs, even if they aren't presented in full detail when you write them up (which would obviously be very cumbersome and hence less clear anyway).
Perhaps the earliest improvement to the proof would be specifying k1k \geq 1 in the n=kn=k assumption.
(edited 5 years ago)

Quick Reply