A cute combinatorial identity

by ayushkhaitan3437

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<m, 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.