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.

  • 2
    Did you read [this previous question](http://math.stackexchange.com/a/102226/742), or [this one](http://math.stackexchange.com/a/14987/742), or [this](http://math.stackexchange.com/a/108377/742)?2012-04-30
  • 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
    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.2012-04-30
  • 0
    What would have changed if you used the word **prime** instead of irreducible?2012-04-30
  • 0
    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.2012-04-30
  • 0
    Sorry, I didn't realize you where considering an arbitrary ring.2012-04-30
  • 0
    @PeterTamaroff I wasn't. I just didn't want to take unique factorization for granted, since that was what I was proving.2012-04-30
  • 0
    Isn't the **unique** factorization theorem something rather hard to prove?2012-04-30
  • 0
    @PeterTamaroff Yes, it's nontrivial, which is why I didn't want to assume it here. In particular, the Euclidean algorithm (first step) implies that $\mathbb{Z}$ ring is Noetherian, which guarantees factorization into irreducibles.2012-04-30
  • 0
    Pardon my ignorance, but then your proof is of existance rather than of uniqueness right? (Also, I know basically nothing about rings, groups, ideals, etc, so it might be useless in your explanation here).2012-04-30
  • 0
    @PeterTamaroff Exactly.Existence, not uniqueness.2012-04-30
  • 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