Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
add comment

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
show 5 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.