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.