Upper bound for sum of binomial coefficients I need to provide a reasonable upper bound for the following sum for large $N$, and a given $c \in (0,1], q \in [0, 1]$:
$$
\sum_{n= [ c N ] }^{N} \binom{N}{n} q^n
$$
Is there a good formula for such an upper bound? It is not clear to me under which conditions on $c$ and $q$ it diverges to infinity with $N$ or it goes to 0 exponentially fast with $N$.
Note that for any $q$ and $N$,
$$
\sum_{n= 0 }^{N} \binom{N}{n} q^n = ( 1 + q)^N.
$$
 A: Your sum, call it $S(c,q,N)$, is similar to a tail of a binomial distribution. The normal distribution is a reasonable approximation to the binomial distribution, and there are algebraic estimates for tails of normal distributions. Therefore, it's possible to get an algebraic estimate for your sum. In the computation below, the "critical value" of $c$ will become apparent.
In a binomial experiment with $N$ trials and probability of success $\alpha$ and failure $\beta=1-\alpha$, the probability of exactly $n$ successful trials is $\binom Nn\alpha^n\beta^{N-n}$. To match your sum, we must have $\alpha\beta^{-1}=q$. This is equivalent to $\alpha=\frac q{1+q}$ and $\beta=\frac 1{1+q}$. So, 
\begin{eqnarray*}
% \nonumber to remove numbering (before each equation)
  S(c,q,N) &=& (1+q)^N\sum_{n=cN}^N \binom Nn\alpha^n\beta^{N-n} \\
    &=& (1+q)^N\text{Binomial} (n\ge cN,\text{probability of success }\alpha,\text{number of trials }N).
\end{eqnarray*}
A binomial distribution with probability of success $\alpha$ and $N$ trials is nicely approximated by a normal distribution with mean $N\alpha$ and standard deviation $\sqrt{N\alpha(1-\alpha)}$. So,
$$S(c,q,N)\approx (1+q)^N\text{Normal}\left(X>cN, \text{mean }N\alpha,\text{standard deviation }\sqrt{N\alpha(1-\alpha)}\right).$$
As usual, this distribution can be standardized by subtracting the mean and then dividing by the standard deviation. So, 
$$S(c,q,N)\approx(1+q)^N\text{Standard Normal}\left(Z>\frac{cN-\alpha N}{\sqrt{N\alpha(1-\alpha)}}=(c-\alpha)\sqrt{\frac{N}{\alpha(1-\alpha)}}\right).$$
Therefore, the critical value of $c$ is $\alpha=\frac q{1+q}$ in the sense that if $c<\frac q{1+q}$, then the cumulative probability in the standard normal distribution approaches 1 as $N$ gets large and in this case $S(c,q,N)$ approaches $(1+q)^N$. On the other hand, if $c>\frac q{1+q}$, then the cumulative probability in the standard normal distribution is a right tail. A "first order" approximation of a right tail in a standard normal distribution is
$$\text{Standard Normal}(Z>x)\approx \frac{{\text{e}}^{-\frac{x^2}2}}{x\sqrt{2\pi}}.$$
So, if $c>\frac q{1+q}$, then 
\begin{eqnarray*}
% \nonumber to remove numbering (before each equation)
  S(c,q,N) &\approx& (1+q)^N\frac{{\text{e}}^{-\frac{(c-\alpha)^2 N}{2\alpha(1-\alpha)}}}{(c-\alpha)\sqrt{\frac{2\pi N}{\alpha(1-\alpha)}}} 
\end{eqnarray*}
After expressing everything in terms of the original variables, in the case of $c>\frac q{1+q}$ we get
$$S(c,q,N) \approx\frac{{\text{e}}^{N\bigl(\log(1+q)-\frac{(c-\frac {q}{1+q})^2(1+q)^2}{2q}\bigr)}}{\bigl((1+q)c-q\bigr)\sqrt{\frac{2\pi N}{q}}}.$$
