# Upper Bounds on Binomial Coefficients using Stirling’s Approximation

We need to bound the binomial coefficients a lot of times. In this post, we will prove bounds on the coefficients of the form ${n \choose k}, {n \choose \alpha n}$ and ${(1-\alpha)n \choose \alpha n}$ where $\alpha \in (0, 1/2]$ and $\alpha n$ is an integer.

Proposition 1. For positive integers $n, k$ such that $1 \leq k \leq n$,

$\displaystyle {n \choose k} \leq \left( \frac{n e}{k} \right)^k.$

Proposition 2. For a positive integer $n$ and any $\alpha$ such that $\alpha n \in \mathbb{N}$ and $\displaystyle \frac{1}{n} \leq \alpha \leq \frac{1}{2}$,

$\displaystyle {n \choose \alpha n} \leq 2^{n H(\alpha)}$

where the binary entropy function $H : [0, 1] \rightarrow [0, 1]$ is defined as follows:

$\displaystyle H(\alpha) := \left\{ \begin{array}{ll}0\,, & \text{ if } \alpha \in \{0, 1\}\\ -\alpha \log_2(\alpha) - (1-\alpha) \log_2(1-\alpha)\, , & \text{ if } \alpha \in (0, 1) \end{array} \right.$

Proposition 3. For a positive integer $n$ and any $\alpha$ such that $\alpha n \in \mathbb{N}$ and $\displaystyle 1 \leq n\alpha \leq \left\lfloor n\left( \frac{1}{2} - \frac{1}{2n} \right) \right\rfloor$ ,

$\displaystyle {(1-\alpha)n \choose \alpha n} \leq \frac{2^{(1-\alpha)n\,H\left( \frac{\alpha}{1-\alpha} \right)} }{ \sqrt{(1-2\alpha) n}} \leq 2^{(1-\alpha)n\,H\left( \frac{\alpha}{1-\alpha} \right)}$

where $H(.)$ is the binary entropy function.

### Proof of Proposition 1

First, recall the power series $e^k=\sum_{i=0}^\infty{\frac{k^i}{i!}}$. For $k \geq 1$, this sum is definitely larger than its $k$th term only. In other words, $e^k \geq k^k/k!$, which implies $k! \geq (k/e)^k$. Now,

$\begin{array}{lcl} {n\choose k} &=& \frac{n!}{k! \cdot (n-k)!}\\ &=& \frac{n(n-1)(n-2)\cdots (n-(k-1))}{k!}\\ &\leq& \frac{n^k}{k!} \\ &\leq& \frac{n^k}{(k/e)^k} \\ &=& (\frac{en}{k})^k.\\ \end{array}$

This proof is extracted from the StackExchange discussion here. For more inequalities/bounds for binomial coefficients, see Wikipedia.

### Proof of Proposition 2

Let us briefly recall Stirling’s approximation of $n!$.

Theorem (Stirling’s approximation). For any positive integer $n$,

$\displaystyle n! = \sqrt{2\pi n}\left( \frac{n}{e} \right)^n e^{r(n)}$ where $\displaystyle \frac{1}{12n} < r(n)< \frac{1}{12n+1}\, .$

$\displaystyle \begin{array}{lcl} {n \choose \alpha n} &=& \frac{n!}{(\alpha n)!\, \left( (1-\alpha)n \right)! }\\ &\approx & \frac{\sqrt{2\pi n}(\frac{n}{e})^n}{2\pi n\sqrt{\alpha (1-\alpha)}(\frac{\alpha n}{e})^{\alpha n}(\frac{(1-\alpha)n}{e})^{(1-\alpha)n} } \exp\left( \frac{1}{12n} - \frac{1}{12\alpha n + 1} - \frac{1}{12(1-\alpha)n+1}\right) \\ &\leq & 2^{nH(\alpha)} \, \frac{ e^{1/12 n} }{ \sqrt{2 \pi n\alpha (1-\alpha)}} \\ &\leq & 2^{nH(\alpha)} \, \frac{ e^{1/12 n} }{ \sqrt{2 \pi (1-\alpha)}} \text{ since } n\alpha > 1 \\ &\leq & \frac{2^{nH(\alpha)}}{ \sqrt{\pi (1-\alpha)}} \text{ since } e^{1/12n} < \sqrt{2} \text{ for } n \geq 1 \\ &\leq & \frac{ 2^{nH(\alpha)} }{ \sqrt{\pi}} \text{ since } \alpha \leq 1/2\, . \end{array}$

### Proof of Proposition 3

First, note that $\alpha \leq \lfloor 1/2 -1/2n \rfloor$ implies $(1-2\alpha)n \geq 1$.

$\displaystyle \begin{array}{lcl} {(1-\alpha)n \choose \alpha n} &=& \frac{((1-\alpha)n)!}{(\alpha n)!\, \left( (1-2\alpha)n \right)! } \\ &\approx & \frac{\sqrt{2\pi (1-\alpha)n}(\frac{(1-\alpha)n}{e})^{(1-\alpha)n}}{2\pi n\sqrt{\alpha (1-2\alpha)}(\frac{\alpha n}{e})^{\alpha n}(\frac{(1-2\alpha)n}{e})^{(1-2\alpha)n} } \exp\left( \frac{1}{12(1-\alpha)n} - \frac{1}{12\alpha n + 1} - \frac{1}{12(1-2\alpha)n+1}\right) \\ &\leq& \sqrt{\frac{\frac{1-\alpha}{\alpha(1-2\alpha)}}{2 \pi n}}\, \left( \frac{(1-\alpha)^{1-\alpha}}{\alpha^\alpha (1-2\alpha)^{1-2\alpha}} \right)^n\, \exp\left(\frac{1}{12(1-\alpha)n}\right)\\ &\leq& \sqrt{\frac{\frac{1-\alpha}{\alpha(1-2\alpha)} }{\pi n}}\, 2^{(1-\alpha)n\,H\left( \frac{\alpha}{1-\alpha} \right)} \text{ since } e^{1/12(2-\alpha)n} < \sqrt{2} \\ &\leq& \frac{2^{(1-\alpha)n\,H\left( \frac{\alpha}{1-\alpha} \right)} }{ \sqrt{(1-2\alpha) n}}\, \text{ since } 1/\alpha -1 > \pi \\ &\leq& 2^{(1-\alpha)n\,H\left( \frac{\alpha}{1-\alpha} \right)} \text{ since } (1-2\alpha)n \geq 1\,. \end{array}$

We remark that the last approximation is rather loose.