Recursion: find explicit formula

[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?

 

[phyzguy]

I think you're right as far as you've gone, but you can go further and reduce the answer to a single number.

 

[DorumonSg]

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?

 

[phyzguy]

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

 

[DorumonSg]

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

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

Where do I put the 2 den?

 

[D H]

Therefore :

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

Am I right?

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

 

[phyzguy]

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

 

[D H]

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.

 

[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

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)

 

[D H]

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?

 

[DorumonSg]

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?

What do u mean?

 

[D H]

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.

 

[D H]

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.

 

[rs1n]

A(0, x) = x + 1 For : x >=0
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)

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.

 

[D H]

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.

Exactly.

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.

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 let's 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.

 

[DorumonSg]

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?

 

[D H]

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

 

[DorumonSg]

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

Is the one?

 

[D H]

Stop with the textspeak.

 

[DorumonSg]

Don't get what you meant by textspeak?

 

[D H]

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?

 

[DorumonSg]

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

 

[D H]

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$$