[My question on math.stackexchange.com][1] and the continuation by [an answer][2] 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 happened upon [this exact same quesiton][3]. It has its own answers and several related references.


  [1]: https://math.stackexchange.com/q/2625685/64809
  [2]: https://math.stackexchange.com/a/2625724/64809
  [3]: https://mathoverflow.net/q/46777/32660