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$?
 A: 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.
A: 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$.
A: 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$
A: 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). 
