# Show that $\frac{n!}{k!(n-k)!}\frac{1}{n^k}\leq\frac{1}{2^{k-1}}$.

I'm working on the problem given in the problem statement. Note that $0\leq k\leq n$ for $n\in\mathbb{N}$. I'm stuck trying to figure out where to even begin to show this inequality. I've done some searches and came across an upper bound for $n\choose k$ as $\frac{n^k}{k!}$, but I couldn't find a proof of that exactly. I also realized that the number of even and odd permutations is $2^{k-1}$, but I'm unsure if that even comes into play.

Note that this is a homework problem given in my Real Analysis class, so please only provide me with a hint and not necessarily the entire proof.

Thanks for any help!

EDIT:

I was able to prove the problem directly. The proof is as follows,

Consider \begin{align} \frac{n!}{k!(n-k)!}\frac{1}{n^k}&=\frac{n(n-1)\cdots(n-k+1)(n-k)!}{k!(n-k)!}\frac{1}{n^k} \nonumber \\ &=\frac{n(n-1)\cdots(n-k+1)}{k!}\frac{1}{n^k}\nonumber \\ &\leq\frac{n^k}{k!}\frac{1}{n^k}\nonumber \\ &=\frac{1}{k!}\nonumber \\ &\leq\frac{1}{2^{k-1}} \nonumber. \end{align} Thus, $\displaystyle\binom{n}{k}\frac{1}{n^k}\leq\frac{1}{2^{k-1}}.$

The inequality is equivalent to

$$\binom{n}k\le\frac{n^k}{2^{k-1}}\;,$$

which you can prove by induction on $n$ using the identity $$\binom{n+1}k=\binom{n}{k-1}+\binom{n}k\;.$$

You have

\begin{align*} \binom{n+1}k&=\binom{n}{k-1}+\binom{n}k\\ &\le\frac{n^{k-1}}{2^{k-2}}+\frac{n^k}{2^{k-1}}\;, \end{align*}

to get you started.

Added: I found a combinatorial argument. For now I’ll leave it spoiler-protected.

We want to show that $2^{k-1}\binom{n}k\le n^k$. $2^{k-1}\binom{n}k$ is the number of ways to pick $k$ elements from the set $\{1,2,\ldots,n\}$ and partition them into two subsets, one of which may be empty. (There are $2^{k-1}$ ways to decide which of the other $k-1$ elements are to go in the same part with the largest element of the subset.) Let $K$ be a $k$-element subset of $\{1,\ldots,n\}$, and suppose that $K=A\cup B$, where $A\cap B=\varnothing$ and $\max K\in B$. Construct a $k$-tuple $\sigma(K)$ of elements of $\{0,\ldots,1\{$ by listing the members of $A$ in descending order followed by the members of $B$ in descending order. Observe that not only $K$, but also $A$ and $B$ can be reconstructed from this permutation of $K$. Thus, the map $K\mapsto\sigma(K)$ is an injection, and $2^{k-1}\binom{n}k\le n^k$.

• Thanks for hint Brian. I'll go ahead and play around with this and see where I get. – Shant Danielian Oct 1 '13 at 0:41
• @Shant: You’re welcome; if you simplify that last expression, I don’t think that you’ll have too much trouble getting what you need to make the induction step work. – Brian M. Scott Oct 1 '13 at 0:43
• +1 Is there a direct combinatorial argument? – Calvin Lin Oct 1 '13 at 0:47
• @Calvin: I’ve not seen one yet, but I’ve not given up hope, either! – Brian M. Scott Oct 1 '13 at 0:47
• @Calvin: I’ve now found a direct combinatorial argument; it’s surprisingly straightforward. – Brian M. Scott Oct 1 '13 at 1:07

$$\binom{n}{k}=\frac{(n-k+1)(n-k+2)..n}{1 \cdot 2 \cdot ... \cdot k}=\frac{(n-k+1)(n-k+2)..n}{2 \cdot 3 \cdot ... \cdot k}\leq \frac{n \cdot n \cdot ....\cdot n}{2 \cdot 2 \cdot ... \cdot 2}=\frac{n^k}{2^{k-1}}$$