Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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. –  Brian M. Scott Mar 20 '13 at 4:05
    
@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. –  Noble. Mar 20 '13 at 4:08
    
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. –  Brian M. Scott Mar 20 '13 at 4:12
add comment

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  Noble. Mar 20 '13 at 4:18
    
@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. –  Ross Millikan Mar 20 '13 at 4:25
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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