2
$\begingroup$

How to prove that $(\frac{n}{k})^k\leq{{n}\choose{k}}\leq\frac{n^k}{k!}$?

I can only manage to see the second inequality, could any one give a hint about the first one?

$\endgroup$
8
$\begingroup$

$$\binom{n}{k} = \frac{n!}{k!(n - k)!} = \frac{n(n - 1)\cdots (n - k + 1)}{k (k - 1) \cdots 1} = \frac{n}{k}\frac{n - 1}{k - 1} \cdots \frac{n - (k - 1)}{1}\geq \frac{n}{k} \cdots \frac{n}{k} = \left(\frac{n}{k}\right)^k$$ where we used the inequality that for $i$ such that $1 \leq i \leq k - 1$, $$\frac{n - i}{k - i} \geq \frac{n}{k}$$ which is easy to verify.

$\endgroup$
2
$\begingroup$

Combinatorial Proof:

Denote by $[n]$ the set $\{1,2,\ldots,n\}$ and $\binom{[n]}{k}$ is the set of all subsets of $[n]$ with $k$ elements. Let $$A:=\Big\{\left(S,x_1,x_2,\ldots,x_k\right)\in \binom{[n]}{k}\times\mathbb{Z}^k\,\Big|\,x_i\in S\text{ for every }i\Big\}$$ and $$B:=\Big\{\left(x_1,x_2,\ldots,x_k\right)\in\mathbb{Z}^k\,\Big|\,1\leq x_i\leq n\text{ for every }i\Big\}\,.$$ The map $f:A\to B$ sending $\left(S,x_1,x_2,\ldots,x_k\right)\mapsto\left(x_1,x_2,\ldots,x_k\right)$ is a surjection. Thence, $|A|\geq |B|$. However, $|A|=\binom{n}{k}\cdot k^k$ and $|B|=n^k$. Hence, $\binom{n}{k}\cdot k^k \geq n^k$, or $\left(\frac{n}{k}\right)^k\leq\binom{n}{k}$.

Now, $\binom{n}{k}\cdot k!$ is the number of ways to arrange $k$ objects from a collection of $n$ distinct objects on a line without repetition. On the other hand, $n^k$ is the number of ways to arrange $k$ objects from a collection of $n$ distinct objects on a line where repetition is allowed. Clearly, $\binom{n}{k}\cdot k! \leq n^k$. Thus, $\binom{n}{k}\leq \frac{n^k}{k!}$.

$\endgroup$
0
$\begingroup$

It is easy to prove $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}$$ if we write it as $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}=\\ \frac{n(n-1)}{k(k-1)}\binom{n-2}{k-2}=\\\frac{n(n-1)(n-2)}{k(k-1)(k-2)}\binom{n-3}{k-3}=\\..\\\frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))}\binom{n-k}{k-k}=\\ \frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))}\binom{n-k}{0}\\=\frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))} $$so $$\frac{n}{k}\frac{n}{k}...\frac{n}{k}\leq \frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))}\leq\frac{n(n)(n)...(n)}{k(k-1)(k-2)...(k-(k-1)))}\\ \frac{n^k}{k^k}\leq \frac{n(n-1)(n-2)...(n-(k-1))}{k(k-1)(k-2)...(k-(k-1)))}\leq \frac{n^k}{k!} $$

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