<s>[INST] 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?
 [/INST] 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!} $$
</s>