# Bounding ${n \choose k}$

Let $k > 0$, and $n > 2k$. Why is it necessarily true that $${n \choose k} > \frac{n^k}{2^k k!}$$ And is the condition $n > 2k$ necessary for this inequality to hold?

-
The condition is not necessary. But it makes deriving $n(n-1)(n-2)\cdots(n-k+1)>n^k/2^k$ easy. –  André Nicolas Mar 29 '12 at 14:42
${n \choose k}$ increases up to $k = \lfloor n/2 \rfloor$, then goes down. So you only really need to worry about the left side up to the max. –  Mitch Mar 29 '12 at 14:57
@AndréNicolas What about $\binom{6}{6} = 1 < \frac{46656}{46080} = \frac{6^6}{2^6 6!}$? –  dtldarek Mar 29 '12 at 15:24
@dtldarek: Certainly the inequality does not hold unconditionally. –  André Nicolas Mar 29 '12 at 15:34
@AndréNicolas Yeah, you are right, I forgot that necessary has very precise meaning in mathematics. +1 for you :-) –  dtldarek Mar 29 '12 at 15:50

We have $$\binom{n}{k} = \frac{n!}{(n-k)!k!} \ge \frac{(n-k)^n}{(n-k)^{n-k}k!} \ge \frac{(n-k)^k}{k!} \ge \frac{(n/2)^k}{k!}$$ using $n > 2k \implies n-k \ge n/2$. In the more general case, as noted in the comments, you will need a more detailed analysis, e.g., using Stirling's approximation for $n!$.

-
How do you prove $\frac{n!}{(n-k)!} \geq \frac{(n-k)^n}{(n-k)^{n-k}}$? –  jamaicanworm Mar 29 '12 at 15:54
Using the definition of n! and the simple inequality chain $n-k+i \ge n-k \ge n-k-i$ for $i \le k$. –  Johannes Kloos Mar 29 '12 at 16:45

If $k\le\frac12n$, then $n-k+1>\frac12n$. Therefore, \begin{align} \binom{n}{k} &=\frac{n(n-1)(n-2)\dots(n-k+1)}{k!}\\ &>\frac{(n/2)^k}{k!}\\ &=\frac{n^k}{2^kk!}\tag{1} \end{align} However, the condition that $k<\frac12n$ can be extended to $k\le\frac34n$ by noting that for $0\le j\le k-1$, $(n-j)\color{red}{(n+j-k+1)}\ge n\color{red}{(n-k+1)}>n^2/4$. \begin{align} \binom{n}{k}^2 &=\frac{n\color{red}{(n-k+1)}(n-1)\color{red}{(n-k+2)}(n-2)\dots(n-k+1)\color{red}{n}}{k!^2}\\ &>\frac{(n^2/4)^k}{k!^2}\tag{2} \end{align} Taking the square root of $(2)$ yields $$\binom{n}{k}>\frac{n^k}{2^kk!}\tag{3}$$ Take It To The Limit:

Above, it is shown that the condition $k<\frac12n$ in the question can be extended to $k\le\frac34n$. One might ask how far this might be pushed. That is, what is the largest $\alpha$ so that $k<\alpha n$ implies $(3)$.

Multiplying $(3)$ by $k!$ and taking the $\log$ of both sides yields $$\sum_{j=0}^{k-1}\log(n-j)>k\log(n)-k\log(2)\tag{4}$$ Noting that $$\sum_{j=0}^{k-1}\log(n-j)\ge\int_{n-k}^n\log(x)\,\mathrm{d}x\tag{5}$$ We get that $$\int_{n-k}^n\log(x)\,\mathrm{d}x>k\log(n)-k\log(2)\tag{7}$$ implies $(3)$. Computing the integral in $(7)$ yields $$n\log(n)-n-(n-k)\log(n-k)+(n-k)>k\log(n)-k\log(2)\tag{8}$$ Subtracting $k\log(n)-k$ from both sides and dividing by $k$ yields $$\frac{n-k}{k}\log\left(\frac{n}{n-k}\right)>1-\log(2)\tag{9}$$ Substituting $\alpha=k/n$ yields $$\frac{1-\alpha}{\alpha}\log\left(\frac{1}{1-\alpha}\right)>1-\log(2)\tag{10}$$ Here is a plot of $\frac{1-\alpha}{\alpha}\log\left(\frac{1}{1-\alpha}\right)$ and $1-\log(2)$:

$\hspace{4cm}$

We can solve $\frac{1-\alpha}{\alpha}\log\left(\frac{1}{1-\alpha}\right)=\beta$ using the Lambert W function: \begin{align} \frac{1-\alpha}{\alpha}\log\left(\frac{1}{1-\alpha}\right)&=\beta\tag{11}\\ (1-\alpha)^{1-\alpha}e^\beta&=e^{(1-\alpha)\beta}\tag{12}\\ (1-\alpha)e^{\beta/(1-\alpha)}&=e^\beta\tag{13}\\ -\beta/(1-\alpha)e^{-\beta/(1-\alpha)}&=-\beta e^{-\beta}\tag{14}\\ -\frac{\beta}{1-\alpha}&=W\left(-\beta e^{-\beta}\right)\tag{15}\\ \alpha&=1+\frac{\beta}{W\left(-\beta e^{-\beta}\right)}\tag{16} \end{align} $(12)$: multiply by $-\alpha$, exponentiate, multiply by $e^\beta$

$(13)$: raise to the $1/(1-\alpha)$ power

$(14)$: take reciprocals, multiply by $-\beta$

$(15)$: apply $W$

$(16)$: algebraically solve for $\alpha$

Plugging $\beta=1-\log(2)$ into $(16)$ gives \begin{align} \alpha &=1+\frac{1-\log(2)}{W\left(-\frac2e(1-\log(2))\right)}\\ &\approx 0.868708579475419252 \end{align} Thus, if $k<\alpha n$, $(3)$ holds.

Example:

$\left.\binom{10000}{8687}\middle/\frac{1000^{8687}}{2^{8687}8687!}\right.=3.095040785$, but $\left.\binom{10000}{8688}\middle/\frac{1000^{8688}}{2^{8688}8688!}\right.=0.8127577101$

-

We have \begin{align*} \binom{n}{k} &> \frac{n^k}{2^k k!} \\ \frac{n!}{(n-k)!k!} &> \frac{n^k}{2^k k!} \\ \frac{n!}{(n-k)!} &> \frac{n^k}{2^k} \\ \prod_{i=n-k+1}^n i &> \left(\frac{n}{2}\right)^k \\ (n-k+1)^k &> \left(\frac{n}{2}\right)^k \\ n-k+1 &> \frac{n}{2} \\ n-2k+2 &> 0 \\ n+2 &> 2k \\ \end{align*}

Edit: $n > 2k$ is not a necessary condition (e.g. $n \geq 2k$ is good as well), but you need something, in general case the inequality does not hold, for example for $n \geq 6$ we have $\binom{n}{n} = 1 \leq \frac{n^n}{2^n n!}$.

-