Upper bound for sum of binomials $\sum_{k=0}^{d}{N-1\choose k}$

Question

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?

Answer 1

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.)

Answer 2

A different proof that works for $N>3d$. Using $(8.17.4)$ and $(8.17.5)$, 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 \mathrm{d}t} . $$ Now \begin{align*} \int_0^{1/2} {t^{N - d - 2} (1 - t)^d \mathrm{d}t} & = \int_0^{1/2} {t^{N - 2d - 2} t^d (1 - t)^d \mathrm{d}t} \\ & \le \frac{1}{{2^{2d} }}\int_0^{1/2} {t^{N - 2d - 2} \mathrm{d}t} = \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!}}. $$