Prove $\Sigma_{j}\binom{n}{j,k,n-j-k} = 2^{n-k}\binom{n}{k}$

Question

Prove $\Sigma_{j}\binom{n}{j,k,n-j-k} = 2^{n-k}\binom{n}{k}$.

The only relevant formula that I think I can apply here is:

$\Sigma_{k_1 + ... + k_m}\binom{n}{k_1,...,k_m} = m^n$

However, I'm not really sure how to approach this problem. I think there should be a way to simplify the left side of the equation, but the above formula doesn't really apply to this. Is there another formula that I should be using to simplify it?

Answer 1

There is a neat combinatorial argument if you are up to it. Think of $\binom{n}{j,k,n-j-k}$ as the number of sequences made up of three symbols.

There are $j$ symbols "type 1", k of "type 2" and n-j-k of "type 3".

Now the sum $\Sigma_{j}\binom{n}{j,k,n-j-k}$ is the total number of such sequences where the number of symbols of type 2 can be any number between $0$ and $n-k$. And that is precisely $2^{n-k}\binom{n}{k}$.