Hacker News Reader

Comment by mcphage | Hacker News Reader

Their inductive step is perfectly valid. However, requires a group of horses with one removed to still have a horse remaining. Using N=1 is an incorrect base case. Had they proved the N=2 base case, their entire argument would work.

Of course, you can’t prove the N=2 base case, so that’s why the argument uses the wrong base case.

View on HN

The inductive step introduces a premise that “requires a group of horses with one removed to still have a horse remaining.” It is not valid to introduce this premise. The inductive step is not valid.

The inductive step would work just fine with the correct base case.

Nah, the inductive step is simply incorrect. For it to be correct it needs to say "for n > 1 the following is true", but it doesn't, the statement isn't true since they forgot to add that part. And if you added "for n > 1" to make the inductive statement correct then it is obvious where the reasoning goes wrong.

In other words, the base case is correct, in all sets of 1 horse all horses has the same color. The inductive step is not correct. Even if you changed the where you put the base case to N=2, the inductive steps reasoning is still wrong as long as it doesn't include the "for n > 1" part.

You wouldn't need to add "for n > 2" to the inductive step, any more than you need to include "for n > 1" for arguments where the base step is 1, or "for n > 20" for arguments where the base step is 20.

You need to do it because you prove the statements separately. Currently the inductive step statement is false, it says that applies for all sets. It doesn't.

Note that you can use false intermediate steps like that and still reach a correct conclusion. Then the conclusion is correct but the proof is still wrong since the steps you used were wrong.

It is completely valid to do that. The induction starts at n=2. Nothing unusual about it, e.g. you can show that 2^n >10 for n>=4 that way.

I mean “valid” in the mathematical/logical sense. It does not follow from the stated assumptions that n > 1, in the inductive step is this proof.

This has nothing to do with the idea that it can be common practice to prove claims of the form for all n > N, P(n) by induction when N is a number like 4. Yes there is a perfectly valid way to use proof by induction to do such proofs. Has nothing to do with this blog post.

In a proof, you can absolutely assume something like "A is true", you do it as a part of a sub-proof. Then anything you prove in the sub-proof like "B is true" can be brought back into the main proof in the form: A implies B is true.

The blog post glosses over this assumption and thus ends up concluding "p(n) implies p(n+1)" instead of "p(n) implies (n>1 implies p(n+1))”

Reply on news.ycombinator.com