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.

Why we assume the condition holds up to certain number $n$ and we prove it holds for $n+1$. Is there any example where something holds up to $n$ but fails for $n+1$? I hope I'm making sense!!

share|improve this question
7  
Try to prove $n=1$ for all natural numbers $n$. The base case is true.. –  Cocopuffs Aug 25 '12 at 7:34
1  
Try: $n^2$ and $n$ have the same number of digits in base $10$. –  Did Aug 25 '12 at 8:53
add comment

2 Answers

up vote 3 down vote accepted

If I understand you correctly this is a confusion about how the variable n is quantified over. The induction step is "for all n (if P(n) then P(n+1))". The induction step is NOT "if (for all n (P(n)) ) then (for all n (P(n+1)))." You are right that the second statement is trivially true for any property P.

share|improve this answer
add comment

It is sort of like climbing an infinite ladder. Generally, you want to show you can get to any rung of the ladder from the first i.e $n=1$. You've shown that $n=1$ is possible. Now by showing that if from the $n$th rung, you can reach the $(n+1)$th rung for all natural numbers $n$, then you can reach any part of the ladder just by climbing from 1 to 2, 2 to 3, etc.. all the way to the rung you want. That is, formally, $S(1)$ implies $S(2)$, $S(2)$ implies $S(3)$ and so on.

By the nature of induction, if both parts of the proof are valid, then there is no natural $n$ where the statement $S(n)$ is true but $S(n+1)$ isn't, as you may climb from $n$ to $n+1$.

share|improve this answer
    
I'm looking for an example where $(n+1)$ is necessary. is there some example? where $n$ holds and $n+1$ fails? –  Monkey D. Luffy Aug 25 '12 at 7:46
    
I'm not sure what you're getting at. I think you're confusing the meaning of $n$ in the proof. It is not a specific number. It is a placeholder for any natural number. So the step where you prove $S(n)$ implies $S(n+1)$ is where you prove that '$S(1)$ implies $S(2)$' and '$S(2)$ implies $S(3)$' and so on. –  E.Lim Aug 25 '12 at 7:57
2  
I think $n^{2}+n + 41$ is prime for $n = 0,\ldots ,39$ but not for $n = 40.$ But the whole point of induction is that if a statement is true for $n = 1,$ but not fo all integers, there MUST come a point at which it is true for $n,$ but false for $n + 1.$ –  Geoff Robinson Aug 25 '12 at 8:01
    
@GeoffRobinson that's what I'm looking for .. .thanks!! –  Monkey D. Luffy Aug 25 '12 at 8:05
add comment

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.