I apologize if this is too elementary. The following identity arises in cluster algebra, where I'm trying to find an expression for cluster variables. Let $a,b$ be any nonnegative integers. Then there are nonnegative integers $d_0,...,d_{a+b}$ (depending on $a,b$, but not $X$) such that $$ {X\choose a} {X\choose b} = \sum_{i=0}^{a+b} d_i{X\choose i} $$for all large enough integers $X\gg 0$. I could prove this, but I'm pretty sure this must be well-known. I just want to get a reference. Or very short proofs (less than five lines) are welcome, too. Thank you.
2 Answers
$\begingroup$
$\endgroup$
2
$\binom{X}{a}\binom{X}{b}$ is the number of ways to choose a subset of size $a$ and a subset of size $b$ from a set of size $X$. The union of these two subsets is a subset of size anywhere from $\text{max}(a, b)$ to $a + b$, so $d_i$ is the number of different ways a subset of size $i$ can be realized as the union of a subset of size $a$ and a subset of size $b$. Whatever this number is it manifestly does not depend on $X$, and the conclusion follows.
-
2$\begingroup$ Which implies $d_i = \binom{i}{a}\binom{a}{b-i+a}$, I think. But the limits are not $\min(a,b)$ to $\max(a,b)$, they are $\max(a,b)$ to $a+b$. $\endgroup$ Commented May 10, 2012 at 0:32
-
$\begingroup$ @Brendan: ah yes, you're right. $\endgroup$ Commented May 10, 2012 at 0:54
$\begingroup$
$\endgroup$
1
Another very short proof: the left side is a polynomial in $X$ of degree $a+b$ that takes integer values when $X$ is an integer, so it can be expressed in the form of the right side.
The identity is equivalent to Vandermonde's theorem.
-
$\begingroup$ This doesn't prove that the $d_i$ are non-negative. $\endgroup$ Commented May 10, 2012 at 19:36