# 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:

Suppose you know the following:
1. You can prove
2. You can prove for an arbitrary , assuming for all ,
Then you can conclude , using only the basic weak induction principle.
Assume the statements that are given in the claim. Let be the statement "for all , P(k)." We will show and for an arbitrary , assuming .

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.

Now we will prove , assuming . So we want to show that for all , that holds. Choose an arbitrary . There are two cases to consider:

• if , then . Thus we can apply to conclude .
• the only remaining case is . In this case, gives us , , , ..., . Thus we can use the second proof given in the assumptions to conclude , which is the same as .
This completes the weak induction proof that . We can then use this to prove the actual claim (that ) as follows: choose an arbitrary ; we want to show . We know is true, so for every holds. In particular, for , we can conclude , which is the same thing as . Thus is true.