Results 1 to 12 of 12

Math Help - induction to show that A (1,n)

  1. #1
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    induction to show that A (1,n)

    Can someone help me with this one: Use induction to show that A (1,n) = n+2, n =0, 1...How do I start here? Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: induction to show that A (1,n)

    My guess is that A(m, n) is the Ackermann function. Do you have the same definition as in Wikipedia? Just follow the regular procedure for proofs by induction: identify the property P(n) you are proving for all n, prove the base case P(0), state the induction hypothesis and the goal for the induction step, etc. For more on the generic procedure, see this post.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    Re: induction to show that A (1,n)

    Base case: A (1,0)=2 true. Inductive Step : Assume A(1,n)= n+2 is true, then A(1, n+1)= (n+1)+2 is true.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: induction to show that A (1,n)

    Yes, this is the outline. So, for the base case, A(1, 0) = A(0, 1) = 2 applying the second and then the first line of definition. For the step, A(1, n + 1) = A(0, A(1, n)) by the third line of definition. Can you continue by using the inductive hypothesis?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    Re: induction to show that A (1,n)

    me...not really
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: induction to show that A (1,n)

    By IH, A(1, n) = n + 2. So, you can simplify A(0, A(1, n)). After that, apply the first line of the definition.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    Re: induction to show that A (1,n)

    simplify A(0, A(1, n)) = A(0, n+2)? A(1,1) =3
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: induction to show that A (1,n)

    Quote Originally Posted by tinabaker View Post
    simplify A(0, A(1, n)) = A(0, n+2)?
    Yes.
    Quote Originally Posted by tinabaker View Post
    A(1,1) =3
    This is true but is not used in the inductive step.
    Quote Originally Posted by emakarov View Post
    After that, apply the first line of the definition.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Junior Member
    Joined
    Oct 2011
    Posts
    38
    Thanks
    1

    Re: induction to show that A (1,n)

    A(0, n+2)= A (1,n), really not sure howto apply the first line of the definition.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: induction to show that A (1,n)

    I assume the definition you have is the following.

    A(m, k) =\begin{cases}k+1 & \mbox{if } m = 0 \\A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } k = 0 \\A(m-1, A(m, k-1)) & \mbox{if } m > 0 \mbox{ and } k > 0.\end{cases}

    Note: compared to the Wiki link above, I systematically replaced n with k everywhere in the definition. This is OK because n is just a placeholder that relates the left- and right-hand sides; it show where a number that is the second argument of the left-hand side is used in the right-hand side.

    To compute A(0, n+2), you compare A(0, n+2) with the definition's left-hand side, i.e., A(m, k). These two expressions match if m = 0 and k= n + 2. Then you replace m with 0 and k with n + 2 everywhere in the right-hand side. You get

    \begin{cases}(n+2)+1 & \mbox{if } 0 = 0 \\A(0-1, 1) & \mbox{if } 0 > 0 \mbox{ and } n+2 = 0 \\A(0-1, A(0, (n+2)-1)) & \mbox{if } 0 > 0 \mbox{ and } n+2 > 0.\end{cases}

    Now you need to select of one of these three values based on which of the corresponding conditions is true.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Junior Member
    Joined
    Oct 2011
    Posts
    47

    Re: induction to show that A (1,n)

    I think the first one, because m=0, then A (0, (n+2)+1)
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,537
    Thanks
    778

    Re: induction to show that A (1,n)

    Quote Originally Posted by mathproblems View Post
    I think the first one, because m=0
    That's right.

    Quote Originally Posted by mathproblems View Post
    then A (0, (n+2)+1)
    But where did A (0, (n+2)+1) come from? Is it in the first line of the definition?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: December 13th 2010, 02:21 AM
  2. Show by mathematical induction:
    Posted in the Discrete Math Forum
    Replies: 18
    Last Post: September 15th 2010, 08:14 AM
  3. show by induction
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: November 18th 2009, 03:08 AM
  4. show integer by induction
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 16th 2008, 11:56 AM
  5. show monotone and bounded by induction
    Posted in the Calculus Forum
    Replies: 1
    Last Post: September 26th 2007, 08:36 AM

Search Tags


/mathhelpforum @mathhelpforum