In both sections, I went to through couple of questions on mathematical induction. Most of the times, we could use induction to prove a statement holds for all natural numbers. The framework for (weak) induction is as follows.
- Identify the statement P(n).
- Basis step: prove P(1).
- Induction step: prove that if P(n) then P(n+1).
- Conclusion: \forall n\ P(n).
Sometimes, we use strong induction. The framework for strong induction is as follows.
- Identify the statement P(n).
- Basis step: prove P(1).
- Induction step: prove that if \forall k\in\mathbb{N} \left(k < n\Rightarrow P(k)\right) then P(n).
- Conclusion: \forall n\ P(n).
Hello Roy,
I am wondering, how does the induction step of strong induction differ from that of the weak induction? Does the “k” here different from the “n” above in the weak induction?
Thanks,
Anson
The difference between strong induction and weak induction is the induction hypothesis used in the induction steps. Morally speaking, in the strong induction hypothesis we assume all the earlier results hold, and we use them to prove the result for n, while in the weak induction, we only use the previous result to show the next one. If you could understand that, then you will see it doesn’t matter which variables you choose.