Show that $\sum^k_{i=0} \binom{n}{i} \leq 2 \binom{n}{k}$, sum of 'the first k' binomial coefficients

Question

I was reading an article on information theory and I came across this upper bound for the sum of 'the first k' binomial coefficients

Consider $n \in \mathbb{N}$.

For $0 \leq k \leq \lceil\frac{n}{3}\rceil$ we have

$\sum^k_{i=0} \binom{n}{i} \leq 2 \binom{n}{k}$

I found this article on mathoverflow about upper bounds for the sum of 'the first k' binomial coefficients, but I haven't been able to work out a proof for it.

Answer 1

Hint: $${n \choose i-1} = {n \choose i} \frac{i}{n+1-i} \le \frac{1}{2} {n \choose i} \ \text{if}\ i < \frac{n+1}{3}$$

Answer 2

As I stated (seven years ago!) in that post on MathOverflow, the quotient

$${\sum_{i=0}^k {n \choose i} \over {n \choose k}} = 1 + {k \over n-k+1} + {k(k-1) \over (n-k+1)(n-k+2)} + \cdots$$

can be bounded above by the geometric series

$$ 1 + {k \over n-k+1} + \left( k \over n-k+1 \right)^2 + \cdots = {n-(k-1) \over n-(2k-1)}. $$

This gives you the inequality

$$ \sum_{i=0}^k {n \choose i} \le {n-(k-1) \over n-(2k-1)} {n \choose k}$$

and so you just need to show that ${n-(k-1) \over n-(2k-1)} \le 2$ when $k \le \lceil n/3 \rceil$.

Answer 3

Fix a nonnegative integer $k\leq \left\lceil\frac{n}{3}\right\rceil$. For each $r=0,1,2,\ldots,k-1$, let $S_r$ denote the set of all $k$-subsets of $\{1,2,\ldots,n\}$ of the form $A\cup \{n,n-1,\ldots,n-k+r-1\}$ with $A$ being an $r$-subset of $\{1,2,\ldots,k\}$. Due to the assumption $k\leq \left\lceil\frac{n}{3}\right\rceil$, it can be easily seen that the $S_r$'s are mutually disjoint. As $\displaystyle\bigcup_{r=0}^{k-1}\,S_r$ consists of $k$-subsets of $\{1,2,\ldots,n\}$, we conclude that $$\sum_{r=0}^{k-1}\,\binom{n}{r}=\sum_{r=0}^{k-1}\,\left|S_r\right|=\left|\bigcup_{r=0}^{k-1}\,S_r\right|\leq \binom{n}{k}\,.$$ This is equivalent to the required inequality.

P.S.: It appears to be the case that this proof works for all nonnegative integers $k\leq \left\lfloor\frac{n-1}{2}\right\rfloor$. The inequality is also strict because $\{n,n-1,\ldots,n-k+1\}$ is a $k$-subset of $\{1,2,\ldots,n\}$ which does not lie in any $S_r$.