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 do we assume the condition holds up to certain number $n$ and prove it holds for $n+1$? Is there any example where something holds up to $n$ but fails for $n+1$?

share|improve this question
11  
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

4 Answers 4

up vote 6 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

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

Well you assume something holds for some $n$,for example you assume $2^{2n}>n!$ This would hold for $n=8$ but would fail for $n+1=9$

share|improve this answer

Principle of mathematical induction is a 'theorem' which states that :if there exist a set S of positive integer with the following properties

1) 1 belongs to S

2) whenever k belongs to S , the next integer k+1 must also be in S

Then S is the set of all positive integers

( the proof of this theorem is based on 'Well Ordering' Principle of natural numbers)

In proof by induction we basically try to show that the set A of +ve integers satisfying our statement P(n) has all the properties of S (which would imply A is the set of all positive integers).

share|improve this answer
    
Actually I would argue that induction is just a property of the natural-number structure, similar to how the distributive property is a property of rings. The well ordering proof is just a proof that well ordered sets implement the natural-number structure in the same way that you would prove that matrices implement the ring structure. –  DanielV Aug 3 at 22:23

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.