Problem with the principle of induction

[mathsciguy]

The principle of induction states that:
Suppose\ that\ P(n)\ is\ a\ statement\ involving\ a\ general\ positive\ integer\ n.\ Then\ P(n)\ is\ true\ for\ all\ positive\ integers\ 1,2,3,...\ if\
(i)\ P(1)\ is\ true,\ and
(ii)\ P(k) \rightarrow P(k+1)\ for\ all\ positive\ integers\ k.
I found it a bit circular to prove that the statement P(n) holds true for all n that is an element of natural numbers by presupposing P(k) is true for all k that is an element natural numbers.

That is what I thought at first, but I'm thinking that that's false, since what the principle of induction states in (ii) is that the implication itself is what needs to be true.

I'm still not too comfortable with the principle of induction, could anyone take a look on my thoughts?

 

[hddd123456789]

I just have programmer's logic under my belt, but it doesn't seem circular to me, (i) and (ii) are conditions on which the principle is true. If the predicate P(1) is true from (i), and if we know that P(1+1) is true when P(1) is true from (ii), and that P(1+1+1) is true when P(1+1) is true..., then we know that P(k+1) is true when P(k) is true. So we can induce that P(n) is true for all positive integers?

 

[justsomeguy]

hddd Got it right. It sounds like what you're looking for is a proof that induction itself works, for which there is a formal proof as well. Wikipedia has a pretty concise example here: http://en.wikipedia.org/wiki/Mathematical_induction#Proof_of_mathematical_induction

 

[mathsciguy]

I just have programmer's logic under my belt, but it doesn't seem circular to me, (i) and (ii) are conditions on which the principle is true. If the predicate P(1) is true from (i), and if we know that P(1+1) is true when P(1) is true from (ii), and that P(1+1+1) is true when P(1+1) is true..., then we know that P(k+1) is true when P(k) is true. So we can induce that P(n) is true for all positive integers?

Well, I get that. Just so I'm making myself clear, I actually thought about the circularity for some time and I tried to resolve it by adhering strictly on what the principle says, and that (i) and (ii) should be true; (ii) which states that the implication itself must be true and not just presupposing P(k) is true. I just want someone to give their insight on that.

hddd Got it right. It sounds like what you're looking for is a proof that induction itself works, for which there is a formal proof as well. Wikipedia has a pretty concise example here: http://en.wikipedia.org/wiki/Mathema...ical_induction

Is that the proof using the Well Ordering Principle? I'm actually familiar with that.

 

[justsomeguy]

Yes, it's the well ordered principle. I reread your question and you/re right, you must assume that (ii) is true. If you cannot make that assumption (or prove it), then you cannot prove that P(n) is true for all natural n via induction, and you must use some other proof.

 

[Vargo]

Yes, the implication is what must be true. That P(k) implies P(k+1).

In order to prove the implication, you typically assume P(k), then deduce P(k+1) from that assumption. So a correct inductive proof can look circular, but it is not. Sometimes it helps to examine an incorrect inductive proof to see how they work. Consider
http://www.greylabyrinth.com/discussion/viewtopic.php?t=4371&sid=d2055447e6ff685ca3f562a112c3ed4c

And here are a couple with simpler errors.
http://www.purplemath.com/modules/inductn2.htm