Hacker News new | past | comments | ask | show | jobs | submit login

Why can’t you asume S(2)? Is it not included in the inductive hypothesis S(k)?



So the base case that they prove is S(1). And the inductive step is to show: S(1) ->(implies) S(2) -> S(3) -> S(4) -> ....

Or to write it more succinctly, that S(n) -> S(n + 1) assuming S(n) is true.

In this particular problem, the proof that is provided can be used to show S(2) -> S(3), that S(3) -> S(4), etc... are valid and true.

However, the proof could NOT be applied to show that S(1) -> S(2).

So whilst you CAN assume S(2) is true in a proof, the whole inductive chain needs to be attached to a valid base case.


The page gives a better explanation than I could :-)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: