14
$\begingroup$

Sequence A003238 of the OEIS counts ``rooted trees with $n$ vertices in which vertices at the same level have the same degree.'' The sequence, $a$, begins

1, 1, 2, 3, 5, 6, 10, 11, 16, ...

and it is of course easy to generate as many terms as you like via recurrences (basically $a(n)$ is the sum of $a(d)$ as $d$ runs over divisors of $n-1$). In the formula section of the OEIS page we find:

Conjecture : $\log(a(n))$ is asymptotic to $c \log(n)^2$ where $0.4 < c < 0.5$ (Benoit Cloitre, Apr 13 2004)

What I'm interested in is both the state of this conjecture, and more generally, methods for analysing the asymptotics of sequences defined by ``similar'' recurrences - either globally (as above) or in the average sense i.e. asymptotics of things like $(1/n)\sum_{i=1}^n a(n)$.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ well ... that's quite a puzzler! I will say that I computed $(\log a(n))/\log^2 n$ for $n$ out to $10^5$; after the first few integers it's an essentially increasing quantity (other than a minor parity difference) which does pass 0.5 between 57800 and 57900. In fact, the data seems to suggest that the power of $\log n$ should be between 2.1 and 2.2, rather than 2. $\endgroup$
    – Greg Martin
    Commented Mar 11, 2014 at 5:43

1 Answer 1

Reset to default
22
$\begingroup$

I'll show that $$ \log a(n) \sim \frac{(\log n)^2}{\log 4} \approx 0.7213\ldots (\log n)^2. $$ So the range for the constant given in the conjecture is false, but an asymptotic of that general shape holds. One can obtain more precise asymptotics by working harder with the argument below.
Roughly speaking what the argument says is that $a(n)$ behaves (in rough order) like the sequence $b(n)$ defined by $b(n+1)=b(n)$ if $n$ is odd, and $b(n+1)=b(n)+b(n/2)$ if $n$ is even.

Put $A(x) = \sum_{j\le x} a(j)$. Then $$ A(n+1) = \sum_{j\le n+1} \sum_{d|(j-1)} a(d) =\sum_{j\le n+1} \sum_{d|(j-1)} a((j-1)/d) = \sum_{d} \sum_{j\le n, d|j} a(j/d) = \sum_d A(n/d). $$ Rearranging we get $$ a(n+1) = A(n+1)-A(n) = \sum_{2\le d\le n} A(n/d). $$

By the monotonicity of $a(n)$, it follows that $$ a(n+1) \le \sum_{2\le d\le n} \frac{n}{d} a(\lfloor n/2\rfloor) \le ( n\log n) a(\lfloor n/2\rfloor). $$ Iterating this inequality leads to the estimate $$ \log a(n) \le (1+o(1)) \frac{(\log n)^2}{2\log 2}. $$

Similarly, keeping just the $d=2$ term in our identity we get $$ a(n+1) \ge A(n/2) \ge \frac{n}{2\log n} a(\lfloor n/2 - n/(2\log n) \rfloor), $$ and iterating this gives the desired lower bound $$ \log a(n) \ge (1+o(1)) \frac{(\log n)^2}{2\log 2}. $$

Improve this answer
$\endgroup$

You must log in to answer this question.

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