# I want a clear explanation for the Principle of Strong Mathematical Induction

I understood the Principle of Mathematical Induction.

I know how to make a recursive definition.

But I am stuck with how the "Principle of Strong Mathematical Induction (- the Alternative Form)" works?

I could not understand it!

I found many websites explaining it but still could not got the idea.

I will highly appreciate an explanation using. English is my second language and my book is too difficult for me.

-
Did you read this previous question, or this one, or this? – Arturo Magidin Apr 30 '12 at 16:47
This answer from Timothy Gowers may be illuminating. – Austin Mohr Dec 16 '13 at 22:24

The only difference between regular induction and strong induction is that in strong induction you assume that every number up to k satisfies the condition that you wish to prove whereas in regular induction you only assume that some integer k satisfies this condition.

-

Strong induction is induction where you assume that all previous cases satisfy your induction hypothesis, not just the most recent case. Sometimes knowing the previous step just isn't enough. The following well-known theorem is a good example of strong induction: Every natural number factors into a product of irreducibles.

Base case: $n=2$ factors into irreducibles. Now, for the induction step, suppose all numbers less than or equal to $n-1$ factor into irreducibles. Now either $n$ is irreducible, or $n=kl$, where $k$ and $l$ are less than $n$. Now since I can write $k$ and $l$ each as a product of irreducibles (by the induction hypothesis), I can write $n$ as a product of irreducibles.

Note that it would not have been good enough to assume the induction hypothesis only for $n-1$, since knowing that $n-1$ factors tells me nothing about whether $n$ factors. Instead, in my induction hypothesis I assumed all natural numbers less than $n$ factor.

EDIT: Note that irreducible numbers are the same as prime numbers. See the discussion below if you're wondering about my choice of terminology.

-
Yes irreducibles are of course the same as primes in $\mathbb{N}$. But that is in fact a theorem, albeit one we all know, and assuming the vocabulary of the fundamental theorem of arithmetic would be to assume a result that is stronger than what I wished to prove. – Brett Frankel Apr 30 '12 at 4:07
What would have changed if you used the word prime instead of irreducible? – Pedro Tamaroff Apr 30 '12 at 4:12
Well, if all irreducibles are primes, then a ring is a UFD, in which we already know that every element factors (uniquely) into irreducibles/primes. Also, the for what it's worth, the proof as stated generalizes to Noetherian domains, where we induct on the length of chains of principal ideals. – Brett Frankel Apr 30 '12 at 4:16
Sorry, I didn't realize you where considering an arbitrary ring. – Pedro Tamaroff Apr 30 '12 at 4:21
@PeterTamaroff I wasn't. I just didn't want to take unique factorization for granted, since that was what I was proving. – Brett Frankel Apr 30 '12 at 4:23

You have seen regular induction:

$$\forall P() : \left( \begin{array} {rrl} & & P(0) \\ \land & \forall x ~:~ & P(x) \implies P(x+1) \\ \implies & \forall y ~:~ & P(y) \end{array}\right)$$

Now what about when $P(x)$ is defined as $P(x) := \forall z ~:~ z \le x \implies Q(z)$? In other words, instead of "$x$ has property $P$", we are saying "everything less than $x$ has property $Q$".

$$\forall Q() : \left( \begin{array} {rrl} & & \forall z : z < 0 \implies Q(z) \\ \land & \forall x ~:~ & (\forall z : z<x \implies Q(z)) \implies (\forall z : z<x+1 \implies Q(z)) \\ \implies & \forall y ~:~ & \forall z ~:~ z < y \implies Q(z) \end{array}\right)$$

Now look at each part:

$$\forall z : z < 0 \implies Q(z)$$

Since there are no values less than $0$, this is always true, so it can be removed as an assumption.

$$(\forall z : z<x \implies Q(z)) \implies (\forall z : z<x+1 \implies Q(z))$$

Since $\forall z : z<x+1 \implies Q(z)$ is the same as $\forall z : z<x \implies Q(z) \land Q(x)$, this can be simplified to

$$(\forall z : z<x \implies Q(z)) \implies Q(x)$$

And lastly:

$$\forall y ~:~ \forall z ~:~ z < y \implies Q(z)$$

This can be simplified to $\forall y ~:~ Q(z)$, since there is no upper bound on the $+1$ function.

So altogether that is:

$$\forall Q() : \left( \begin{array} {rrl} & \forall x ~:~ & (\forall z : z<x \implies Q(z)) \implies Q(x) \\ \implies & \forall y ~:~ & Q(y) \end{array}\right)$$

Which is strong induction.

-