Results 1 to 6 of 6

Math Help - Recursion problem

  1. #1
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160

    Recursion problem

    I need some direction to the recursion problem listed below : recursion is a topic which i recently studied and i have not get a hang of it.

    Consider the following recursive recursive function A(m,n)

    A(0,n) = n+1 n greater or equal to 0
    A(m,0) = A(m-1,1) m > 0
    A(m,n) = A(m-1,A(m,n-1)), m>0,n>0

    Find A(2,n) for n greater or equal to 0

    I am not sure whether this is the right approach but here is what i did.

    A(2,n) = A(1,A(2,n-1))
    = A(0,A(1,A(2,A(2,n-2)))

    Then i got stuck
    Follow Math Help Forum on Facebook and Google+

  2. #2
    ddt
    ddt is offline
    Junior Member
    Joined
    Oct 2008
    Posts
    33
    Quote Originally Posted by tester85 View Post
    I need some direction to the recursion problem listed below : recursion is a topic which i recently studied and i have not get a hang of it.

    Consider the following recursive recursive function A(m,n)

    A(0,n) = n+1 n greater or equal to 0
    A(m,0) = A(m-1,1) m > 0
    A(m,n) = A(m-1,A(m,n-1)), m>0,n>0

    Find A(2,n) for n greater or equal to 0

    I am not sure whether this is the right approach but here is what i did.

    A(2,n) = A(1,A(2,n-1))
    = A(0,A(1,A(2,A(2,n-2)))

    Then i got stuck
    Two hints:

    1) this is the Ackermann function

    2) try first to get a non-recursive expression for A(1, n), then go on to solve A(2, n).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    Ok i will try now. I tired to solve for A(1,n)

    Here is what i got.

    A(1,n) = A(0,A(1,n-1))
    = A(0,A(0,A(1,n-2)))

    it seems like an endless loop is my approach wrong. I cannot go further even with the following link.

    http://en.wikipedia.org/wiki/Ackermann_function
    Last edited by tester85; October 19th 2008 at 04:43 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    ddt
    ddt is offline
    Junior Member
    Joined
    Oct 2008
    Posts
    33
    Quote Originally Posted by tester85 View Post
    Ok i will try now. I tired to solve for A(1,n)

    Here is what i got.

    A(1,n) = A(0,A(1,n-1))
    = A(0,A(0,A(1,n-2)))

    it seems like an endless loop is my approach wrong. I cannot go further even with the following link.
    First of all, A(0, A(1,n-1)) = A(1,n-1) + 1 from the definition of the function.

    Let's write x_n for A(1, n). Then you have a recurrence relation

    x_0 = 2
    x_{n+1} = x_n + 1

    You can calculate a number of the terms, see what formula you likely get for x_n, and prove it by induction.

    There are general theorems for solving such a recurrence relation, but they're too tedious to use for this exercise.
    Last edited by ddt; October 19th 2008 at 05:34 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    Ok noted with thanks. Now i know how to approach the problem.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Oct 2008
    From
    Singapore
    Posts
    160
    Mistake spotted. Problem solved.
    Last edited by tester85; October 22nd 2008 at 03:42 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: June 17th 2011, 11:58 AM
  2. recursion
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 13th 2009, 07:00 AM
  3. problem in recursion
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 3rd 2009, 09:51 AM
  4. Problem with understanding recursion
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2009, 05:24 AM
  5. Pattern/Recursion for paint can problem
    Posted in the Algebra Forum
    Replies: 1
    Last Post: September 8th 2008, 01:45 AM

Search Tags


/mathhelpforum @mathhelpforum