4
$\begingroup$

In short, I want to use the Mellin transform to obtain the asymptotic behavior of the sequence $D_n = \frac{ [z^n] D(z)} {C_n}$ where $$ D(z) = \frac 1{2z}\sum_{p \ge 1}C_p \left( \sqrt{1-4z+4z^{p+1}}-\sqrt{1-4z}\right) $$ and $C_n=\frac 1 {n+1} \binom{2n}n$ denotes the $n$-th Catalan number.

The generating function $D(z)$ describes the average size of the so-called minimal directed acyclic graph of a binary tree. It is taken from the paper Analytic variations on the common subexpression problem and its asymptotic is there proven to be $2 \sqrt{\frac{\ln 4}{\pi}}\frac{n}{\sqrt{\ln n}}$.
However, since that proof is rather complicated (a detailed proof can be found in the appendix of this paper), because the form of the generating function just screams for Mellin analysis via so-called harmonic sums, and lastly, because there is an analysis of the very similar generating function $$ U(z) = \frac 1{2}\sum_{p \ge 1}\left(\sqrt{1-4z+2^{p+1}z^{p+1}}-\sqrt{1-4z}\right) $$ in this paper by F. Disanto, I believe that an analysis via Mellin is possible and insightful.

Some background. The main reference I used for Mellin transforms is the paper Mellin transforms and asymptotics: Harmonic sums.Harmonic sums are functions of the form $$ G(z) = \sum_{k } \lambda_k g(\mu_k z) $$ and the aforementioned paper derives under which circumstances the Mellin transformation of those functions may be "factored" to the Mellin transform of the function $g(z)$ multiplied by the so-called Dirichlet series $$ \Lambda(s) = \lambda_k \mu_k^{-s}. $$

Where I got stuck. I first carefully followed the paper by Disanto, but the derived function did not meet the requirements under which the function may be factored. This resulted in this question. However, I later noticed that I had made a mistake in the very beginning: Disanto replaces the term $\sqrt{1-4z+2^{p+1}z^{p+1}}$ by $\sqrt{1-4z+2^{-p-1}}$, and shows that the induced error is bounded. Yet in our case, if we replace $\sqrt{1-4z+4z^{p+1}}$ by $\sqrt{1-4z+4^{-p}}$, the corresponding error becomes infinite (this is caused by the Catalan series in the sum).

So I am looking for a different estimate of the term $\sqrt{1-4z+4z^{p+1}}$, possibly one that splits the $p$ away from the $z$, as I think that's the best way to later be able to factor the Dirichlet series away from the base function.

$\endgroup$

migrated from math.stackexchange.com Jun 5 '15 at 13:53

This question came from our site for people studying math at any level and professionals in related fields.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.