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

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s