Is "Strong Induction" not actually stronger than normal induction?

Question

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.

Answer 1

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.

Answer 2

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.

Answer 3

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

Answer 4

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