Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
f(1) = 2
f(2) = 2^2
f(3) = 2^(2^2)
f(4) = 2^(2^(2^2))

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

share|cite|improve this question
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.'s_up-arrow_notation – Calle Feb 13 '11 at 2:41
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|cite|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

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|cite|improve this answer

Your Answer


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.