Results 1 to 2 of 2

Thread: inductive proof question

  1. #1
    Newbie
    Joined
    Jul 2007
    Posts
    6

    inductive proof question

    hello,

    proving some predicate $\displaystyle A$ over the naturals $\displaystyle N$.

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

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

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

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

    but i already know that $\displaystyle 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
    5
    Quote Originally Posted by polypus View Post
    hello,

    proving some predicate $\displaystyle A$ over the naturals $\displaystyle N$.

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

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

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

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

    but i already know that $\displaystyle 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 $\displaystyle n = 1$

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

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

    $\displaystyle A(1) \wedge A(2)$,

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

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

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

    then prove that this implies:

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

    But the approach working with $\displaystyle 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: Dec 29th 2010, 07:38 AM
  2. Replies: 1
    Last Post: Sep 5th 2010, 10:15 AM
  3. help me with Inductive Proof #2
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Oct 17th 2009, 03:20 AM
  4. quick question about inductive proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: Oct 17th 2009, 02:30 AM
  5. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Apr 28th 2008, 06:24 PM

Search Tags


/mathhelpforum @mathhelpforum