Asymptotic approximation of sum $\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$ I need to find the asymptotic approximation of this sum
$$\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$$ 
Can you please share a link to theory or hint how it can be solved? 
Here is my attempt $n \approxeq k + 2^{2^k}(k+1)$. How can one get the value of $k(n)$ from this equation?
 A: $$S(n)=\sum_{k=0}^{n}\frac{\binom{n}{k}}{2^{2^k}}=\frac{1}{2}+\sum_{k>\log_2 n}\frac{\binom{n}{k}}{2^{2^k}}+\sum_{1\leq k\leq\log_2 n}\frac{\binom{n}{k}}{2^{2^k}},$$
but since:
$$ \sum_{k>\log_2 n}\frac{\binom{n}{k}}{2^{2^k}}<\frac{1}{2^n}\sum_{k>\log_2 n}\binom{n}{k}<1,$$
we have:
$$S(n)\leq\frac{3}{2}+\sum_{1\leq k\leq\log_2 n}\frac{\binom{n}{k}}{2^{2^k}}\leq \frac{3}{2}+\log_2 n\cdot\max_{1\leq k\leq\log_2 n}\frac{\binom{n}{k}}{2^{2^k}}.$$
In order to find the $k$ that maximizes the ratio, it is sufficient to find a zero of:
$$\frac{d}{dk}\left(\log_2\binom{n}{k}-2^k\right).$$
Switching from derivatives to forward differences, we expect that a suitable approximation of that zero is given by the solution of:
$$\frac{n-k-1}{k+1}=\frac{\binom{n}{k+1}}{\binom{n}{k}}=2^{2^k},$$
or:
$$\frac{n}{k+1}=2^{2^k}+1,$$
so the "stationary" $k$ is expected to lie between $\log_2(\log_2 n)$ and $\log_2\left(\log_2 \frac{n}{\log_2(\log_2 n)}\right)$, giving:
$$ S(n)\leq\frac{\log^{(1)}(n)\log^{(2)}(n)}{n}\cdot 2^{\log^{(1)}(n)\log^{(2)}(n)-\log^{(2)}(n)\log^{(3)}(n)},$$
where $\log^{(\nu)}(n)$ is the $\nu$-fold iterated of $\log_2$.
