Show that $\sum^k_{i=0} \binom{n}{i} \leq 2 \binom{n}{k}$, sum of 'the first k' binomial coefficients 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.
 A: 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}$$
A: 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$.
A: 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$.
