- prove base case), and (this is called the
- for an arbitrary , prove , assuming (this is the inductive step)
More concisely, the inductive step requires you to prove for all .assuming
The intuition for why strong induction works is the same reason as that for weak induction: in order to prove , for example, I would first use the base case to conclude . Next, I would use the inductive step to prove ; this inductive step may use but that's ok, because we've already proved . I would then use the inductive step to conclude ; this may use both and , but that's okay because we've already proved and . Next, I would again use the inductive step to conclude ; as before, this may use , , or , but this is not a problem since we have already proved those three facts. Similarly, we can use the inductive step to conclude P(4), P(5), etc.
Note that you can always use strong induction instead of weak induction. Using weak induction is just a matter of style: by avoiding unneeded assumptions, you reduce the complexity of your proof, and clearly indicate to the reader what assumptions you are actually planning to use. I often start inductive proofs by not specifying whether they are proofs by strong or weak induction; once I know which inductive hypothesis I actually need, I go back and fill in the beginning of my inductive step.