Solve $\sum_{i=0}^k \binom{n}{i} = u$. I would like to get as tight bounds as possible for $k$ from $\sum_{i=0}^k \binom{n}{i} =u $.  In other words, the number of terms in the sum neeeded to get to $u$. We can assume that both $n$ and $u$ are large and that $u$ is exponential in a root of $n$. That is we have very roughly $u \approx 2^{(n^{c})}$ for $0 < c \leq 1$
We know that  $\left(\frac{n}{k}\right)^k\leq\binom{n}{k} \leq \sum_{i=0}^k \binom{n}{i} \leq (k+1) \binom{n}{i} \leq (k+1) \left(\frac{\mathrm{e}n}{k}\right)^k$.   However this doesn't appear to help at all.  

I assume that $0<c<1$.  Let $S(n,k):=\sum_{0\le i\le k} \binom{n}{i}$.  Observe that, since $S(n,\lfloor n/2 \rfloor)$ is asymptotically $2^{n-1}(1+o(1))$, which is much larger than $u$, you will have $k<\lfloor n/2\rfloor$.  Therefore
$$
\binom{n}{k}\le S(n,k) \le (k+1) \binom{n}{k}
$$
and using Stirling's approximation then gives
$$
\log S(n,k) = O(\log n) + n H(\frac{k}{n}),
$$
where $H(x)$ is the entropy function,
$$
H(x)=-x \log x - (1-x) \log (1-x).
$$
Then, since $H(x)=x(1-\log x)+O(x^2)$ for small $x$,
$$
\log u = k(1 +\log n - \log k) + O(\frac{k^2}{n})+O(\log n)\ \ \ \ \ (n\to\infty,\ \frac kn\to 0.)
$$
Assuming that $\log u=\Theta(n^c)$ as you suggest above, you then get the rough estimate
$$
k=\frac{\log u}{(1-c)\log n}(1-\frac{\log \log n}{(1-c)\log n}+O(\frac{1}{\log n})).
$$
