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

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

• Excellent. +1 Thank you. – Hans May 24 '18 at 20:28
• Would you be interested in taking a look at this question math.stackexchange.com/q/3386637/64809 also regarding asymptotics? – Hans Oct 9 '19 at 18:29

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

• Oh, darn, I should have run my last expression in the opposite direction just as you do in your first line... Anyway, you are right. Both the finite and infinite sums are good. Are you able to answer the main question, the second question, regarding the asymptotics of $a_n$ for large $n$? – Hans Jan 28 '18 at 22:54
• The term between square brackets is approximately s/2^k, so such sequence has an approximately linear growth. – Jack D'Aurizio Jan 28 '18 at 22:59
• I am not so sure about that. What about the terms of $\big(\frac{s}{2^k}\big)^j$ for larger $j$'s? Bear in mind we are looking at large $s$. – Hans Jan 28 '18 at 23:05
• @Hans: answer updated. $a_s$ behaves like $s$ for (very) small values of $s$ and is bounded by a multiple of $\log(s)$ for (moderately) large values of $s$. – Jack D'Aurizio Jan 29 '18 at 14:04
• Nice idea. 1) It is best not to mention the case for small $s$ which is obvious from the original recursion. 2) Could you please make the asymptotic argument, which I think is right, rigorous? – Hans Jan 29 '18 at 17:20