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!
Answer
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}$.
No comments:
Post a Comment