2
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for hint Brian. I'll go ahead and play around with this and see where I get. $\endgroup$ – Shant Danielian Oct 1 '13 at 0:41
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 1 '13 at 0:43
  • $\begingroup$ +1 Is there a direct combinatorial argument? $\endgroup$ – Calvin Lin Oct 1 '13 at 0:47
  • $\begingroup$ @Calvin: I’ve not seen one yet, but I’ve not given up hope, either! $\endgroup$ – Brian M. Scott Oct 1 '13 at 0:47
  • $\begingroup$ @Calvin: I’ve now found a direct combinatorial argument; it’s surprisingly straightforward. $\endgroup$ – Brian M. Scott Oct 1 '13 at 1:07
3
$\begingroup$

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

$\endgroup$

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.