A cute combinatorial identity
Just wanted to record a cute combinatorial argument. Prove that
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 items from items, and then selecting items from those already-selected items. Obviously, for , this does not make sense. Hence, in those cases. For , the above interpretation is valid.
We can interpret the right hand side as the number of ways of selecting items from items, and then going to each of the left-over items (there are of them) and deciding if they had been pre-selected or not. Here pre-selection implies being selected amongst the items, out of which the final items have been chose.
Hence, the right hand side equals the left hand side.