1
$\begingroup$
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.

  • 0
    You should check out Knuth's up-arrow notation. http://en.wikipedia.org/wiki/Knuth's_up-arrow_notation2011-02-13

2 Answers 2

7

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.

  • 0
    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.2011-02-13
5

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.