Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
6  
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
1  
${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
1  
@AndréNicolas What about $\binom{6}{6} = 1 < \frac{46656}{46080} = \frac{6^6}{2^6 6!}$? –  dtldarek Mar 29 '12 at 15:24
1  
@dtldarek: Certainly the inequality does not hold unconditionally. –  André Nicolas Mar 29 '12 at 15:34
1  
@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

3 Answers 3

up vote 3 down vote accepted

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

share|improve this answer
    
How do you prove $\frac{n!}{(n-k)!} \geq \frac{(n-k)^n}{(n-k)^{n-k}}$? –  jamaicanworm Mar 29 '12 at 15:54
2  
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}$plot

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$

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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