Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
f(1) = 2
f(2) = 2^2
f(3) = 2^(2^2)
f(4) = 2^(2^(2^2))
etc

how can I find a closed form solution to this? Thanks.

share|improve this question
4  
What exactly do you mean by closed form? –  Mariano Suárez-Alvarez Feb 13 '11 at 2:40
    
You should check out Knuth's up-arrow notation. en.wikipedia.org/wiki/Knuth's_up-arrow_notation –  Calle Feb 13 '11 at 2:41
add comment

2 Answers

up vote 7 down vote accepted

Well the first thing that might be natural to do is define your function recursively, such as

$$f(0)=1$$ $$f(n)=2^{f(n-1)}$$.

You'll get stuck pretty quickly solving this though if you aren't familiar with tetration. Defining a closed form would be quite tricky, especially in terms of basic operations because tetration is actually a basic operation. If you consider the hierarchy of arithmetic functions (also known as hyperoperators you have

$$A_0(a,b)=b+1, \mbox{ this is just the successor function.} $$ $$A_1(a,b)=a+b, \mbox{ addition, right?}$$ $$A_2(a,b)=a\times b $$ $$A_3(a,b)=a^b, $$ $$A_4(a,b)=a\uparrow \uparrow b $$

and so forth. If you look at the wikipedia article there's actually an infinite hierarchy of functions that can be defined recursively. But back to your original question, well you could define it in several ways but they're all going to need to use tetration (or some very funky notation). So we might write:

$$f(n)=A_4(2,n)$$ $$f(n)=2\uparrow \uparrow n$$ $$f(n)=\underset{\mbox{$n$ times}}{\underbrace{2^{2^{\dots^{2^2}}}}}$$.

Hope this helps.

share|improve this answer
    
Thanks, the reason I ask this question - I am going through a textbook (Structure and Interpretation of Computer Programs) and a question was to give a concise mathematical definition of ackermann(2,n) (the Ackermann function), which appears to me to be in the form of my question. –  Chris Feb 13 '11 at 2:59
add comment

This operation is known as tetration. There is no closed form solution in terms of the usual arithmetic operations other than the one you wrote.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.