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

Claim (see proof):

Suppose you know the following:

1. You can prove [math]P(0) [/math]
2. You can prove [math]P(n+1) [/math] for an arbitrary [math]n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/Natural_number}{\mathbb{N}} [/math], assuming [math]P(k) [/math] for all [math]k \leq n [/math],

Then you can conclude [math]\href{/cs2800/wiki/index.php/%5Cforall}{\forall} n \href{/cs2800/wiki/index.php/%5Cin}{\in} \href{/cs2800/wiki/index.php/Natural_number}{\mathbb{N}}, P(n) [/math], using only the basic weak induction principle.