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

Example of a proof of a theorem using weak(ordinary) induction

The two types of inductions have process of proving P(a) and "for all integers $n \ge b, P(n)$" as a result in common.

For example, in the proof of the following question, we can use weak induction instead of strong induction, and using weak(ordinary) induction makes the proof simpler and shorter than the strong form of induction. So what's the benefit of using strong induction when it's replaceable by weak induction?

[EDIT] As requested, here's the weak induction version of the question. Plus, I changed the $s{k_1}$ part in red in the weak induction after reading answers. I now understand using weak induction doesn't prove the statement.

Source: Discrete Mathematics with Applications, Susanna S. Epp

• Do you mind spelling out the weak induction proof you have in mind? I can't figure it out from your clip notes. Feb 28, 2016 at 8:55
• @GitGud I added my thoughts in gray and red in the proof. Did you see it? Feb 28, 2016 at 8:58
• @GitGud I uploaded the weak induction proof of the question. Feb 28, 2016 at 11:56
• @buzzee: read my answer. the reason you can't just change the words "strong" to "weak" is that the strong proof uses the assumption $s_{k-1}=5^{k-1}-1$. you don't have this assumption in the weak setting. but you do have it in the strong setting. Feb 28, 2016 at 12:43

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}$.

• Good example but one could reason like that: since strong and weak induction are (provably) equivalent, there cannot be a statement that can be proved by one of them and not by the other. How is it possible? Feb 28, 2016 at 12:12
• @MarcoDisce See Brian's answer, specifically what I quote in my first comment to it. Feb 28, 2016 at 12:39
• @MarcoDisce: as Git Gud says, the fact that weak and strong induction are logically equivalent does not mean that weak induction can prove $P(k+1)$ solely on the basis of $P(k)$. You need a different $P(n)$ altogether. Feb 28, 2016 at 12:40

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.

• "The conversion requires changing the proposition $P$".This, I suspect, is what the OP is missing. Can't be sure because I don't really understand what weak induction proof the OP has in mind. Feb 28, 2016 at 8:58
• @GitGud: I think that the OP simply didn’t realize that the argument presented by Epp actually is using strong induction in a way that is essential in the form in which the argument is presented. As I read it, the OP thought that checking the truth of $P(1)$ and using the truth of more than just $P(k)$ to get that of $P(k+1)$ were unnecessary in the argument as presented. (I could, however, be doing the OP an injustice.) Feb 28, 2016 at 9:00
• In your answer, "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$" Since only "$P(0)$ is true" and there's no '$P(1)$ is true' in that basis step part, it should be $k\ge 0$, not $k\ge 1$ in the induction step. Feb 28, 2016 at 9:42
• @buzzee: No, it should not: the induction step as given requires that both $P(k)$ and $P(k-1)$ be true, so starting at $k=0$ makes no sense. If the induction step required only that $P(k)$ be true, I could write ‘and $k\ge 0$, but that’s not the case, so I can’t. And that is why this really is an example of strong induction. Feb 28, 2016 at 9:51
• In the given proof, k is the upper limit range of the i. The induction step supposes ∀0≤i≤k, P(i) and then proves p(k+1). In this case, if k=0 we can't suppose P(k-1)=P(-1) be true, which is a counterexample to your claim that the given step requires both P(k) and P(k-1) be true. Feb 28, 2016 at 10:18

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.

• Could you help me to obtain that statement that will allow us to demonstrate it with weak induction? Apr 18, 2020 at 1:40
• For every integer $n \ge 2$ we have that each integer $2\le m \le n$ is divisible by a prime number. (Induction on $n$.).
– quid
Apr 18, 2020 at 1:58
• So, " we have that each integer $2≤m≤n$ " is now a given information? Apr 18, 2020 at 17:09
• Yes, this is the statement to prove. You prove it for $n=2$. Then you assume it as hypothesis for $n$ and prove it for $n+1$. The case $n=2$ is basically the same as only $m=2$ is posisble. For $n+1$.you can say let $m$ with $2 \le m\le n+1$. Case 1. $m \le n$. This is direct by hypothesis. Case 2. $m=n+1$. Give the argument as in answer.
– quid
Apr 18, 2020 at 17:30
• Well, but if the claim says that $m$ holds for $2\leq m \leq n$, why you prove $2$? Apr 18, 2020 at 19:31

Often it's conceptually easier to think about an argument in terms of strong induction. It is true that you can always recast the proof in terms of weak induction (though I don't exactly follow the comments you're making on the example in the question--what you have to do to make the argument use weak induction is change the statement you are proving by induction from "$P(k)$" to "$P(i)$ is true for all $i\leq k$"), but it is a bit simpler to use strong induction directly. I could turn your question around and ask you: why should you ever use weak induction, when it's replaceable by strong induction? It's largely a matter of taste, and which version leads to a more easily understood proof for the particular problem you are trying to solve.

Besides that, the concept of strong induction generalizes better than weak induction. Strong induction works on any well-ordered set (or even more generally, any set equipped with a well-founded relation). This generalized form of induction, called transfinite induction, is extremely important in set theory and also has applications in many other areas of mathematics, and cannot be reduced to weak induction the same way ordinary induction can. (Well, there is sort of a "weak induction" version of transfinite induction given by splitting into successor and limit cases, but it is still rather different from ordinary weak induction because of the limit cases besides $0$. And this doesn't work at all when doing induction on general well-founded relations.)

• I know "well-ordering principle", but haven't heard or read about "well-ordered set" before. Feb 28, 2016 at 9:03
• Does "well-ordered set" mean nonempty subsets in the following explanation? "Well-Ordering Principle. Every nonempty subset of the positive integers has a smallest element." sites.millersville.edu/bikenaga/math-proof/induction/… Feb 28, 2016 at 10:21
• "Well-ordered set" refers to any set (not necessarily a subset of $\mathbb{N})$) with an ordering which satisfies the well-ordering principle. See en.wikipedia.org/wiki/Well-order. Feb 28, 2016 at 19:23