Proof:Strong induction is equivalent to weak induction
You may think that strong induction is stronger than weak induction in the sense that you can prove more things using strong induction than you could using only weak induction (the names certainly suggest that!). In fact, this is false: you can systematically convert a proof by strong induction to a proof by weak induction by strengthening the inductive hypothesis. Here is a formal statement of this fact:
- You can prove
- You can prove for an arbitrary , assuming for all ,
To see , we want to show that for any , holds. But the only that is less than or equal to 0 is . The first assumption given in the claim is that holds, so holds for all , and thus holds.
- if apply to conclude . , then . Thus we can
- the only remaining case is use the second proof given in the assumptions to conclude , which is the same as . . In this case, gives us , , , ..., . Thus we can