$n \approxeq k + 2^{2^k}(k+1)$. How can one get the value of $k(n)$ from this equation? I am trying to find approximation for this sum. Asymptotic approximation of sum $\sum_{k=0}^{n}\frac{{n\choose k}}{2^{2^k}}$
Doing following way. Let $a_k(n) = \frac{n\choose k}{2^{2^k}}$. I tried to find $k$ that $\frac{a_{k+1}(n)}{a_k(n)}$ congregates to finite value other than $0$. I think for that $k$ the sum will be approximately the same as $a_k(n)$.
So I get $n \approxeq k + 2^{2^k}(k+1)$. How can one get the value of $k(n)$ from this equation?   
 A: We'll apply the method used in the answers of this question and this question.
First we write the equation as
$$
n = k2^{2^k} \left(1 + k^{-1} + 2^{-2^k}\right).
$$
For convenience we'll write $\log_2 = \lg$, so that
$$
\lg n = 2^k + \lg k + \lg\left(1 + k^{-1} + 2^{-2^k}\right)
$$
or, rearranging,
$$
2^k = \lg n - \lg k - \lg\left(1 + k^{-1} + 2^{-2^k}\right).
\tag{1}
$$
As $n \to \infty$ so does $k$, so it will eventually be true that
$$
2^k < \lg n,
$$
whence
$$
k < \lg\lg n.
$$
Bootstrapping this into $(1)$ we get that
$$
2^k = \lg n + O(\lg\lg\lg n),
$$
and thus
$$
\begin{align}
k &= \lg\Bigl(\lg n + O(\lg\lg\lg n)\Bigr) \\
&= \lg\lg n + \lg\left(1 + O\left(\frac{\lg\lg\lg n}{\lg n}\right)\right) \\
&= \lg\lg n + O\left(\frac{\lg\lg\lg n}{\lg n}\right). \tag{2}
\end{align}
$$
We can bootstrap again, but first we'll write
$$
\lg\left(1 + k^{-1} + 2^{-2^k}\right) = \frac{1}{k\log 2} + O\left(\frac{1}{k^2}\right),
$$
so that $(1)$ becomes
$$
2^k = \lg n - \lg k - \frac{1}{k\log 2} + O\left(\frac{1}{k^2}\right).
\tag{3}
$$
Substituting $(2)$ into this yields
$$
\begin{align}
2^k &= \lg n - \lg\left(\lg\lg n + O\left(\frac{\lg\lg\lg n}{\lg n}\right)\right) \\
&\qquad - \frac{1}{\log 2\left(\lg\lg n + O\left(\frac{\lg\lg\lg n}{\lg n}\right)\right)} + O\left(\frac{1}{(\lg\lg n)^2}\right).
\end{align} \tag{4}
$$
We expand each term; the first is
$$
\begin{align}
\lg\left(\lg\lg n + O\left(\frac{\lg\lg\lg n}{\lg n}\right)\right) &= \lg\lg\lg n + \lg\left(1 + O\left(\frac{\lg\lg\lg n}{(\lg n)\lg\lg n}\right)\right) \\
&= \lg\lg\lg n + O\left(\frac{\lg\lg\lg n}{(\lg n)\lg\lg n}\right)
\end{align}
$$
and the second is
$$
\begin{align}
\frac{1}{\lg\lg n + O\left(\frac{\lg\lg\lg n}{\lg n}\right)} &= \frac{1}{\lg\lg n} \frac{1}{1+O\left(\frac{\lg\lg\lg n}{(\lg n)\lg\lg n}\right)} \\
&= \frac{1}{\lg\lg n} \left(1+O\left(\frac{\lg\lg\lg n}{(\lg n)\lg\lg n}\right)\right) \\
&= \frac{1}{\lg\lg n} + O\left(\frac{\lg\lg\lg n}{(\lg n)(\lg\lg n)^2}\right).
\end{align}
$$
Comparing the three error terms
$$
O\left(\frac{1}{(\lg\lg n)^2}\right), \quad O\left(\frac{\lg\lg\lg n}{(\lg n)\lg\lg n}\right), \quad \text{and} \quad O\left(\frac{\lg\lg\lg n}{(\lg n)(\lg\lg n)^2}\right),
$$
we see that $O\left(\frac{1}{(\lg\lg n)^2}\right)$ is the largest.  We therefore retain only this one, and $(4)$ becomes
$$
2^k = \lg n - \lg\lg\lg n - \frac{1}{(\log 2)\lg\lg n} + O\left(\frac{1}{(\lg\lg n)^2}\right).
\tag{5}
$$
By taking $\lg$ of both sides we obtain
$$
\begin{align}
k &= \lg\left(\lg n - \lg\lg\lg n - \frac{1}{(\log 2)\lg\lg n} + O\left(\frac{1}{(\lg\lg n)^2}\right)\right) \\
&= \lg\lg n + \lg\left(1 - \frac{\lg\lg\lg n}{\lg n} - \frac{1}{(\log 2)(\lg n)\lg\lg n} + O\left(\frac{1}{(\lg n)(\lg\lg n)^2}\right)\right) \\
&= \lg\lg n - \frac{\lg\lg\lg n}{(\log 2)\lg n} - \frac{1}{(\log 2)^2(\lg n)\lg\lg n} + O\left(\frac{1}{(\lg n)(\lg\lg n)^2}\right).
\end{align}
$$
Consequently,

$$
k = \lg\lg n - \frac{\lg\lg\lg n}{(\log 2)\lg n} - \frac{1}{(\log 2)^2(\lg n)\lg\lg n} + O\left(\frac{1}{(\lg n)(\lg\lg n)^2}\right).
$$

