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

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
Commented Jan 28, 2018 at 22:54
• The term between square brackets is approximately s/2^k, so such sequence has an approximately linear growth. Commented Jan 28, 2018 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
Commented Jan 28, 2018 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$. Commented Jan 29, 2018 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
Commented Jan 29, 2018 at 17:20

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
Commented May 24, 2018 at 20:28
• Would you be interested in taking a look at this question math.stackexchange.com/q/3386637/64809 also regarding asymptotics?
– Hans
Commented Oct 9, 2019 at 18:29