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

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

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

-

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

-
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 '14 at 22:23