approximation of binomial coefficient sum I would like to find some approximation or upper & lower bounds on the next simple expression:
\begin{align}
\sum_{i = 0}^{k} \binom{h}{i}  \qquad h \geq k
\end{align}
But I need this approximation/bounds to be computable in polylogarithmic time - i.e. in: \begin{align}
O(\log_{}^{c} h)  \qquad c \in N
\end{align}
If you still follow you may be intrested in my specific problem:
given two numbers:
\begin{align}
n, k \in N  \qquad n \geq 2^k
\end{align}
find in polylogarithmic time (as function of n) a number:
\begin{align}
h \in N
\end{align}
such that:
\begin{align}
\sum_{i = 0}^{k} \binom{h-1}{i} < n \le \sum_{i = 0}^{k} \binom{h}{i}
\end{align}
It is obvious that:
\begin{align}
\lceil \log_{2}n \rceil \leq h \leq n-1
\end{align}
Thanks in advance.
 A: After thinking about this for few more hours, I came up with a solution to my specific problem (with no approximations):
Claim: The specified problem is computable in $O(\log^3n)$.
Proof: Note that $n \ge 2^k \rightarrow k \le log_2n \rightarrow k=O(\log n)$
Lemma: The comparison of $\sum_{i = 0}^{k} \binom{h}{i}$ with $n$ is computable in $O(k\log n)$
Proof of lemma: consider the following algorithm:
$1.\;choose \leftarrow 1 \\ 2.\;sum\leftarrow 0 \\3.\;for \; i=1 \; to \; k \; do: \\ 3.1. \;\;\; sum \leftarrow sum+choose \\ 3.2. \;\;\; choose \leftarrow choose * \frac{h-i}{i+1}\\ 3.3. \;\;\; if \; sum >n \; break \; (exit \; the \; loop) \\ 4. \; comapare \; n \; with  \; sum$
Make sure you understand why this works. Since in any iteration $sum,choose,h,i=O(n)$ and there is a constant amount of arithmetic calculations on this numbers, each iteration takes $O(\log n)$. When we sum all the $\le k+1$ itertions we get total of: $O(k\log n) = O(\log^2n)$.
So as we know how to compare in $O(\log^2n)$, and we know that $\lceil \log_{2}n \rceil \leq h \leq n-1$ (i.e. $O(n)$ possible values), we can binary search $h$ and in each step make the two $O(\log^2n)$ comparissons $\sum_{i = 0}^{k} \binom{h-1}{i} < n \;,\; n \le \sum_{i = 0}^{k} \binom{h}{i}$, yielding a total of $O(\log^3n)$.
