1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Recursion: find explicit formula

  1. Apr 3, 2010 #1
    A(0, x) = x + 1 For : x >=0
    A(y, 0) = A(y-1, 1) For : y > 0
    A(y, x) = A(y-1, A(y, x-1)) For : y > 0, x > 0

    Find A(2,x) for x >= 0

    I worked this out... but I am wondering if I am right.

    Let x be 1 and y be 2.

    From statement 3 :

    A(y, x) = A(y-1, A(y, x-1)) = A(1, A(2, 0))

    From statement 2 & 3 :

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

    Therefore :

    A(2,x) = A(1, A(1,1))

    Am I right?
     
  2. jcsd
  3. Apr 3, 2010 #2

    phyzguy

    User Avatar
    Science Advisor

    Re: Rercusion

    I think you're right as far as you've gone, but you can go further and reduce the answer to a single number.
     
  4. Apr 3, 2010 #3
    Re: Rercusion

    How?

    A(0, x) = x + 1 For : x >=0
    A(y, 0) = A(y-1, 1) For : y > 0
    A(y, x) = A(y-1, A(y, x-1)) For : y > 0, x > 0

    Find A(2,x) for x >= 0

    I worked this out... but I am wondering if I am right.

    Let x be 1 and y be 2.

    From statement 3 :

    A(y, x) = A(y-1, A(y, x-1)) = A(1, A(2, 0))

    From statement 2 & 3 :

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

    Therefore :

    A(2,x) = A(1, A(1,1))

    Lets see...

    If I continue...

    Let x be 0 for statement 1.

    A(0, x) = x + 1
    a(0, 0) = 1

    So back to before...

    I sub in 1 as A(0, x).

    A(2,x) = A(1, A(A(0,0), A(0,0))

    Erm... nope no idea... help?
     
    Last edited: Apr 3, 2010
  5. Apr 3, 2010 #4

    phyzguy

    User Avatar
    Science Advisor

    Re: Rercusion

    If A(0,x) = x+1, then isn't A(0,1) = 2?
     
  6. Apr 3, 2010 #5
    Re: Rercusion

    Oops my bad... but still no idea how to continue.

    Where do I put the 2 den?
     
  7. Apr 3, 2010 #6

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Rercusion

    No, for two reasons. First, your goal is to come up with a general expression for A(2,x), not A(2,1). Second, you have not reduced the A(2,1) to a number.

    You already have a general expression for A(0,x). It is rule #1 for this function.
    Hint: Before jumping directly to the problem of A(2,x) find a general expression for A(1,x).
     
  8. Apr 3, 2010 #7

    phyzguy

    User Avatar
    Science Advisor

    Re: Rercusion

    My bad. D H is right - you're original chain is incorrect.
     
  9. Apr 3, 2010 #8

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Rercusion

    To all who are helping with this thread: Keep in mind that this is a homework problem. If you know the name of this function, please do not mention it. Many resources on the net explicitly develop the answer to this problem, and these are easy to find if you know the name of the function.
     
  10. Apr 3, 2010 #9
    Re: Rercusion

    A(0, x) = x + 1 For : x >=0
    A(y, 0) = A(y-1, 1) For : y > 0
    A(y, x) = A(y-1, A(y, x-1)) For : y > 0, x > 0

    Find A(2,x) for x >= 0

    Let x be 1 and y be 2.

    From statement 3 :

    A(y, x) = A(y-1, A(y, x-1)) = A(1, A(2, 0))

    From statement 2 & 3 :

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

    Therefore :

    A(2,x) = A(1, A(1,1))

    Let x be 0 for statement 1.

    A(0, x) = x + 1
    a(0, 0) = 1

    So back to before...

    I sub in 1 as A(0, x).

    A(2,x) = A(1, A(A(0,0), A(0,0))

    _____________________________________________________________________________

    k...

    From statement 3 :

    So A(1,x) = A(1-1, A(1, x-1)) = A(0, A(1, x - 1))

    Let x be 1 and y be 1

    A(1,1) = A(0, A(1,0))

    From statement 2 :

    A(1, 0) = A(0, 1)

    Therefore A(y, 0) = A(0, y)

    Thefore A(2, x) = A(x, 2)
     
  11. Apr 3, 2010 #10

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Rercusion

    Try again. A(4,2), for example is a huge, huge number. A(2,4) is a nice small number.

    Have you tried the hint in post #6?
     
  12. Apr 3, 2010 #11
    Re: Rercusion

    What do u mean?
     
  13. Apr 3, 2010 #12

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Rercusion

    First off, please stop using textspeak. It is not appreciated here at all.

    What I mean is that A(2,x) is not equal to A(x,2). For example, consider A(2,4) versus A(4,2). A(2,4) is a small number. A(4,2) is a huge number; so huge that your calculator would probably print it as infinity.
     
  14. Apr 3, 2010 #13

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Rercusion

    It looks like you are really lost on this problem. So, step-by-step, here is how to evaluate A(1,1).
    1. The first step in evaluating any A(m,n) is to determine the reduction rule that needs to be applied. In the case of A(1,1), neither of the first two rules apply, so we must use rule #3, A(y, x) = A(y-1, A(y, x-1)). With this rule, A(1,1) = A(0,A(1,0)). So right off the bat we will need to evaluate the function at least two more times,
      • Once to evaluate A(1,0), and
      • Another time to evaluate A(0,A(1,0)), but plugging the solution for step 1a into that expression.
    2. The next step is to evaluate A(1,0). The second rule tells how to reduce this: A(1,0)=A(0,1).
    3. Now we need to evaluate A(0,1). The first rule tells how to evaluate this one: A(0,1)=1+1=2.
    4. Now we have the answer to step number 3: A(1,0)=A(0,1)=2, and this in turn is the answer to step 1a. Time to move on to step 1b. We need to evaluate A(0,A(1,0)), but now we know A(1,0)=2. Plugging that in, we need to evaluate A(0,2). That one is once again easy. The first rule applies; A(0,2)=2+1=3.
    5. This result is the final answer: A(1,1)=3.
     
    Last edited: Apr 3, 2010
  15. Apr 3, 2010 #14
    Re: Rercusion

    It is very important that you understand that one generally cannot extrapolate a property about a single instance to the general case. For example, you noticed that A(1,0) = A(0,1) and concluded that this implies A(y,0) = A(0,y). However we only know (up to this point) that A(y,0) = A(0,y) is true ONLY FOR y=1, not for ANY y.

    Work out a few examples with various values of x and y. Do it for more than just one pair of x,y. First try examples (at least two) where x<y. Then try it for examples where x=y, and finally for x>y. Once you have seen a few examples, you will have a much better picture.

    DH has helped already you tremendously on how to look at the case when x=1 and y=1.
     
  16. Apr 3, 2010 #15

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Rercusion

    Exactly.

    That's good advice in general, but not with this nasty function. Stick to small (very small!) values of y.

    Lets look at A(2,1). You will quickly see that you need to evaluate A(1,1). Later on, you will run into A(1,1) again. It would be kind of silly to grind through the calculations given in post #13 twice. A(1,1) is not going to change. If you keep track of prior results, calculating A(2,1) will require evaluating this function 11 times. If you don't keep track, you will have need to make four more evaluations.

    Now lets look at A(3,1) and then at A(4,1). Even if you do keep track of prior results, calculating A(3,1) will require evaluating A(y,x) for 38 distinct y,x pairs. If you don't keep track of prior results, you will evaluate A(y,x) 106 times. Things start getting interesting with y=4. Calculating A(4,1) requires evaluating A(y,x) for 196625 distinct y,x pairs. If you don't keep track of prior results, calculating A(4,1) will require 2862984010 evaluations of A(y,x). Calculating A(4,1) is not something you can do by hand -- unless of course you develop a nice simple rule for A(3,x) or A(4,x), that is.
     
  17. Apr 4, 2010 #16
    Re: Rercusion

    I worked it out,

    A(2,1) = 5

    So A(2,x) = n + 4

    I tried it on 2 other numbers n = 0 and n = 3 and it works.

    Am I right?

    Is there any other way to prove that the solution is correct?
     
    Last edited: Apr 4, 2010
  18. Apr 4, 2010 #17

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Rercusion

    A(2,1) is 5, but you have the wrong general relationship. Try the hint in post #6. I'll repeat it: Work out a general relationship for A(1,x) first. You will need that to derive the general relationship for A(2,x).
     
  19. Apr 4, 2010 #18
    Re: Rercusion

    A(1,x) = x + 2
    A(2,x) = 2x + 3

    Is the one?
     
    Last edited: Apr 4, 2010
  20. Apr 4, 2010 #19

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Re: Rercusion

    Stop with the textspeak.
     
  21. Apr 4, 2010 #20
    Re: Rercusion

    Don't get what you meant by textspeak?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Recursion: find explicit formula
  1. Recursive formulae (Replies: 14)

Loading...