I'm proving something via induction (which has turned into strong induction) and there's something I've never really fully understood about strong induction. The name "strong induction" does make it sound like a more 'powerful' version of induction - but surely this is somewhat counter-intuitive (at least in my mind) given the implications of strong induction?

Just going to the definition of strong induction, it lets you assume that not only does the inductive hypothesis hold for some integer, but also that it holds for all integers less than it as well.

In my mind, assuming something is true for more than one cases isn't as powerful as assuming it's true for only one value and using that as a basis. In my proof, I've had to use not only the $n=k$ assumption, but also the assumption it holds for $n = k-1$, and I really can't see how this is 'strong' or 'complete' induction.

I'm sure someone can enlighten me! Thanks everyone.

  • 1
    $\begingroup$ The two are equivalent: any result that can be proved with one can be proved with the other, though sometimes in a slightly roundabout manner. Despite the names, neither is stronger or weaker than the other in power. $\endgroup$ Mar 20, 2013 at 4:05
  • $\begingroup$ @BrianM.Scott Thanks Brian, I understood they're equivalent but not really why it was ever called "strong". One of my professors last year implied (probably inadvertently) that it's more powerful, and I just couldn't see how it was possible. Thanks for clearing it up though. $\endgroup$
    – Noble.
    Mar 20, 2013 at 4:08
  • 1
    $\begingroup$ You’re welcome. I’ve always assumed that the strong in strong induction refers to the fact that you use an apparently stronger induction hypothesis than in so-called ordinary induction. But there’s no denying that it’s a somewhat misleading name. $\endgroup$ Mar 20, 2013 at 4:12
  • $\begingroup$ @BrianM.Scott To prove a statement with weak induction that can not be proved only with assuming $p(k)$ holds a property $p$, i need necessarily have that information in the statement? per example, in some statement must say: "Prove for $n > k$ holds for $p$ property knowing that $k < m \leq n$ holds the property". And later prove the $k$ base case, and prove that for $n+1$ holds? $\endgroup$ Apr 18, 2020 at 19:43
  • $\begingroup$ @EduardoS.: Do you mean that we’re taking the proposition $P(n)$ to be ‘$p(m)$ is true for $k<m\le n$’, so that $P(n+1)$ is ‘$p(m)$ is true for $k<m\le n+1$’, and then using weak induction to prove that $P(n)$ implies $P(n+1)$? If so, yes, that’s how to convert a proof by strong induction into an equivalent one by weak induction. $\endgroup$ Apr 18, 2020 at 19:52

4 Answers 4


I believe the crux of Noble's question, as presented in his recent comment, is:

[B]ut I can't see how assuming it's true for more than one value is more powerful.

In logical terms, we say that a statement $A$ is stronger than a statement $B$ if $A \implies B$. It is clear that -- forgive me for writing $\wedge$ for and when discussing logical statements --

$A \wedge A' \implies A$,

and more generally

$A_1 \wedge A_2 \wedge \ldots \wedge A_n \implies A_n$.

In other words, assuming a set of things is stronger than assuming a subset of things.

This is the sense in which strong induction is "stronger" than conventional induction: for your predicate $P$ indexed by the positive integers, assuming $P(1) \wedge \ldots \wedge P(n)$ is stronger than just assuming $P(n)$. In more practical terms, the more hypotheses you assume, the more you have to work with and it can only get easier to construct a proof.

Now let me supplement with further comments:

  1. Nevertheless the principle of mathematical induction implies (and, more obviously, is implied by) the principle of strong induction, via the simple trick of switching from the predicate $P(n)$ to the predicate $Q(n) = P(1) \wedge \ldots P(n)$.

  2. Here is a further possible source of confusion in the terminology. Suppose I have a theorem of the form $A \wedge B \implies C$. Someone else comes along and proves the theorem $A \implies C$. Now their theorem is stronger than mine: i.e., it implies my theorem. Thus when you weaken the hypotheses of an implication you strengthen the implication. (While we're here, let's mention that if you strengthen the conclusion of an implication, you strengthen the implication.) This apparent reversal may be the locus of the OP's confusion.

  • $\begingroup$ Why $a\to c$, implies $a \land b \to c$? $\endgroup$ Apr 18, 2020 at 19:51
  • $\begingroup$ @Eduardo: Well, for instance because $a \wedge b \rightarrow a$ and "$\rightarrow$" is transitive. (I didn't want to just answer "Think about it," but it couldn't hurt!) $\endgroup$ May 21, 2021 at 21:19

When you say "assuming something is true for more than one cases isn't as powerful as assuming it's true for only one value" you have the direction wrong. Assuming it is true for one value is one thing, assuming it is true for many values is clearly stronger-you have more to work with. As others have said, you can't prove anything from strong induction that you can't prove from weak induction, but that is a significant result in logic. Bigger assumptions are weaker than smaller ones, because you might need something that is in the big one and not in the small one.

  • $\begingroup$ I'm sure you're right, but I can't see how assuming it's true for more than one value is more powerful. If you can prove something using just the assumption it's true for one integer, why is needing to also assume it for other values to complete the proof stronger? I would have thought that the more assuming at least trivially makes a proof less rigorous? I'm not arguing with you, I'm sure you're correct in what you say, it just doesn't compute with me for some reason. $\endgroup$
    – Noble.
    Mar 20, 2013 at 4:18
  • $\begingroup$ @Noble. The more assumptions you need, the weaker the proof. It is not less rigorous, but you need more input to reach the conclusion. I can prove $x=2 \implies x^2=4$. I can also prove $x=2 \& y=6 \implies x^2=4$. The second is weaker and less useful. $\endgroup$ Mar 20, 2013 at 4:25
  • 1
    $\begingroup$ @RossMillikan It's about the strength of the inference rule. The simple rule is $S(0)\wedge (S(n)\Rightarrow S(n+1))\vdash \forall n S(n)$. The universally quantified statements you get from this inference rule correspond to the $S(n)$ for which you can prove $S(0)\wedge (S(n)\Rightarrow S(n+1))$. If you can prove that statement, you can definitely prove $S(0)\wedge \bigwedge_{k<n+1} S(k)\Rightarrow S(n+1)$ by simple conjunction rules, so the "strong induction" rule for a formula S(n) gives at least as many new theorems over any reasonable base inference system as the weak induction rule. $\endgroup$ Apr 22, 2020 at 15:08

There is no "power difference" between strong induction and "regular" induction: i.e., they can be shown to be equivalent. The term "strong" is a "misnomer", in a sense, in that it is no stronger (nor weaker) than "regular" induction: as I see Brian Scott commented, one way to put this is that what can be shown with strong induction can be shown with induction.

To add to the confusion, and this may be the source of confusion you're struggling with: the terms "stronger" and "weaker" can be used to describe the strength of the assumptions used (in which case, since strong induction has a larger domain of assumptions, it is "stronger" in that sense.), and this use of the terms stronger and weaker is different than what "stronger" and "weaker" mean when describing the power of a theorem: if $A$ implies $B$, but not vice versa, then $A$ can be said to be a stronger theorem.

The fact that "strong" induction is distinguished from "conventional" induction can be used, for practical purposes, as an indicator that the proof proceeds as you suggest: assuming the truth of $P(k)$ for all $k \leq n$. And so strong induction is particularly useful, e.g., to shorten proofs involving *recursive function*s, in which one needs to and like to have the "power" to assume that $P(k)\forall k\leq n$ as opposed simply $P(k), k= n,\;$ in order to prove $P(k+1)$ and hence $P(n)$.


I look at it the following way:

Strong Induction (SI): $[P(1), \ldots ,P(n - 1) \implies P(n)] \implies P(n) \;\forall n \in \mathbb{N}$

Weak Induction (WI): $[P(1) \text{ and } P(n - 1) \implies P(n)] \implies P(n) \;\forall n \in \mathbb{N}$

Although SI $\iff$ WI, I would argue that SI is "stronger" than WI. Indeed, the inductive hypothesis in SI ($P(1), \ldots P(n - 1)$) is stronger than the inductive hypothesis in WI ($P(n - 1)$) because you get to assume more. This means that the inductive step in SI ($P(1), \ldots P(n - 1) \implies P(n)$) is weaker than the inductive step in WI ($P(n - 1) \implies P(n)$) because you use more assumptions to prove the same conclusion ($P(n)$). But since WI and SI both have the same conclusion ($P(n) \;\forall n \in \mathbb{N}$), this in turn means that SI is the stronger result because it has the weaker hypothesis (inductive step). This line of reasoning is borne out by the fact that the proof of SI $\implies$ WI is completely trivial (ignore $P(1), \ldots, P(n - 2)$) whereas the proof of WI $\implies$ SI requires a tiny bit of work (define $Q(n) = P(1) \land \cdots \land P(n)$ and apply WI to $Q$).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.