# Strong Induction proofs done with Weak Induction

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.

-
By "strong" and "weak" I assume that you say that the "weak" induction is when we only assume the precedent case holds, and the "strong" one is when all precedent cases are assumed? –  Patrick Da Silva Feb 11 '12 at 22:56
Yes, maybe a better term would have been incomplete or complete? There are many different ways to state it. –  gsingh2011 Feb 11 '12 at 23:14
There is no better term, it just required precision. It's fine! –  Patrick Da Silva Feb 11 '12 at 23:20
@gsingh2011: Strong induction doesn't have "base cases", it has special cases. See this answer. –  Arturo Magidin Feb 12 '12 at 3:42

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,

-
This helps a lot. So the only difference between two proofs of "strong" and "weak" induction would be statement of the induction hypothesis. However, in both cases, the induction hypothesis would be mean the exact same thing. And in both cases, the validity of the induction hypothesis needs to be backed by multiple base cases if necessary (as many strong induction proofs have multiple while weak have a single base case, this shows that you would still need the multiple base cases for weak induction). –  gsingh2011 Feb 11 '12 at 23:25
To sum it up, yeah. –  Patrick Da Silva Feb 11 '12 at 23:45

Statements that say that two propositions are equivalent have to be done carefully, because the background theory is important.

1. Induction (or "weak" induction): Let $S\subseteq \mathbb{N}$ be such that:

• $0\in S$; and
• For all $n\in\mathbb{N}$, if $n\in S$ then $s(n)\in S$.

Then $S=\mathbb{N}$.

2. Strong induction: Let $S\subseteq \mathbb{N}$ be such that:

• For all $n\in\mathbb{N}$, if $\{k\in\mathbb{N}\mid k\lt n\}\subseteq S$ then $n\in S$.

Then $S=\mathbb{N}$.

Above, $s(n)$ is the successor function.

The main difficulty is to establish exactly what our "background" is. The induction Schema makes sense in the context of Peano's postulates; Strong induction requires a defined property of $\lt$.

Moreover, it is not the case that induction and strong induction are equivalent axioms! That is, if we take the other four Peano axioms,

1. $0\in\mathbb{N}$.
2. If $n\in\mathbb{N}$, then $s(n)\in\mathbb{N}$.
3. For all $n\in\mathbb{N}$, $0\neq s(n)$.
4. If $s(n)=s(m)$ then $n=m$.

then it is not true that Axioms 1-4 + Induction yields a theory equivalent to Axioms 1-4 + Strong induction, even if you throw in an order so that you can state Strong induction!

To see this, consider a disjoint union of two copies of the natural numbers; let's call one copy the "green" natural numbers, and the other copy the "purple" natural numbers (I usually use blue and red, but let's avoid politics this year...). We interpret the primitives as follows: $\mathbb{N}$ is the set that contains all green and all purple natural numbers. $0$ corresponds to the green $0$. If $n$ is green, then $s(n)$ is the green $n+1$; if $n$ is purple, then $s(n)$ is the purple $n+1$. The order is defined as follows: if $n$ is green and $m$ is purple, then $n\lt m$. If both $n$ and $m$ are of the same color, then $n\lt m$ if and only if $n$ is smaller than $m$ in the usual order.

This model satisfies Peano's axioms 1 through 4; it also satisifies the strong induction postulate.

However, in this model, the set $S$ of all green natural numbers satisfies the hypothesis of "Induction" but is not all of $\mathbb{N}$: green $0$ is in $S$, and if $n$ is a green natural number, then so is $s(n)$. This means that this set is not a model for Peano arithmetic. So it is false that weak and strong induction can be swapped with one another and yield equivalent theories with the other four Peano postulates.

However, if we add a further property, namely

For every $n\in\mathbb{N}$, either $n=0$ or else there exists $m\in\mathbb{N}$ such that $n=s(m)$;

then the first four axioms, plus this property, plus strong induction does imply weak induction.

I guess the moral is that the statement "weak induction is equivalent to strong induction" has to be made precise before it is true; one has to specify a "background theory" or a set of "background properties" which we may take for granted before the equivalence is established. But in the presence of those "background properties", then Patrick Da Silva's argument is the standard one: any proof (over a suitable theory for $\mathbb{N}$) that uses induction can be reshaped (in a straightforward way) to become a proof that uses strong induction instead; and any proof that uses strong induction can be reshaped (in a more-or-less algorithmic manner) into a proof that uses weak induction.

-
Great answer @Arturo ! Where could I read more about non-standard models (of anything) such as the one you described? –  magma Feb 24 '12 at 15:41