# Can we solve a "very" exponential recurrence?

Can we solve this recurrence relation : $$T_n = \exp(T_{n-1})$$ ?

Thanks!

It depends what you mean by "solve". This is tetration, and it has a number of "closed" forms. For example:

$$\begin{eqnarray*}T_0 & = & 1 \\ T_{n+1} & = & 2^{T_n}\end{eqnarray*}$$

If $$n \ge 3$$, then:

$$\begin{eqnarray*}T_n & = & A(4, n-3) + 3\end{eqnarray*}$$

Where $$A()$$ is Ackermann's function.

Or using the Hyperoperation sequence:

$$\begin{eqnarray*}T_n & = & H_4(2,n)\end{eqnarray*}$$

Or in Knuth's arrow notation:

$$\begin{eqnarray*}T_n & = & 2 \uparrow \uparrow n\end{eqnarray*}$$

• In this context does exp(x) mean 2^x, not e^x? I'd assumed the latter (e^x) and was confused by the appearance of 2 in this answer. That said I'm not a computer scientist, I'm so I'm guessing it's a difference in convention specific to the field?
– bob
Jan 28 at 14:05
• @bob Tough to say. Unless told otherwise, I tend to assume in contexts like this that "exponential" means "$b^x$ for some $b$". Jan 30 at 5:12