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!

  • $\begingroup$ What have you tried? $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.