Let's consider a function (or a way to obtain a formal power series):


Where $\dots$ is replaced by an infinite sequence of nested brackets raised to $n$th power.

The function is defined as the limit of:





For $|x|$ 'small enough' we have a finite limit $f(x)$, but I'm not really interested in it right now.

What I'm interested in - if we consider the function to be represented by a (formal) power series, then we can expand the terms $f_n$ and study the sequence of coefficients.

It appears to converge as well (i.e. the coefficients for first $N$ powers of $x$ stop changing after a while).

For example, we have the correct first $50$ coefficients for $f_{10}$:



I say they are correct, because they are the same up until $f_{15}$ at least (checked with Mathematica).

Is there any other way to define this integer sequence?

What can we say about the rate of growth of this sequence, the existence of small $a_n$ for large $n$, etc.? (see numerical estimations below)

Does it become monotone after $a_{18}=60$? (Actually, $a_{27}=7500$ is smaller than the previous term as well) (see numerical estimations below)

Are $a_0,a_3,a_5,a_8$ the only zero members of the sequence? (appears to be yes, see numerical estimations below)

The sequence is not in OEIS (which is not surprising to me).


Following Winther's lead I computed the ratios of successive terms for $f_{70}$ until $n=35 \cdot 69=2415$:


enter image description here

And also the differences between the successive ratios:


enter image description here

We have:



I conjecture that $c_{\infty}=\sqrt{2}$, but I'm not sure.

  • After much effort, I computed


Which seems to disprove my conjecture. The nearby values seem to agree with this.

$$c_{4948}=1.4132224343 \\ c_{4947}=1.4132265001$$

But the most striking thing - just how much the sequence stabilizes after the first $200-300$ terms.

How can we explain this behaviour? Why does the sequence start with more or less 'random' terms, but becomes monotone for large $n$?


The sequence is now in OEIS, number A276436

  • 1
    $\begingroup$ I would love to see if the coefficients count something. $\endgroup$
    – abnry
    Sep 1, 2016 at 22:05
  • 1
    $\begingroup$ just a curiosity: if I am not wrong, it seems that $x$ can be factored out, what is the reason for which you have included it ? $\endgroup$
    – G Cab
    Sep 1, 2016 at 22:27
  • 1
    $\begingroup$ Gorgeous question, +1. What prompted you to ask this question? $\endgroup$ Sep 1, 2016 at 22:28
  • $\begingroup$ It's quite easy to show that this polynomial stabilizes term-by-term into a limiting (formal) power series; more precisely, the coefficient of $x^m$ in $f_n(x)$ doesn't depend on $n$ as long as $n\ge m$. $\endgroup$ Sep 1, 2016 at 22:46
  • 1
    $\begingroup$ The fact that the formal power series converges comes from the fact that $f_n$ is gotten from $f_{n-1}$ by replacing one instance of $x$ with $x+x^n$. So at the very least you know that $f_n$ agrees with $f_{n-1}$ up to degree $n-1$. In fact, it agrees up to higher order as well. $\endgroup$ Sep 1, 2016 at 22:47

4 Answers 4


Just adding some results from a numerical computation of the first $n = 4000$ $a_n$'s in case anyone is interested to see how the sequence grows. The Mathematica code used (probably not very efficient) is given at the end. I compute $f_n(x)$ by solving the reccurence: $g_{i+1} = (x + g_i)^{n-i}$ with $g_1 = x^n$. This way we have $f_n(x) = g_n$.

Here you can see $\frac{\log(a_n)}{n}$,

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$enter image description here

and here you can see the ratio $\frac{a_{n+1}}{a_n}$

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$enter image description here

and here is a plot of $f(x)$ (well $f_{15}(x)$ however the plot below looks the same for larger $n$). The vertical line denotes $x = \frac{1}{\sqrt{2}}$ which seems to be a vertical asymptote for $f(x)$.

$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~$enter image description here

(* Define the function f_n(x) *)
f[n_, x_] := Module[{res, i},
   res = x^n; 
   Do[ res = (x + res)^(n - i); , {i, 1, n - 1}]; 

(* How many an's to compute? *)
numterms = 1000;

(* am stabilize for m > n(n-1)/2 so we only need to compute fn for n = nmax *)
nmax = Ceiling[Sqrt[2 numterms]];

(* Extract the coefficients *)
powerseries = Normal[Series[f[nmax, x], {x, 0, numterms}]];
an = Coefficient[powerseries, x, #] & /@ Range[0, numterms];
bn = Table[{i, Log[an[[i]]]/i}, {i, 1, Length[an]}];
cn = Table[{i, an[[i + 1]]/an[[i]]}, {i, 1, Length[an] - 1}];

(* Plot it up *)
  • $\begingroup$ Great work! I wonder if the ratio approaches a constant $\endgroup$
    – Yuriy S
    Sep 2, 2016 at 10:39
  • $\begingroup$ Wow, and I randomly computed it exactly for $1/\sqrt2$, it was probably wrong $\endgroup$
    – Yuriy S
    Sep 2, 2016 at 15:19

An interpretation of what $f$ is counting: In terms of diagrams consider a branching process where at each level $n-1$ you either put a leaf (the factor $x$) or you branch into $n$ distinct branches at level $n$. The generating functions at each level then verifies the recursion relation (I put the recursion differently than the OP):

$$L_{n-1}(x) = x + (L_{n}(x))^n $$

Each $L_n(x)=x + ...$

The function $L_1(x)=f(x)$ then counts the number of trees. Using parantheses for indicating the branching level we have:

$L_1(x)=f(x)=(x) \ + \ ((x)(x)) \ + \ 2 ((x) \ \ ((x)\;(x)\;(x)) )+ ...$

Here is a drawing of orders up to $x^7$. Each filled circle corresponds to a leaf (a factor of $x$). Regarding counting factors, e.g. 6 comes from 2 choices for where to put the 3-branching and then 3 choices for putting the 4-branching. First 5 terms

  • $\begingroup$ Thank you for the interpretation. Looks complicated though, I don't know how to get any more insight in the properties of the sequence $\endgroup$
    – Yuriy S
    Sep 3, 2016 at 19:58
  • $\begingroup$ @YuriyS Yes, usually it's the other way round. Given a branching process one estimate growth rates using generating functions (at least what I usually encounter). Btw radius of convergence being 1 it looks as if $a_{n+1}/a_n$ should go to 1 (supposing ithas a limit). $\endgroup$
    – H. H. Rugh
    Sep 3, 2016 at 20:06
  • $\begingroup$ @ H.H.Rugh, now I know it's not $1$. It's around $1/\sqrt{2}$ according to the function approximation plot $\endgroup$
    – Yuriy S
    Sep 3, 2016 at 20:07

Two aspects which might be helpful.

Recurrence relation:

We use the following recurrence relation to represent $f(x)$:

\begin{align*} f_1(x,y)&=y\\ f_2(x,y)&=x+y^2\\ f_3(x,y)&=x+(x+y^3)^2\\ f_4(x,y)&=x+(x+(x+y^4)^3)^2\\ f_5(x,y)&=x+(x+(x+(x+y^5)^4)^3)^2\\ &\cdots \end{align*}

We obtain \begin{align*} f_1(x,y)&=y\\ f_n(x,y)&=f_{n-1}(x,x+y^n)\qquad\qquad n> 1 \end{align*} and conclude \begin{align*} f(x)=\lim_{n\rightarrow\infty}f_n(x,y) \end{align*}

Note $y$ is not part of the power series $f(x)$, since the term with lowest power of $y$ in $f_n$ is $n$ and so $y$ vanishes when taking the limit.

Coefficients of $f(x)$:

If we take a look at the change from $f_4$ to $f_5$

$$f_4(x,y)=x+(x+(x+y^4)^3)^2 \qquad\rightarrow\qquad f_5(x,y)=x+(x+(x+(x+y^5)^4)^3)^2$$ we see the coefficients which might change from $f_4(x,x)$ to $f_5(x,x)$ start with the coefficients of the smallest power introduced by the substitution $$y^4\qquad\rightarrow\qquad (x+y^5)^4$$ which is $x^{4+3+2+1}$.

In the table below we see marked with blue color the coefficients which are stable with increasing $n$. We see blocks of $1,1+2$ up to $1+2+3+4+5$ coefficients in $f_2(x,x)$ to $f_6(x,x)$. \begin{array}{c|cccccccccccccccccccccc} f_n(x,x)&x^1&x^2&x^3&x^4&x^5&x^6&x^7&x^8&x^9&x^{10}&x^{11}&x^{12}&x^{13}&x^{14}&x^{15}\\ \hline f_1(x,x)&1\\ f_2(x,x)&\color{blue}{1}&1\\ f_3(x,x)&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}&2&&1\\ f_4(x,x)&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}&\color{blue}{2}&\color{blue}{0}&\color{blue}{1}&6&&6&6&&15&2&&20&\cdots\\ f_5(x,x)&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}&\color{blue}{2}&\color{blue}{0}&\color{blue}{1}&\color{blue}{6}&\color{blue}{0}&\color{blue}{6}&\color{blue}{6}&24&15&26&48&56&\cdots\\ f_6(x,x)&\color{blue}{1}&\color{blue}{1}&\color{blue}{0}&\color{blue}{2}&\color{blue}{0}&\color{blue}{1}&\color{blue}{6}&\color{blue}{0}&\color{blue}{6}&\color{blue}{6}&\color{blue}{24}&\color{blue}{15}&\color{blue}{26}&\color{blue}{48}&\color{blue}{56}&\cdots\\ \end{array}

We note the coefficients of $f_n(x,x)$ and $f_{n-1}(x,x)$ up to $x^{(n-1)+(n-2)+\cdots +1}=x^\frac{n(n-1)}{2}$ are the same and conclude:

The coefficients of the terms up to $x^\frac{n(n-1)}{2}$ in $f(x)$ are given by the corresponding coefficients of $f_n(x,x)$ for $n> 1$.

\begin{align*} [x^j]f(x)=[x^j]f_n(x,x)\qquad\qquad 0\leq j\leq \frac{n(n-1)}{2} \end{align*}

with $[x^j]$ denoting the coefficient of $x^j$ in a series.

  • $\begingroup$ Maybe $\frac{n(n-1)}{2}$ is the more convenient way to represent the number of correct coefficients. It's just the triangular numbers. Thank you for this observation $\endgroup$
    – Yuriy S
    Sep 2, 2016 at 13:09
  • $\begingroup$ @YuriyS: You're welcome. Formulas updated. I'm curious if somebody can add some substantial information. $\endgroup$
    – epi163sqrt
    Sep 2, 2016 at 13:20
  • $\begingroup$ @ Markus Scheuer, you might be interested in my edit with some numerical estimations. $\endgroup$
    – Yuriy S
    Sep 2, 2016 at 17:56
  • $\begingroup$ @YuriyS: Very nice! Especially the asymptotic behaviour. I'm pretty sure, we have to find a symbolic equation for $f$ as it is shown in Flajolet's and Sedgewick's Analytic Combinatorics and the asymptotic estimation can also be done with one of the techniques described there. Regrettably, I wasn't able at the time to derive a proper symbolic equation. An additional aspect is the related function $g_n(x,y)=g _{n-1}(x,1-y^{n})$ has a much nicer representation and a proper transformation could do the job. $\endgroup$
    – epi163sqrt
    Sep 2, 2016 at 18:23
  • $\begingroup$ Maybe as G Cab suggested it's better to work with h(x)=f(x)/x: $$h_0=1 \\ h_1=1+x \\ h_2=1+x(1+x^2)^2 \\ h_3=1+x(1+x^2(1+x^3)^3)^2$$ $\endgroup$
    – Yuriy S
    Sep 2, 2016 at 19:01

A remark that might be helpful:

Using the notation $$F_k(x) = (x+(x+(x+\ldots)^{k+2})^{k+1})^k,$$ so that in particular $F_1(x) = f(x)$, we have $$\frac{d}{dx}F_k(x) = k(x+F_{k+1}(x))^{k-1}\left(1+\frac{d}{dx}F_{k+1}(x)\right).$$ Now to find $a_n$ we need to take $F_1(x)$, differentiate it $n$ times and then evaluate at $x=0$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .