What's the benefit of using strong induction when it's replaceable by weak induction?

The other two answers are of course correct, but given your comments on Brian's answer, I will give a more down-to-earth response: in all likelihood, the proof you have in mind using weak induction is not correct. You should do as Git Gud says and spell out exactly what alternative proof you have in mind.

Why do I suspect you don't have a weak proof of the claim Epp proves? Because, as Brian illustrates, if you take $P(n)$ to be the statement $$s_n=5^n-1$$ you can't show $P(k+1)$ solely on the basis of $P(k)$.

Why? Just try it. By definition, $$s_{k+1}=6s_k-5s_{k-1}$$ and by the hypothesis $P(k)$, we can substitute $5^k-1$ for $s_k$, so we have $$s_{k+1}=6(5^k-1)-5\color{blue}{s_{k-1}}$$ But what do we do with $s_{k-1}$? We don't have any hypothesis on it! Only if we use strong induction can we use the hypothesis $P(k-1)$ and thereby substitute in $5^{k-1}-1$ for $s_{k-1}$.


In the example that you’re discussing, you can not leave out proving $P(1)$. To see this, change the definition of the sequence slightly: $s_0=0$, $s_1=5$, and $s_k=6s_{k-1}-5s_{k-2}$ for $k\ge 2$. As before, let $P(n)$ be the formula $s_n=5^n-1$. Then $P(0)$ is true, and the induction step proceeds exactly as before to show that if $P(i)$ is true for all integers $i$ from $0$ through $k$, and $k\ge 1$, then $P(k+1)$ is true: there is nothing in that part of the argument that depends on the value of $s_1$. However, it is obviously not the case that $P(n)$ is true for all integers $n\ge 0$, since $P(1)$ is false.

The induction step requires knowing that $P(k)$ and $P(k-1)$ are true: without both of those, you cannot derive the truth of $P(k+1)$. And that means that to get $P(2)$, you need to know not only that $P(0)$ is true, but also that $P(1)$ is true. Thus, this argument really does use strong induction.

In fact the two forms of induction are logically equivalent, and every argument using strong induction can be converted to one that uses ordinary induction, but the conversion requires changing the proposition $P$. I can’t remember whether Epp proves the equivalence; if she does not, leave a question, and I’ll explain further.

In practice one simply uses whatever form of induction is convenient. I really wish that elementary texts didn’t make such a big deal of the difference: it’s not really very important, apart from the fact that so-called strong induction is in many ways a better introduction to more sophisticated forms of induction like structural and transfinite induction.


Strong Induction is more intuitive in settings where one does not know in advance for which value one will need the induction hypothesis.

Consider the claim:

Every integer $n \ge 2$ is divisible by a prime number.

Using strong induction the proof is straightforward. It is true for $n=2$, as $2 \mid 2$ and $2$ is prime.

Assume the statement true for $2 \le a \le n$. We show $n+1$ is divisible by a prime number.

If $n+1$ is a prime number, then as $(n+1) \mid (n+1)$, the claim is proved. If $n+1$ is not a prime number then there exists some proper divisor $a\mid (n+1)$, so $2 \le a \le n$.

By induction hypothesis, we know that $a$ is divisible by a prime number $p$. Since $p \mid a $ and $a \mid (n+1)$ it follows that $p \mid (n+1)$ and the proof is complete.

If you want to do this with weak induction you will have to change the statement you want to prove to something less intuitive.