undefined | Better HN

0 pointsindianboy424y ago0 comments

Isn't that just how proof by induction works? You assume the hypothesis is true for n and prove it for n+1

0 comments

3 comments · 1 top-level

ahartmetz4y ago· 2 in thread

But you don't go from n-1 to n. You'd have to start at the infinite horses case where the conjecture must be true for, well, who knows what reason. Intuitively, "Consider the conjecture proven. If we reduce the difficulty, it's still proven" just seems obviously wrong.

Arcsech4y ago

There are two parts to an inductive proof:

1. Assuming that a property is true for N, prove that it is true for N+1.

2. Prove that the property is true for some concrete N where the proof for step 1 holds.

The trick is that you need to be sure to pick your concrete N correctly, as the article demonstrates. In particular, the problem with the "solution" in the article is that the proof given for step 1 doesn't hold for N=1, because N+1=2, and then just follow the rest of the argument from the article.

runarberg4y ago

I still don’t quite understand. The inductive step shows n + 1 → n right? However with any positive base case b, n → n + 1 isn’t certain for any integers above b, only below it.

Say you’ve proved the case for n = 3 and that n + 1 → n. Then you’ve proven that 2 + 1 → 3, and by induction 1 + 1 → 2, However you’ve never proven it for n = 4 because n → n + 1 has never been established.

Or am I missing something here?

EDIT: I’ve seen in other posts that this the problem with OP is that it hides the transitivity of the operation. In fact the failure of the proof was that it proved transitivity with a false premise. If transitivity was true, then using n + 1 → n is just fine. The Wikipedia article for this statement is actually a lot clearer. https://en.wikipedia.org/wiki/All_horses_are_the_same_color

1 more reply

j / k navigate · click thread line to collapse