8
$\begingroup$

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?

  • 1
    @AndréNicolas Yeah, you are right, I forgot that necessary has very precise meaning in mathematics. +1 for you :-)2012-03-29

3 Answers 3

2

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

6

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$

4

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

  • 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$.2012-03-29