Proof of asymptotics of a recursion or functional equation In his answer to this question seeking the asymptotics of 
$$a_n = 1+\frac1{2^n}\sum_{k=0}^n {n\choose k}a_k,\, \forall n\in\mathbf N,\, a_0=0.$$
for $n\to\infty$, @JackD'Aurizio continued my approach and provided two summation expressions
$$a_s=\sum_{m=1}^{s}\binom{s}{m}\frac{(-1)^{m+1}}{1-\frac{1}{2^m}}=\sum_{k\geq 1}\left[1-\left(1-\frac{1}{2^k}\right)^s\right].$$
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, both of us failed to prove this heuristic result. I am hereby seeking a rigorous proof.
 A: A quick computation. We show that  $a_n = \log_2 n + \mathcal{O}(1)$. Notice that $x \mapsto 1 - (1-2^{-x})^n$ is decreasing in $x$ for each $n \geq 1$. So
$$ a_n = \sum_{j=0}^{\infty} (1 - (1 - 2^{-j})^n) \leq 1 + \int_{0}^{\infty}(1 - (1 - 2^{-x})^n) \, dx = 1 + \frac{H_n}{\log 2}, $$
where $H_n = \sum_{k=1}^{n} \frac{1}{k}$ is the harmonic numbers and the integral is computed using the substitution $u = 1-2^{-x}$. A lower bound is obtained in a similar way:
$$ a_n \geq \int_{0}^{\infty}(1 - (1 - 2^{-x})^n) \, dx = \frac{H_n}{\log 2}. $$

More detailed result. Write $F_{n}(x) = (1 - 2^{-x})^n$. Using Euler-MacLaurin formula, we find that
$$ a_n = \frac{H_n}{\log 2} + \frac{1}{2} - \int_{0}^{\infty} \tilde{B}_1(x)  \, dF_n(x), $$
where $\tilde{B}_1(x)$ is the periodic Bernoulli polynomial of degree 1. Notice that the bound $|\tilde{B}_1(x)| \leq \frac{1}{2}$ replicates the previous inequalities.
Now let $X_i \sim \mathrm{Exp}(\log 2)$ be i.i.d. and $M_n = \max\{X_1, \cdots, X_n\}$. Then $\mathbb{P}[M_n \leq x] = F_n(x)$ and $M_n - \log_2 n \Rightarrow G$, where $G$ satisfies $\mathbb{P}[G \leq x] = \exp(-2^{-x})$. From this, we may expect that
\begin{align*}
a_{n}
&= \frac{H_{n}}{\log 2} + \frac{1}{2} - \mathbb{E}[\tilde{B}_1(M_{n})] \\
&= \frac{H_{n}}{\log 2} + \frac{1}{2} - \mathbb{E}[\tilde{B}_1(G + \log_2 n)] + o(1)
\end{align*}
holds. Indeed this is not terribly hard to establish using the continuous mapping theorem. Finally, numerical computations suggests that $\alpha \mapsto \mathbb{E}[\tilde{B}_1(G + \alpha)]$ is quite small (of order $10^{-6}$) but not identically zero, hence $a_n$ should exhibit an oscillation which slows down at logarithmic speed.
