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

1. ## 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?

Hello Grillakis

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

Hello Grillakis

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

Ackermann's function

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

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

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

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

$\displaystyle 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.

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