# Help Please?? Show that A(1, n) = 2^(n) whenever n >= 1?

• Mar 24th 2009, 05:06 AM
Grillakis
Help Please?? Show that A(1, n) = 2^(n) whenever n >= 1?
I am stuck on this same problem as the other guys topic. But I think we do use induction.I have this so far:

Base Case:
A(1, n) = n + 2
n + 2 = 2^(n) Let n = 2
2 + 2 = 2^(2)
4 = 4 Base case holds

Induction Hypothesis:
We going to assume P(k) is true for all integers of k > 1

Induction Step (Confused Here):
We must prove for P(k+1)

What do I do next b/c I cant solve this?
• Mar 24th 2009, 06:18 AM
Hello Grillakis

Please tell us what you mean by A(1, n).

• Mar 24th 2009, 06:23 AM
Quote:

Hello Grillakis

Please tell us what you mean by A(1, n).

Ackermann's function
• Mar 24th 2009, 06:26 AM
Grillakis
Quote:

Hello Grillakis

Please tell us what you mean by A(1, n).

well A(1, n) is Ackermann function. So I am assuming it wants us to prove that A(1, n) = 2^(n)

Heres a link to Ackermanns Function:
Ackermann Function -- from Wolfram MathWorld

(Edit: Sorry! you already gave the link. I think its asking me to prove using Induction, which I tried in the 1st post. Doesn't help in the book but it shows 1 using Induction.)
• Mar 24th 2009, 06:30 AM
Quote:

Originally Posted by Grillakis
I am stuck on this same problem as the other guys topic. But I think we do use induction.I have this so far:

Base Case:
A(1, n) = n + 2
n + 2 = 2^(n) Let n = 2
2 + 2 = 2^(2)
4 = 4 Base case holds

Induction Hypothesis:
We going to assume P(k) is true for all integers of k > 1

Induction Step (Confused Here):
We must prove for P(k+1)

What do I do next b/c I cant solve this?

----------------------------------
You know that A(1,n) = n + 2

You are trying to prove
A(1,n) = 2^{n}

--------------------------
If you agree with this than I dont agree with you

because

$n+2 \ne 2^{n}$ for n>= 1 , example put n = 3
• Mar 24th 2009, 06:39 AM
Grillakis
Quote:

----------------------------------
You know that A(1,n) = n + 2

You are trying to prove
A(1,n) = 2^{n}

--------------------------
If you agree with this than I dont agree with you

because

$n+2 \ne 2^{n}$ for n>= 1 , example put n = 3

That's what its asking me from the book word for word is show that it =. I can pop a link to show you, and it shows 1 example using Induction, but the example they show I don't understand.

Heres a link (it's at the bottom of the page: #50 on page 10/10):
http://isis.poly.edu/courses/discretemath/problems4.pdf

(This is what we confused on.)

I agree with you its not correct b/c when I tried 1 since n >= 1 I would have LHS:1 + 2 = 3 = 2^(1) = 2RHS which is not equal, but it does work when n = 2, but like you also mention doesn't work with 3.
• Mar 24th 2009, 06:49 AM
Quote:

Originally Posted by Grillakis
That's what its asking me from the book word for word is show that it =. I can pop a link to show you, and it shows 1 example using Induction, but the example they show I don't understand.

Heres a link (it's at the bottom of the page: #50 on page 10/10):
http://isis.poly.edu/courses/discretemath/problems4.pdf

(This is what we confused on.)

I agree with you its not correct b/c when I tried 1 since n >= 1 I would have LHS:1 + 2 = 3 = 2^(1) = 2RHS which is not equal, but it does work when n = 2, but like you also mention doesn't work with 3.

It is a misprint "most probably" ,As far as I can induce you should try proving that
A(1,n) = 2 + n
• Mar 24th 2009, 07:07 AM
Grillakis
Quote: