How to prove $ \sum_{k=3}^n \binom nk \binom k3 =\binom n3 2^{n-3} $

Question

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

Answer 1

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*}

Answer 2

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}$$

Answer 3

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?

Answer 4

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.

Answer 5

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$.