You are Here: Home >< Maths

# Proof by induction(All horses are the same colour) watch

1. Hi, I'm sure a lot of people have heard about this "famous proof" but I want to know is what is wrong with this proof? I'm not sure where the flaw is. I've tried searching the internet on it but i don't really understand their explanation. Can anyone explain this to me in a simple way. Thanks.
2. I don't recall the exact proof, but I do recall that the flaw is in something like it relies on there being an intersection of two sets, when in the case for 1 (or maybe 2) this is not the case. Look at the proof, draw some venn diagrams and it should all become clear.
3. It's to do with how many base cases you have and how many base cases you need.
4. Ah ok, I'll have a look into a bit more but I sort of start to understand it now. Thanks.
5. (Original post by JBKProductions)
Ah ok, I'll have a look into a bit more but I sort of start to understand it now. Thanks.
It's quite hard to get your head round, but it makes it easier if you convert it into something more mathematical.

Let be a set of colours (so say C = {brown, white, black} or something), let be the set of all horses and let be a function where is the colour of horse .

What your conjecture about the "nth case" appears to say is that for all n, and for any subset of size n, then for all ... but this isn't what your conjecture is actually saying. Go figure. [Or let me know if you need another shove in the right direction.]
6. (Original post by nuodai)
It's quite hard to get your head round, but it makes it easier if you convert it into something more mathematical.

Let be a set of colours (so say C = {brown, white, black} or something), let be any set of n horses and let be a function where is the colour of horse .

What your conjecture appears to say is that for all n, and for all , ... but this isn't what your conjecture is actually saying. Go figure. [Or let me know if you need another shove in the right direction.]
7. (Original post by JBKProductions)
I worded that badly so read the post again... it says pretty much the same thing though.

Using my new notation, what it actually says is not only that for each , . I mean, you would take one horse and say "this horse is all the same colour" would you? There's an implicit assumption about the size of the set.

Although, I've just thought about this a bit more, and I might be leading you up the wrong street slightly. When you assume it's true for a set of size k and show that it's true for a set of size k+1, what you do is take two subsets of size k from the set of size k+1; this assumes that the intersection of these two subsets is non-empty. [That is, there is a horse which lies in both of the size k subsets.] Can you think of a k for which this doesn't work? So how big should your base set be?

These are basically two ways of saying the same thing; one is a common-sense approach and the other is the mathematical approach.

EDIT: And for what it's worth this pseudo-proof does generalise, when corrected, to a very important result, which I'll tell you if you're interested (but only after you've worked out where the proof falls).
8. (Original post by nuodai)
I worded that badly so read the post again... it says pretty much the same thing though.

Using my new notation, what it actually says is not only that for each , . I mean, you would take one horse and say "this horse is all the same colour" would you? There's an implicit assumption about the size of the set.

Although, I've just thought about this a bit more, and I might be leading you up the wrong street slightly. When you assume it's true for a set of size k and show that it's true for a set of size k+1, what you do is take two subsets of size k from the set of size k+1; this assumes that the intersection of these two subsets is non-empty. [That is, there is a horse which lies in both of the size k subsets.] Can you think of a k for which this doesn't work? So how big should your base set be?

These are basically two ways of saying the same thing; one is a common-sense approach and the other is the mathematical approach.

EDIT: And for what it's worth this pseudo-proof does generalise, when corrected, to a very important result, which I'll tell you if you're interested (but only after you've worked out where the proof falls).
Is it to do with...

Spoiler:
Show
n=1?

ie. two horses?
9. (Original post by nuodai)
I worded that badly so read the post again... it says pretty much the same thing though.

Using my new notation, what it actually says is not only that for each , . I mean, you would take one horse and say "this horse is all the same colour" would you? There's an implicit assumption about the size of the set.

Although, I've just thought about this a bit more, and I might be leading you up the wrong street slightly. When you assume it's true for a set of size k and show that it's true for a set of size k+1, what you do is take two subsets of size k from the set of size k+1; this assumes that the intersection of these two subsets is non-empty. [That is, there is a horse which lies in both of the size k subsets.] Can you think of a k for which this doesn't work? So how big should your base set be?

These are basically two ways of saying the same thing; one is a common-sense approach and the other is the mathematical approach.

EDIT: And for what it's worth this pseudo-proof does generalise, when corrected, to a very important result, which I'll tell you if you're interested (but only after you've worked out where the proof falls).
So it's when there are two horses? Since if you take two subsets(say A and B) in the set of 2 horses then the intersection of the A and B will be empty?
10. (Original post by JBKProductions)
So it's when there are two horses? Since if you take two subsets(say A and B) in the set of 2 horses then the intersection of the A and B will be empty?
Yup. So basically your "true for k implies true for k+1" only works when , so your base case needs not 1 horse, but 2.
11. (Original post by nuodai)
Yup. So basically your "true for k implies true for k+1" only works when , so your base case needs not 1 horse, but 2.
Thanks, I understand it now. Btw what was the other resultf you was talking about? I'm interested in it now.
12. (Original post by JBKProductions)
Thanks, I understand it now. Btw what was the other resultf you was talking about? I'm interested in it now.
It's really not very interesting, it's just important because it saves a lot of work. The result is essentially that if any pair of horses are the same colour, then all horses are the same colour. But we don't have to be talking about horses and colours, we could be talking about anything. It means that if we can show that something is true for an arbitrary pair, and if that thing being true for some set of size k means that it's true for a set of size k+1, then it's true for everything; and checking these first two things is often easier than checking everything.
13. (Original post by nuodai)
It's really not very interesting, it's just important because it saves a lot of work. The result is essentially that if any pair of horses are the same colour, then all horses are the same colour. But we don't have to be talking about horses and colours, we could be talking about anything. It means that if we can show that something is true for an arbitrary pair, and if that thing being true for some set of size k means that it's true for a set of size k+1, then it's true for everything; and checking these first two things is often easier than checking everything.
Thanks!

### Related university courses

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: April 8, 2011
The home of Results and Clearing

### 2,504

people online now

### 1,567,000

students helped last year
Today on TSR

### University open days

1. Keele University
Sun, 19 Aug '18
2. University of Melbourne
Sun, 19 Aug '18
3. Sheffield Hallam University
Tue, 21 Aug '18
Poll
Useful resources

### Maths Forum posting guidelines

Not sure where to post? Read the updated guidelines here

### How to use LaTex

Writing equations the easy way

### Study habits of A* students

Top tips from students who have already aced their exams