Results 1 to 4 of 4

Math Help - Proving Complete Induction

  1. #1
    MHF Contributor
    Joined
    Mar 2010
    From
    Florida
    Posts
    3,093
    Thanks
    5

    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) k\in\mathbb{Z}, \ k\geq m if P(i) is true \forall i\in\mathbb{N}, \ 1\leq i\leq k then P(k+1) is true.

    How do I prove this?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,546
    Thanks
    780
    I am somewhat busy right now, but this topic was discussed in this thread.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by dwsmith View Post
    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) k\in\mathbb{Z}, \ k\geq m if P(i) is true \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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    May 2011
    From
    Sacramento, CA
    Posts
    165
    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)?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Complete Induction proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 22nd 2009, 06:41 AM
  3. Complete Induction proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: October 22nd 2009, 06:41 AM
  4. Complete/Simple Induction
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: August 25th 2009, 11:57 PM
  5. proof by complete induction
    Posted in the Algebra Forum
    Replies: 2
    Last Post: September 25th 2007, 01:09 PM

Search Tags


/mathhelpforum @mathhelpforum