Find the recurrence formula!

Question

I have a sequence defined by recursion as follows:

$$\begin{cases}x_0=a\\ x_{n+1}=x_n\cdot B^{x_n} \end{cases}$$ where $a,B$ are fix natural numbers. Does anyone know how to find a recurrence formula for this?

I tried to write in a different way, and I figure out that another equivalent definition of the sequence could be

$$\begin{cases}x_0=a\\ x_{n+1}=a\cdot B^{x_0+\cdots+x_n}\end{cases}$$

Then I tried to use logarithms and differences, but really couldn't get to anything good.

Answer 1

You wanted to say : an explicit formula for $x_n$ I suppose ? If you calculate the firsts terms : $x_0 = a$ $x_1 = a B^a$ $x_2 = a B^a B^{aB^a}$ $x_3 = a B^a B^{aB^a} B^{a B^a B^{aB^a}}$

You can guess $x_n$ can be written in the form : $x_n = B_0 B_1 .. B_n$ [EDIT : what I have written just after this was false]

EDIT : You have : $x_n = B_0 B_1 .. B_n$ With $B_0 = a, B_n = B^{B_0 .. B_{n-1}}$

So you can understand the terms of $x_n$ using decreasing sequences of integers with first terms $\leq n$.

For instance : n = 2.

$x_2 = a B^a B^{aB^a}$

To (0) will be associated the first $a$ at the left.

To (1) is associated the tower $B^a$. To (1,0) is associated the $a$ in the tower $B^a$

To (2) is associated the tower $B^{aB^a}$. To $(2,0)$, the first $a$ at the left in the exponent of the tower $aB^a$. To $(2,1)$ the term $B^a$ in $aB^a$. To (2,1,0) the last exponent $a$.

In the general case, you have an algorithm to generate your expression of $x_n$ in function of $a$ and $B$.

• Put the $a$ on the first floor, associated to $(0)$, put the $n$ $B$ on the first floor, the base of the towers associated to the sequences of 1 term (1), (2), .. , (n).
• To fill the second floor, you look at the sequences $(k, l)$ with $0 \leq l < k$. To each of these sequence, you put a B on the $k$-th tower if $l\neq 0$, $a$ if $l=0$
• You continue like this, until the $n$-th floor ; then you have finished.

If you index $B$ by the sequences I said, you can also have a recursion formula.

$B_r = a$ if $r$ is a sequence ending by $0$, $B_r = B^{\prod B_s}$ where the product is on the $s$, the sequences which has $r$ as initial segment and one term more than r, and $x_n = B_{(0)} .. B_{(n)}$

It is quite technical, but it enables to understand how the towers of $B$ and $a$ are distributed, and can be helpful if you want to have some asymptotics.