# Combinatoric proof that $\sum_{k=0}^m \binom{m}{k}\binom{n+k}{m} = \sum_{k=0}^m \binom{n}{k}\binom{m}{m-k}2^k$

Proof that:

$$\sum_{k=0}^m \binom{m}{k}\binom{n+k}{m} = \sum_{k=0}^m \binom{n}{k}\binom{m}{m-k}2^k$$ for $$k,m,n \in \mathbb{N}$$.

Can someone help me understand this equality by giving a combinatoric argument?

I believe that the RHS means "all possible ways to first select $$k$$ elements from $$m$$ elements and thereafter, selecting $$m$$ elements out of $$n+k$$ elements". Same for the LHS. The factor $$2^k$$ probably has to do something with having to pick between two possible options for $$k$$ elements.

I can't really find a good scenario to prove the equation. I tried with a group of $$m$$ kids, with $$n$$ boys and $$k$$ girls. But that did not really work out.

Thanks for helping!

• What have you tried? – Phicar Jan 22 at 2:52

Well suppose you have $$m$$ boys and $$n$$ girls and you want to pick a team of $$m$$ people. Assume, further, that the way to select them is as follows, you first pick $$k$$ man in a preliminary round $$\binom{m}{k}$$ and in a secondary round out of the chosen man and all the woman you pick your team of $$m$$ i.e., $$\binom{n+k}{m}.$$ Now, assume you pick directly the man and the women of the team, so they have to add up to $$m$$ so $$\binom{n}{k}\binom{m}{m-k}$$ but you have to pay the men who pass the preliminary round in the LHS, and so you can choose any subset of the man who were not selected ($$k$$ of them) in $$2^k$$ ways.