# why the last step of proof by induction is necessary?

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!!

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

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.

-
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$.
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
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