31
$\begingroup$

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

$$f(x)=x+(x+(x+(x+(x+(x+\dots)^6)^5)^4)^3)^2$$

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

The function is defined as the limit of:

$$f_1(x)=x$$

$$f_2(x)=x+x^2$$

$$f_3(x)=x+(x+x^3)^2$$

etc.

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

$$(a_n)=$$

0,1,1,0,2,0,1,6,0,6,6,24,15,26,48,56,240,60,303,504,780,1002,1776,3246,3601,7826,7500,18980,26874,38130,56196,99360,153636,210084,390348,486420,900428,1310118,2064612,3073008,4825138,7558008,11428162,18596886,26006031,43625940,65162736,100027728,152897710,242895050,365185374

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).


Edit

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

$$c_n=\frac{a_{n+1}}{a_n}$$

enter image description here

And also the differences between the successive ratios:

$$d_n=c_n-c_{n+1}$$

enter image description here

We have:

$$c_{2413}=1.428347168$$

$$c_{2414}=1.428338038$$

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

  • After much effort, I computed

$$c_{4949}=1.4132183695$$

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$?


UPDATE

The sequence is now in OEIS, number A276436


$\endgroup$
  • 1
    $\begingroup$ I would love to see if the coefficients count something. $\endgroup$ – abnry Sep 1 '16 at 22:05
  • $\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 '16 at 22:27
  • 1
    $\begingroup$ Gorgeous question, +1. What prompted you to ask this question? $\endgroup$ – Brevan Ellefsen Sep 1 '16 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$ – Greg Martin Sep 1 '16 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$ – Cheerful Parsnip Sep 1 '16 at 22:47
4
$\begingroup$

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.

$\endgroup$
  • $\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 '16 at 13:09
  • $\begingroup$ @YuriyS: You're welcome. Formulas updated. I'm curious if somebody can add some substantial information. $\endgroup$ – Markus Scheuer Sep 2 '16 at 13:20
  • $\begingroup$ @ Markus Scheuer, you might be interested in my edit with some numerical estimations. $\endgroup$ – Yuriy S Sep 2 '16 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$ – Markus Scheuer Sep 2 '16 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 '16 at 19:01
6
$\begingroup$

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}]; 
   res 
 ];

(* 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 *)
ListLogLinearPlot[bn]
ListLogLinearPlot[cn]
$\endgroup$
  • $\begingroup$ Great work! I wonder if the ratio approaches a constant $\endgroup$ – Yuriy S Sep 2 '16 at 10:39
  • $\begingroup$ Wow, and I randomly computed it exactly for $1/\sqrt2$, it was probably wrong $\endgroup$ – Yuriy S Sep 2 '16 at 15:19
5
$\begingroup$

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

$\endgroup$
  • $\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 '16 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 '16 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 '16 at 20:07
1
$\begingroup$

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$.

$\endgroup$

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.