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

Published by -

Graduate student

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: