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.