http://mathcenter.oxford.emory.edu/site/math125/strongInductionEquivalence/
In the link given above, I'm not sure that the proof of 'whenever weak induction holds, strong induction holds' is correct. This is because in the proof the second hypothesis of strong induction has been assumed in order to prove that P(n) holds by weak induction. Now according to me, to show that whenever weak induction holds, strong induction holds, you would have to show that the statement P(n) holds on strength of the basis step and the second hypothesis of weak induction alone. I have no qualms about assuming that the second hypothesis of strong induction holds and then proving that P(n) holds by strong induction, but I believe that such an assumption (second hypothesis of strong induction) should not be an essential part of proving P(n) by weak induction. Otherwise what we get as a conclusion is that 'whenever weak induction holds on strength of the second hypothesis of strong induction (besides the hypotheses of weak induction), then strong induction holds', instead of 'whenever weak induction holds, strong induction holds'. I believe that not all statements proved by weak induction have to assume the second hypothesis of strong induction in order for the proof to work.
Where have I gone wrong? Am I missing something?
Thanks for your time. Sayan
