2
$\begingroup$

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.

  • 0
    This [answer](http://mathoverflow.net/a/37978/8871) from Timothy Gowers may be illuminating.2013-12-16

3 Answers 3

9

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.

4

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

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

Since $\forall z : z is the same as $\forall z : z, this can be simplified to

$(\forall z : z

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

Which is strong induction.

3

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.

  • 0
    I simply said it because you wrote `I just didn't want to take unique factorization for granted, since that was what I was proving.`2012-04-30