[throwvirtever]

I feel like I'm too ignorant of mathematics to be confused by this "proof".

When you set out to prove "for any set of n horses, every horse in that set has the same color" and you then "suppose for all sets of n horses, every horse in the set has the same color" as a first step, you're messing with a tautology, aren't you? I mean if you've supposed that it's true for all, it's definitely true for any, right?

What am I missing that makes the problem subtle and interesting, rather than just blatantly circular from the start?

[mannerheim]

The inductive step assumes the hypothesis is true for n, and proves it for the n+1 case. The overall proof is then for all positive integers, n.

[na85]

But why would anyone assume that n horses, for arbitrary n, are the same color?

That's absurd. Anyone who's ever seen a field with horses in it would trivially know that this is a faulty assumption to make.

You might as well say "We can prove that coconuts can migrate. First, assume that coconuts can migrate. Thus, coconuts migrate".

It's equally valid logic.

[phkahler]

>> The inductive step assumes the hypothesis is true for n

You don't get to assume the thing you're trying to prove is true as a part of the proof that it's true. The only time we assume something like that is in a proof by contradiction, where the contradiction implies either an error in our logic, or an error in the assumptions.

[shkkmo]

There are two steps of an inductive proof

one is proving the inductive rule that: p(n) implies p(n+1)

the other is proving that there exists some number i for which p(i) is true. This, combined with the proof of the inductive rule, allows you to prove that p(n) is true for all n >= i.

[LanceH]

In simpler terms the two steps for this problem are:

1. There exists some number of horses where all horses are of the same color. This is obviously true when you have 1 horse.

2. The second step is that you have to prove that if you have some number of horses n, and they are all of the same color, then if you add another horse all the horses are of the same color.

He's saying there is some set of n+1 horses, n of which are of the same color. Then he makes the (false) claim that removing one horse at random leaves you with n horses, which therefore must all be of the same color. This is incorrect because the assumption is that there is a set of n horses, not "if you have n number of horses they are all the same color.

The base case of n=1 is just fine. It's adding a randomly colored horse to a set of horses that doesn't always result in an n+1 set of like-colored horses. He doesn't even explain the illogical step correctly, so the whole thing is a mess.

[ajuc]

It's not circular, because you aren't using the assumption A in the final proof, you are just using the implication A(N) => A(N+1) in the final proof.

the final proof is:

    A(1) is true
    AND
    A(N) implies A(N+1)
    means that
    A(N) is true for all N >= 1

the assumption that A is true for N was just used as a condition in the implication

If A(N) is false in general - you would realize that despite assuming it - because the implication or the base case couldn't be proven.