Homework Help: Recursion: find explicit formula

1. Apr 3, 2010

DorumonSg

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. Apr 3, 2010

phyzguy

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.

3. Apr 3, 2010

DorumonSg

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
4. Apr 3, 2010

phyzguy

Re: Rercusion

If A(0,x) = x+1, then isn't A(0,1) = 2?

5. Apr 3, 2010

DorumonSg

Re: Rercusion

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

Where do I put the 2 den?

6. Apr 3, 2010

D H

Staff Emeritus
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).

7. Apr 3, 2010

phyzguy

Re: Rercusion

My bad. D H is right - you're original chain is incorrect.

8. Apr 3, 2010

D H

Staff Emeritus
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.

9. Apr 3, 2010

DorumonSg

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)

10. Apr 3, 2010

D H

Staff Emeritus
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?

11. Apr 3, 2010

DorumonSg

Re: Rercusion

What do u mean?

12. Apr 3, 2010

D H

Staff Emeritus
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.

13. Apr 3, 2010

D H

Staff Emeritus
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
14. Apr 3, 2010

rs1n

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.

15. Apr 3, 2010

D H

Staff Emeritus
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.

16. Apr 4, 2010

DorumonSg

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
17. Apr 4, 2010

D H

Staff Emeritus
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).

18. Apr 4, 2010

DorumonSg

Re: Rercusion

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

Is the one?

Last edited: Apr 4, 2010
19. Apr 4, 2010

D H

Staff Emeritus
Re: Rercusion

Stop with the textspeak.

20. Apr 4, 2010

DorumonSg

Re: Rercusion

Don't get what you meant by textspeak?

21. Apr 4, 2010

D H

Staff Emeritus
Re: Rercusion

You obviously got exactly what I meant because you edited your post to get rid of the textspeak. And yes, those are the correct relationships. Can you prove them, or did you just guess?

22. Apr 4, 2010

DorumonSg

Re: Rercusion

Too long to type out. But yeah, I proved them.

23. Apr 4, 2010

D H

Staff Emeritus
Re: Rercusion

Since you obtained the correct answer, the function A(m,n) discussed in this thread is the Ackermann function. Things get much nastier after m=2. For example, A(3,n) exhibits exponential growth:

\aligned A(3,0) &= 5 = 8-3 = 2^3-3\\ A(3,1) &= 13 = 16-3 = 2^4-3 \\ A(3,2) &= 29 = 32-3 = 2^5-3 \\ A(3,n)&=2^{n+3}-3\endaligned

A(4,n) is much, much worse. It exhibits hyperexponential growth.

\aligned A(4,0) &= A(3,1) = 13 = 2^{2^2} - 3 \\ A(4,1) &= A(3,A(4,0)) = 2^{2^{2^2}} - 3 \\ A(4,2) &= A(3,A(4,1)) = 2^{2^{2^{2^2}}} - 3 \\ A(4,n) &=\underbrace{2^{2^{\cdots^2}}}_{n+3} - 3 \endaligned