4
$\begingroup$

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.

$\endgroup$

3 Answers 3

6
$\begingroup$

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}$$

$\endgroup$
1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I don't think this works. Counterexample: $n=10, k = 4$. Then $\frac{n-(k-1)}{n-(2k-1)} > 2$. $\endgroup$
    – Seb123
    May 1, 2017 at 10:11
  • $\begingroup$ You're right. It seems that the bound I proved there was slightly weaker than what's needed. $\endgroup$ May 1, 2017 at 13:31
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.