Question

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.

Answer 1

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

Answer 2

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.