# Strong induction

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:

1. The base case. We prove that $P(1)$ is true (or occasionally $P(0)$ or some other $P(n)$, depending on the problem).

2. 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.