Proving Complete Induction

• Jun 9th 2011, 10:54 AM
dwsmith
Proving Complete Induction
I am not sure how to prove complete induction:
P(n) is a statement of variables n. If
(i) P(1), P(2),...,P(m) are true and
(ii)$\displaystyle k\in\mathbb{Z}, \ k\geq m$ if P(i) is true $\displaystyle \forall i\in\mathbb{N}, \ 1\leq i\leq k$ then P(k+1) is true.

How do I prove this?
• Jun 9th 2011, 04:04 PM
emakarov
I am somewhat busy right now, but this topic was discussed in this thread.
• Jun 10th 2011, 11:13 AM
CaptainBlack
Quote:

Originally Posted by dwsmith
I am not sure how to prove complete induction:
P(n) is a statement of variables n. If
(i) P(1), P(2),...,P(m) are true and
(ii)$\displaystyle k\in\mathbb{Z}, \ k\geq m$ if P(i) is true $\displaystyle \forall i\in\mathbb{N}, \ 1\leq i\leq k$ then P(k+1) is true.

How do I prove this?

That depends upon what you know. It is an axiom of Peano arithmetic

CB
• Jun 10th 2011, 01:13 PM
bryangoodrich
From what I've seen you prove it from having already established weak induction. That looks like the route taken in emakarov's link. Do you already have weak induction for this proof? If not, prove weak induction, and then prove strong induction. Does anyone know of a more direct proof (i.e., prove strong induction without weak induction)?