2
$\begingroup$

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

Thanks!

$\endgroup$

1 Answer 1

13
$\begingroup$

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*}$$

$\endgroup$
2
  • 3
    $\begingroup$ 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? $\endgroup$
    – bob
    Jan 28 at 14:05
  • 1
    $\begingroup$ @bob Tough to say. Unless told otherwise, I tend to assume in contexts like this that "exponential" means "$b^x$ for some $b$". $\endgroup$
    – Pseudonym
    Jan 30 at 5:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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