Seeking proof to an asymptotics of a recursion or functional equation

Question

My question on math.stackexchange.com and the continuation by an answer to it gives the two summation expressions for the recursion $$a_n = 1+\frac1{2^n}\sum_{k=0}^n {n\choose k}a_k,\, \forall n\in\mathbf N,\, a_0=0$$ as $$a_s=\sum_{m=1}^{s}\binom{s}{m}\frac{(-1)^{m+1}}{1-\frac{1}{2^m}}=\sum_{k=0}^\infty\left[1-\left(1-\frac{1}{2^k}\right)^s\right].$$ I am seeking an asymptotics to $a_n$ as $n\to\infty$. As stated in the aforementioned answer, 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}$. Approximating $1-\frac{1}{2^k}\approx e^{-\frac1{2^k}}$ and subsequently $a_s$ with $b_s$ where $$b_{2s}-b_s = 1-e^{-s} \approx 1,$$ We obtain heuristically $$a_s \approx b_s\approx D+\log_2s,$$ for some constant $D$.

However, we failed to prove this heuristic result. I am seeking a rigorous proof.

---

We have now the excellent proofs below of Fedor Petrov and Iosif Pinelis. I then happened upon this exact same quesiton. It has its own answers and several related references. Here is another appearance of the same problem with many answers and references to powerful tools.

Answer 1

I claim that $$a_s=\log_2s+\frac\gamma{\log2}-\frac12+\log 2\int_{-\infty}^\infty\exp(-2^{-y})2^{-y}\left(\{y+\log_2s\}-\frac12\right)dy+o(1).$$ The integral term is a 1-periodic function of $\log_2 s$.

Denote $f(x)=1-(1-2^{-x})^s$. Then $f(0)=1,f(+\infty)=0$ and $f$ decreases on $[0,\infty)$. Thus $\sum_{k\geqslant 1} f(k)\leqslant \int_0^\infty f(x)dx\leqslant \sum_{k\geqslant 0} f(k)$. Look at the integral. Denote $1-2^{-x}=t$, then $t$ varies between 0 and 1. Next, $-x=\log(1-t)/\log 2$, so $dx=\frac{dt}{(1-t)\log 2}$ and the integral rewrites as $\frac1{\log2}\int_0^1\frac{1-t^s}{1-t}dt$. When $s$ is a positive integer, the integral equals $$\int_0^1 (1+t+t^2+\dots+t^{s-1}) dt=1+1/2+1/3+\dots+1/s=\log s+\gamma+o(1),$$ the same holds for non-integral $s$ by monotonicity in $s$. So we get $\sum_{k\geqslant 1} f(k)=\log_2 s+A(s)+o(1)$, where $$A(s)=\frac\gamma{\log 2}-\frac12+\sum_{k=1}^\infty\left( \frac{f(k-1)+f(k)}2-\int_{k-1}^kf(x)dx\right).$$ By Euler--Maclaurin integration by parts, we write $$\int_{k-1}^k f(x)dx=\int_{k-1}^k f(x)d\left(x-k+\frac12\right)=\frac{f(k-1)+f(k)}2-\int_{k-1}^k\left(x-k+\frac12\right)f'(x)dx.$$ Thus $$A(s)=\frac\gamma{\log 2}-\frac12+\int_0^\infty \left(\{x\}-\frac12\right)f'(x)dx.$$

Our goal is to estimate the last integral with prescribed accuracy $\varepsilon$. Choose large $M$, then the value $f(\log_2s\pm M)$ are close to 0 and 1, and we may choose $M$ so large that $f(\log_2s+M)+1-f(\log_2s-M)<\varepsilon/5$. Then the integral outside the segment $[\log_2s-M,\log_2s+M]$ is less than $\varepsilon/10$ in absolute value (we use $\int_{x_1}^{x_2}|f'(x)|dx=f(x_1)-f(x_2)$, that follows by monotonicity.) On the segment $[\log_2s-M,\log_2s+M]$ we use the change of variables $x=\log_2s+y$, $y\in [-M,M]$. Then $$-f'(x)=s(1-2^{-x})^{s-1}2^{-x}\log 2=\log 2\cdot 2^{-y}(1-s^{-1}2^{-y})^{s-1}.$$ Uniformly on $[-M,M]$ the expression $(1-s^{-1}2^{-y})^{s-1}$ is close for large $s$ to $e^{-2^{-y}}$. Therefore within another $\varepsilon/10$, the integral over $[\log_2s-M,\log_2s+M]$ is close to $$\log 2\int_{-M}^M 2^{-y}e^{-2^{-y}}\left(\{y+\log_2s\}-\frac12\right)dy.$$ The upper and lower limits may be replaced by $\pm \infty$ (within another $\varepsilon/10$), and we get the claim.

Answer 2

Let $c_k:=(1-\frac1{2^k})^s$ and $b_k:=1-c_k$, so that \begin{equation} a_s=\sum_{k\ge0}b_k. \tag{1} \end{equation} Let $k_s:=\lceil \log_2 s\rceil$, so that $s/2^{k_s}\in[1/2,1]$. Clearly, $b_k\le1$, whence \begin{equation} \sum_0^{k_s}b_k\le k_s+1.\tag{2} \end{equation} On the other hand, $c_k\le d_k:=e^{-s/2^k}$ and the ratio $d_{j-1}/d_j=d_j$ is increasing in $j$, with $d_{k_s}\in[1/e,1/\sqrt e]$. So, majorizing $\sum_0^{k_s}d_k$ by a geometric series, we have \begin{equation} \sum_0^{k_s}c_k\le\sum_0^{k_s}d_k\le\frac{d_{k_s}}{1-d_{k_s}}=O(1). \tag{3} \end{equation} Also, $b_k\le\frac s{2^k}$ and hence \begin{equation} 0\le\sum_{k>k_s}b_k\le\sum_{k>k_s}\frac s{2^k}=\frac s{2^{k_s}}\le1. \tag{4} \end{equation} Collecting (1)--(4) and recalling that $b_k=1-c_k$, we have \begin{equation*} a_s=k_s+O(1)=\log_2 s+O(1). \end{equation*}