Strong induction is a type of proof closely related to simple induction.
As in simple induction, we have a statement \(P(n)\) about the whole number \(n\), and we want to prove that \(P(n)\) is true for every value of \(n\). To prove this using strong induction, we do the following:
The base case. We prove that \(P(1)\) is true (or occasionally \(P(0)\) or some other \(P(n)\), depending on the problem).
The induction step. We prove that if \(P(1)\), \(P(2)\), …, \(P(k)\) are all true, then \(P(k+1)\) must also be true. In this step, the assumption that \(P(1)\), …, \(P(k)\) are true is called the inductive hypothesis.
Together, these imply that \(P(n)\) is true for all whole numbers \(n\). (The proof is the same as with simple induction.)
The critical difference between this and simple induction is that in step 2, we do not assume that only \(P(k)\) is true, but \(P(k)\) and all earlier \(P(i)\) for \(i<k\).
It is convenient if the proof of \(P(k+1)\) might depend on not only the previous \(P(k)\) but on any earlier \(P(i)\).
It turns out that this form of induction is actually equivalent to simple induction: anything one can prove with one of them, one can also prove with the other.
