# A cute combinatorial identity

Just wanted to record a cute combinatorial argument. Prove that $\sum\limits_{i=0}^n {n\choose i} {i\choose m}= {n\choose m} 2^{n-m}$

I read this formula in the article “Pascal functions” in “The American Mathematical Monthly”.

They prove it using the new machinery of Pascal functions that they develop in the article. I tried proving it using an algebraic argument, but couldn’t find the right formulation. I could finally prove it using a combinatorial argument, which I have explained below:

The left hand side counts the number of ways of first selecting $i$ items from $n$ items, and then selecting $m$ items from those already-selected $i$ items. Obviously, for $i, this does not make sense. Hence, ${i\choose m}=0$ in those cases. For $i\geq m$, the above interpretation is valid.

We can interpret the right hand side as the number of ways of selecting $m$ items from $n$ items, and then going to each of the left-over items (there are $n-m$ of them) and deciding if they had been pre-selected or not. Here pre-selection implies being selected amongst the $i$ items, out of which the final $m$ items have been chose.

Hence, the right hand side equals the left hand side.