1
$\begingroup$

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

  • 1
    Try: $n^2$ and $n$ have the same number of digits in base $10$.2012-08-25

4 Answers 4

6

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.

1

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
0

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$

0

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

  • 0
    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.2014-08-03