Show that $\binom{n}{k} \frac{1}{n^k}\leqslant \frac{1}{k!}$ holds true for $n\in \mathbb{N}$ and $k=0,1,2, \ldots, n$ $$\binom{n}{k} \frac{1}{n^k}\leqslant \frac{1}{k!}$$
How would I prove this? I tried with induction, with $n$ as a variable and $k$ changing, but then I can't prove for $k+1$, can I? 
Is there a better method than using induction (if induction even works)?
 A: We have
$$ \frac{k!}{n^k}\binom{n}{k} = \frac{k!}{n^k} \frac{n(n-1)\dotsm(n-k+1)}{k!} \\
= 1 \left( \frac{n-1}{n} \right) \left( \frac{n-2}{n} \right) \dotsm \left( \frac{n-k+1}{n} \right) \\
= \left(1- \frac{1}{n} \right) \left(1- \frac{2}{n} \right) \dotsm \left( 1-\frac{k-1}{n} \right),  $$
and every term in this product is strictly between $0$ and $1$, so the entire (finite) product is also positive and less than $1$.
A: The simplest way I see is the following:
$$\binom{n}{k}\frac{1}{n^k} = \frac{\overbrace{n(n-1)\dots(n-k+1)}^{\text{$k$ positive terms, each no larger than $n$} }}{k!} \frac{1}{n^k} \le \frac{1^k}{k!}$$
A: HINT:
Write out the expression 
$$\begin{align}
\binom{n}{k}\frac{1}{n^k}&=\frac{n(n-1)(n-2)\cdots (n-k-2)(n-k-1)}{k!n^k}\\\\
&=\frac{1}{k!}\left(1-\frac{1}{n}\right)\left(1-\frac{2}{n}\right)\cdots\left(1-\frac{k-2}{n}\right)\left(1-\frac{k-1}{n}\right)
\end{align}$$
A: $$\frac{n!}{(n-k)!}=\underbrace{(n-k+1)}_{\leq n}...\underbrace{(n-1)}_{\leq n}\underbrace{n}_{\leq n}\leq n^{k}\implies \binom{n}{k}\frac{1}{n^k}= \frac{n!}{(n-k)!k!}\frac{1}{n^k}\leq \frac{1}{k!}$$
A: Consider $k$-tuples of elements from a set with $n$ elements.
How many are there tuples $(a_1, a_2, \dots, a_k)$ consisting of pairwise different elements? Choose the set $\{a_1, a_2, \dots, a_k\}$ (there are ${n \choose k}$ options) and then order it ($k!$ options), therefore there are ${n \choose k} k!$ such tuples.
How many are there tuples $(a_1, a_2, \dots, a_k)$? $n^k$. 
Therefore ${n \choose k} k! \leq n^k $.
