Sequence [A003238 of the OEIS](http://oeis.org/A003238) 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)$.



Are the asymptotics of A003238 known?
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}. 
$$ 


