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

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?

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