Asymptotics of a recursive sequence

I am asking for the asymptotics of a sequence $(a_n)_{n=0}^\infty$ defined by the following recursion relation $$a_n = 1+\frac1{2^n}\sum_{k=0}^n {n\choose k}a_k,\, \forall n\in\mathbf N,\, a_0=0.$$ We can construct a generating function $f(x)=\sum_{n=0}^\infty \frac{a_n}{n!}x^n$. $$f(x)=\sum_{n=0}^\infty \frac{a_n}{n!}x^n = \sum_{n=1}^\infty \frac{x^n}{n!}+\sum_{n=0}^\infty\sum_{k=0}^n\frac{a_k}{k!}\Big(\frac x2\Big)^k \frac1{(n-k)!}\Big(\frac x2\Big)^{n-k}=e^x-1+f\Big(\frac x2\Big)e^{\frac x2},$$ or $$g(2x)=1-e^{-2x}+g(x)\Longleftrightarrow g(2^nx)-g(x)=n-\sum_{k=1}^ne^{-2^kx},\ g(x) := f(x)e^{-x}.$$ Is there an analytic expression for $g$? What is the aymptotics of $a_n$ as $n\to\infty$?

If there is an analytic expression, we can use the Cauchy residue theorem to analyze the asymptotics of $a_n$.

Solution 1:

Let $h(x)=f(x)e^{-x}$. We have

$$h(x) = 1-e^{-x}+h\left(\frac{x}{2}\right)=\sum_{n\geq 0}\left(1-e^{-x/2^n}\right)=\sum_{n\geq 0}\sum_{m\geq 1}\frac{(-1)^{m+1} x^m}{m! 2^{mn}} $$ hence $$ h(x) = \sum_{m\geq 1}\frac{(-1)^{m+1}x^m}{m!\left(1-\frac{1}{2^m}\right)}$$ and $$ f(x)=\sum_{n\geq 0}\frac{x^n}{n!}\sum_{m\geq 1}\frac{(-1)^{m+1} x^m}{m!\left(1-\frac{1}{2^m}\right)}=\sum_{s\geq 1}\frac{x^s}{s!}\sum_{m=1}^{s}\binom{s}{m}\frac{(-1)^{m+1}}{1-\frac{1}{2^m}}$$ where $$ \sum_{m=1}^{s}\binom{s}{m}\frac{(-1)^{m+1}}{2^{km}}=1-\left(1-\frac{1}{2^k}\right)^s $$ ensures $$ f(x)=\sum_{s\geq 1}\frac{x^s}{s!}\underbrace{\sum_{k\geq 0}\left[1-\left(1-\frac{1}{2^k}\right)^s\right]}_{a_s}.$$

If we approximate $\left[1-\left(1-\frac{1}{2^k}\right)^s\right]$ with $\frac{s}{2^k}$ we have $a_s\approx s$. On the other hand the approximation $\left[1-\left(1-\frac{1}{2^k}\right)^s\right]\approx \frac{s}{2^k}$ is accurate only for small values of $s$; $1-e^{-s/2^k}$ is much better. Using the explicit representation for $a_s$, numerical experiments suggest that $$ a_s \approx A \log\left(B+Cs\right)\qquad \text{for }s\to +\infty$$ with $A\approx C\approx \sqrt{2}\approx\frac{1}{\log 2}$ and $a_s$ is clearly related to the Weibull distribution, appearing, for instance, in the Fisher–Tippett–Gnedenko theorem. Indeed, by defining $$b_s=\sum_{k\geq 0}\left(1-e^{-s/2^k}\right) $$ we have $$ b_{2s}-b_s = 1-e^{-s} \approx 1\text{ for large values of }s$$ and the only regular solutions of $b_{2s}-b_s=1$ are $b_s=D+\log_2(s)$.

Solution 2:

W. Szpankowski in 'Average Case Analysis of Algorithms on Sequences' treats this exact problem in Example 10.6. The techniques used are Mellin transforms and analytic depoissonization (no probabalistic arguments). His result is, up to the first 2 oscillatory terms,

$$a_n \sim \frac{\log(n) + \gamma}{\log2}+\frac{1}{2} + P_0 + \frac{1}{2n}P_2$$ $$ P_0 = \frac{1}{\log2}\sum_{k=1}^{\infty}\, \Gamma(\frac{2\pi\,i\,k}{\log{2}})\exp{(-2\pi i k \frac{\log{n}}{\log{2}})} +\Gamma(\frac{-2\pi\,i\,k}{\log{2}})\exp{(2\pi i k \frac{\log{n}}{\log{2}})}.$$

$$ P_2 = \frac{1}{\log2}\sum_{k=-\infty}^{\infty}\, \Gamma(2+\frac{2\pi\,i\,k}{\log{2}})\exp{(-2\pi i k \frac{\log{n}}{\log{2}})} $$

About 4 digits agreement are obtained for $n$ as small as 15. The problem is stated in Jack D'Aurizrio's alternate expression for $a_n,$ $$ a_n = \sum_{k=0}^{\infty} \big(1-(1-2^{-k})^n\big) .$$