Upper bound for sum of binomials $\sum_{k=0}^{d}{N-1\choose k}$ I am interested to find a proof for the following upper bound.
$$\sum_{k=0}^{d}\begin{pmatrix}N-1\\k\end{pmatrix} \leq \frac{2N^d}{d!}$$
for $N\geq 3d$. I have tried to bound the sum by $(d+1)$ times the maximum of the binomial (attained at $k = d$), which yields the upper bound $2N^{d+1}/d!$ (worse by a factor of $N$). However, I could not find a proof for the above inequality.
Any ideas on how to start the proof?
 A: True when $d = 0$.
Suppose true up to $d-1$ for $d \geq 1$.  Need
\begin{align*}
\frac{(N-1)!}{(N-d-1)!\ d!} &\leq \frac{2N^d}{d!} - \frac{2N^{d-1}}{(d-1)!}  \\
    &= \left(1 - \frac{d}{N} \right) \frac{2N^d}{d!}  \text{,}
\end{align*}
simplifying to
$$  \frac{(N-1)!}{(N-d-1)!} \leq \left(1 - \frac{d}{N} \right) 2 N^d  \text{.}  $$
The left-hand side is less than or equal to $N^d$ and (using the constraint between $N$ and $d$), the right-hand side is greater than or equal to $\frac{4}{3}N^d$.
(If the displayed inequality is a little mysterious, ask how each side of your inequality changes going from $d-1$ to $d$.  In detail, write out \begin{align*}
k &= 0 &&:& \frac{(N-1)!}{(N-1)!\ 0!} &\leq \frac{2N^0}{0!}  \\
k &= 1 &&:& \frac{(N-1)!}{(N-1-1)!\ 1!} &\leq \frac{2N^1}{1!} - \frac{2N^0}{0!} \\
  &  &&&  &\vdots  \\
  &  &&& \frac{(N-1)!}{(N-k-1)!\ k!} &\leq \frac{2N^k}{k!} - \frac{2N^{k-1}}{(k-1)!}  \\
  &  &&& &\vdots  \\
k &= d &&:& \frac{(N-1)!}{(N-d-1)!\ d!} &\leq \frac{2N^d}{d!} - \frac{2N^{d-1}}{(d-1)!}
\end{align*}
Summing the left-hand sides gives the sum you ask about.  Summing the right-hand sides telescopes to the term you want to compare with.)
A: A different proof that works for $N>3d$. Using http://dlmf.nist.gov/8.17.E4 and http://dlmf.nist.gov/8.17.E5, your sum may be re-expresssed in terms of the incomplete beta function:
$$
2^{N - 1} I_{1/2} (N - d - 1,d + 1) = 2^{N - 1} \frac{{\Gamma (N)}}{{\Gamma (N - d - 1)d!}}\int_0^{1/2} {t^{N - d - 2} (1 - t)^d dt} .
$$
Now
\begin{align*}
\int_0^{1/2} {t^{N - d - 2} (1 - t)^d dt} & = \int_0^{1/2} {t^{N - 2d - 2} t^d (1 - t)^d dt} \\ & \le \frac{1}{{2^{2d} }}\int_0^{1/2} {t^{N - 2d - 2} dt}  = \frac{1}{{2^{N - 1} }}\frac{1}{{N - 2d - 1}}.
\end{align*}
So your sum is at most
$$
\frac{1}{{N - 2d - 1}}\frac{{\Gamma (N)}}{{\Gamma (N - d - 1)d!}} = \frac{{N - d - 1}}{{N - 2d - 1}}\frac{{\Gamma (N)}}{{\Gamma (N - d)d!}} \le 2\frac{{\Gamma (N)}}{{\Gamma (N - d)d!}} \le \frac{{2N^d }}{{d!}}.
$$
