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?

  • 6
    $\begingroup$ The condition is not necessary. But it makes deriving $n(n-1)(n-2)\cdots(n-k+1)>n^k/2^k$ easy. $\endgroup$ – André Nicolas Mar 29 '12 at 14:42
  • 1
    $\begingroup$ ${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. $\endgroup$ – Mitch Mar 29 '12 at 14:57
  • 1
    $\begingroup$ @AndréNicolas What about $\binom{6}{6} = 1 < \frac{46656}{46080} = \frac{6^6}{2^6 6!}$? $\endgroup$ – dtldarek Mar 29 '12 at 15:24
  • 1
    $\begingroup$ @dtldarek: Certainly the inequality does not hold unconditionally. $\endgroup$ – André Nicolas Mar 29 '12 at 15:34
  • 1
    $\begingroup$ @AndréNicolas Yeah, you are right, I forgot that necessary has very precise meaning in mathematics. +1 for you :-) $\endgroup$ – 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!$.

  • $\begingroup$ How do you prove $\frac{n!}{(n-k)!} \geq \frac{(n-k)^n}{(n-k)^{n-k}}$? $\endgroup$ – jamaicanworm Mar 29 '12 at 15:54
  • 2
    $\begingroup$ Using the definition of n! and the simple inequality chain $n-k+i \ge n-k \ge n-k-i$ for $i \le k$. $\endgroup$ – 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)$:


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.


$\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!}$.


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.