How to prove $ \sum_{k=3}^n \binom nk \binom k3 =\binom n3 2^{n-3} $ How to prove this?
$$
\sum_{k=3}^n \binom nk \binom k3 = \binom n3 2^{n-3}
$$
It seems that some terms in the binomial coefficients cancel out:
$$\binom nk \binom k3  = \frac{n!}{k!(n-k)!} \cdot \frac{k!}{(k-3)!3!} = \frac{n!}{(n-k)!(k-3)!3!}.$$
But it's not clear whether this can be simplified further.
Thank you
 A: Hint:Note 
$$\binom{k}{3}\binom{n}{k}=\dfrac{k(k-1)(k-2)}{6}\binom{n}{k}=\dfrac{n(n-1)(n-2)}{6}\binom{n-3}{k-3}$$
A: Try to evaluate these expressions combinatorially. The left side counts the number of ways to choose some $k$ number of objects from $n$ objects, and then choosing $3$ from that $k$, for any $k$ such that $3\leq k\leq n$. That's the harder side the evaluate- can you see how the right side counts the same thing?
A: The cross product of binomial coefficients
\begin{align*}
\binom{n}{k}\binom{k}{j}=\binom{n}{j}\binom{n-j}{k-j}
\end{align*}
indicates a slight generalisation.

We obtain
  \begin{align*}
\sum_{k=j}^n\binom{n}{k}\binom{k}{j}&=\sum_{k=j}^n\binom{n}{j}\binom{n-j}{k-j}\\
&=\binom{n}{j}\sum_{k=0}^{n-j}\binom{n-j}{k}\\
&=\binom{n}{j}2^{n-j}
\end{align*}

A: How many $n$-digit strings are there in ternary (using only the numbers $0$, $1$, and $2$) that use exactly three $0$'s?  Each term in the sum on the left picks out $k$ digits that are less than $2$ and then, among these $k$, the $3$ digits that are $0$.  The right hand side picks out the $3$ digits that are $0$ and then, among the remaining $n-3$ digits, lets each one be either a $1$ or a $2$.
A: From the left side extract $n!$ and $3!$ You are then left with
$\sum_{k=3}^{n} \frac{1}{(n-k)! (k-3)!}$
You can then replace $k$ by $n-k$ in the above summation to arrive at
$ \sum_{k=n-3}^{0} \frac{1}{(n-k-3)! k!}$.
The summand looks now like an $n-3$ choose something which we engineer as
$ \frac{1}{(n-3)!}\sum_{k=0}^{n-3} \frac{(n-3)!}{(n-3-k)! k!}$.
which is $ \frac{1}{(n-3)!} 2^{n-3}$.
Now replace the  $n!$ and $3!$ you took out earlier.
