Show that $\frac{n!}{k!(n-k)!}\frac{1}{n^k}\leq\frac{1}{2^{k-1}}$. 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}}.$
 A: 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$.

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