Results 1 to 2 of 2

Math Help - inductive proof question

  1. #1
    Newbie
    Joined
    Jul 2007
    Posts
    6

    inductive proof question

    hello,

    proving some predicate A over the naturals N.

    if the following statement holds for my base case, say n = 1

    A(n) \wedge A(n + 1)

    and i then assume it to hold for all n \epsilon N,
    then i can also assume that A(n) holds for all n.
    i can hence take my inductive hypothesis as

    A(n) \rightarrow  A(n + 1)

    but i already know that A(n + 1) holds for all n.

    this has got to be cheating right?

    thanks for any pointers
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by polypus View Post
    hello,

    proving some predicate A over the naturals N.

    if the following statement holds for my base case, say n = 1

    A(n) \wedge A(n + 1)

    and i then assume it to hold for all n \epsilon N,
    then i can also assume that A(n) holds for all n.
    i can hence take my inductive hypothesis as

    A(n) \rightarrow A(n + 1)

    but i already know that A(n + 1) holds for all n.

    this has got to be cheating right?

    thanks for any pointers
    Yes,
    The error lies here:

    Not only is it cheating you are assuming the result.


    if the following statement holds for my base case, say n = 1

    A(n) \wedge A(n + 1)

    and i then assume it to hold for all n \epsilon N,
    Your base case is:

    A(1) \wedge A(2),

    which tells you nothing about any A(n),\ n>2.

    You have to assume that for some k \in N that:

    A(k) \wedge A(k + 1)

    then prove that this implies:

    A(k+1) \wedge A(k+2).

    But the approach working with A(n) looks more natural to me

    RonL
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: December 29th 2010, 07:38 AM
  2. Replies: 1
    Last Post: September 5th 2010, 10:15 AM
  3. help me with Inductive Proof #2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 17th 2009, 03:20 AM
  4. quick question about inductive proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 17th 2009, 02:30 AM
  5. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 28th 2008, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum