# Problem with the principle of induction

1. Dec 12, 2012

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

Last edited: Dec 12, 2012
2. Dec 12, 2012

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

3. Dec 12, 2012

### justsomeguy

4. Dec 12, 2012

### mathsciguy

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.

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

Last edited by a moderator: May 6, 2017
5. Dec 12, 2012

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

6. Dec 12, 2012

### 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