3 ms·
This is standard induction: let P(n) be some statement about the number n. If you can establish that P(n) implies P(n+1) for all n >= 1, and that P(1) is true,
by joppy 5y ago
This is standard induction: let P(n) be some statement about the number n. If you can establish that P(n) implies P(n+1) for all n >= 1, and that P(1) is true, then P must be true for every positive integer. You can find many examples by googling for “induction proof”.
The problem in the proof is that the inductive step P(n) implies P(n+1) only holds for n >= 3, and so the fact that P(1) is true does not imply anything for the larger integers.
- didibus 5y agoOkay, but my issue and I think the one of the OP is that even for n >= 3 how did they prove that all horses are the same color for n >= 3?
- dack 5y agoYeah this is why I'm confused as well. I don't follow how if we assume n are the same color, that it implies anything about n+1. It sounds like the article is saying that the N+1 logic makes sense for n > 2, but I don't see how it does.
- ashtonbaker 5y agoAssume (accept without questioning) that it’s a property of the universe that any group of 2 horses are the same color. Now, say you have a group of 3 horses, A, B, and C. You can use your knowledge about groups of 2 horses here: A and B must be the same color because they are a group of 2 horses. B and C must be the same color for the same reason. So all the horses are the same color. You can now use the proof for groups of 3 horses to prove the same fact about groups of 4 horses, and so on. The flawed inductive proof tries to generalize this argument to all groups of n and n+1 horses. That is, assume the property is true for groups of n horses, and show that it logically follows that it’s true for groups of n+1 horses. The structure of the argument is the same as my 2/3 horses example. However, you can’t use an argument like that for any value of n, as it isn’t true for n=1. That is, it’s not true that if every group of 1 horses is the same color (a true fact in nature) then it follows that every pair of horses is the same color.
- joppy 5y agoIt’s more like “in a world where every group of n horses are the same colour”, no matter of whether that world is the real world or not, “prove that any group of n+1 horses are the same colour”. This inductive step proves nothing about the real world, it needs a base case to kick things off. If you can prove it true for n=5 say, then the inductive step gives you every higher number.
- jpmoral 5y agoThe idea is that if it holds for n = 3 then it holds for n > 3. The way to show that it holds for n = 3 is to show that it holds for n = 2, which it doesn't.
- amalcon 5y agoIt's not proven in a vacuum: it's proven under the assumption that it's true for N-1. E.g. if we assume that all groups of 2 horses are the same color, we can prove that all groups of 3 horses are by labelling them A, B, C. A and B are the same color because they are a group of 2; B and C are the same color because they are also a group of 2; A and C are the same color transitively (or because they are also a group of 2). Therefore A, B, and C are the same color. This step is logically sound, and you can do this for any N greater than three. The problem is that this fails when tried for N=2, because then each sub-group can have only one horse in it. We already know that each horse is the same color as itself, so we don't actually reveal any new information by doing this. Since it doesn't work for N=2, the base assumption used for the N=3 case is incorrect.