4
$\begingroup$

I came across the following identity while computing certain expressions: $$\sum_{i=0}^m \binom{l}{i}\binom{m+n-l}{m-i} = \binom{m+n}{m}.$$ Here, $m,n,l \geq 0$ are fixed and $l \leq m+n$. Also assume that $\binom{x}{y} = 0$ whenever $x < y$.

I verified this identity for small values of $m$, $n$ and $l$, and I think I have come up with a combinatorial argument for why this identity is true. Can someone please verify it for me?

Proof.

The RHS is the number of ways of choosing $m$ objects out of a collection of $m+n$ distinct objects.

We can make this selection in the following way as well. Divide the collection into two distinct bunches of $l$ objects and $m+n-l$ objects. We can select $m$ objects out of our $m+n$ objects by selecting $i$ objects from the $l$-bunch and the remaining $m-i$ from the $(m+n-l)$-bunch, for each possible value of $i$ between $0$ and $m$ (in the sense that we don't try to select more than $l$ objects out of our first bunch, or more than $m+n-l$ objects out of our second bunch). But, this is nothing but the expression on the LHS.

Is my proof valid? I would be grateful if someone can provide alternative proofs of this identity as well. Thanks in advance!

$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

Your combinatorial argument looks good. Another way is to think about it algebraically.

The essence of your identity is $(x+1)^{m+n} = (x+1)^l (x+1)^{m+n-l}$.

For polynomials (or formal power series) $F = \sum_i f_i x^i$, $G = \sum_j g_j x^j$ the $m$th coefficient operator $[x^m]$ acts on products by convolution, i.e. $[x^m](FG) = \sum_{i=0}^m F_iG_{m-i}$

The RHS of your identity is the coefficient of $x^m$ in $(x+1)^{m+n}$, which of course matches the coefficient of $x^m$ in $(x+1)^l (x+1)^{m+n-l}$.

$\endgroup$
0

You must log in to answer this question.