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$?
Why is the last step of proof by induction necessary?
-
1Try: $n^2$ and $n$ have the same number of digits in base $10$. – 2012-08-25
4 Answers
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$.
-
0@GeoffRobinson that's what I'm looking for .. .thanks!! – 2012-08-25
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).
-
0Actually 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. – 2014-08-03