I've been told that strong induction and weak induction are equivalent. However, in all of the proofs I've seen, I've only seen the proof done with the easier method in that case. I've never seen a proof (in the context of teaching mathematical induction), that does the same proof in both ways, and I can't seem to figure out how to do them myself. It would put my mind at ease if I could see with my own eyes that a proof done with strong induction can be completed with weak induction. Does anyone have a link to proofs proved with both, or could anyone show me a simple proof here? I'm more interested in proofs were strong induction is the easier method.
Induction – Strong Induction Proofs Done with Weak Induction
induction
Related Solutions
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:
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)$.
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.
Best Answer
The idea is that if something is proved with "strong" induction, i.e. by assuming all preceding cases, then you can use "weak" induction on the hypothesis "all preceding cases hold". Let me explain with mathematical notation, perhaps it'll be a little clearer.
Suppose you want to prove a proposition for all $n \ge 1$, i.e you want to show that for all $n \ge 1$, $P(n)$ is true, where $P(n)$ is some proposition. Define the proposition $Q(n)$ by "$P(k)$ is true for all $k$ with $1 \le k \le n$". Then showing that $P(n)$ is true using "strong" induction is equivalent to showing that $Q(n)$ is true using "weak" induction. But $P(n)$ is true for all $n$ if and only if $Q(n)$ is true for all $n$, hence the proof techniques are completely equivalent (in the sense that using one technique or the other has the same veracity ; it doesn't mean that one is more or less complicated to use than the other).
At some point in the study of mathematics you stop making the distinction between "strong" and "weak". You just say that you're using "induction". I wouldn't be sure that you stop distinguishing this if you study logic though, but let's just leave those kind of problems to logicians, shall we.
Hope that helps,