q-Vandermonde identity

Short description: A q-analogue of the Chu–Vandermonde identity.

In mathematics, in the field of combinatorics, the q-Vandermonde identity is a q-analogue of the Chu–Vandermonde identity. Using standard notation for q-binomial coefficients, the identity states that

[math]\displaystyle{ \binom{m + n}{k}_{\!\!q} =\sum_{j} \binom{m}{k - j}_{\!\!q} \binom{n}{j}_{\!\!q} q^{j(m-k+j)}. }[/math]

The nonzero contributions to this sum come from values of j such that the q-binomial coefficients on the right side are nonzero, that is, max(0, k − m) ≤ j ≤ min(n, k).

Other conventions

As is typical for q-analogues, the q-Vandermonde identity can be rewritten in a number of ways. In the conventions common in applications to quantum groups, a different q-binomial coefficient is used. This q-binomial coefficient, which we denote here by [math]\displaystyle{ B_q(n,k) }[/math], is defined by

[math]\displaystyle{ B_q(n, k) = q^{-k(n-k)} \binom{n}{k}_{\!\!q^2}. }[/math]

In particular, it is the unique shift of the "usual" q-binomial coefficient by a power of q such that the result is symmetric in q and [math]\displaystyle{ q^{-1} }[/math]. Using this q-binomial coefficient, the q-Vandermonde identity can be written in the form

[math]\displaystyle{ B_q(m + n,k)=q^{n k}\sum_{j}q^{-(m+n)j} B_q(m,k - j) B_q(n,j). }[/math]

Proof

As with the (non-q) Chu–Vandermonde identity, there are several possible proofs of the q-Vandermonde identity. The following proof uses the q-binomial theorem.

One standard proof of the Chu–Vandermonde identity is to expand the product [math]\displaystyle{ (1 + x)^m (1 + x)^n }[/math] in two different ways. Following Stanley, we can tweak this proof to prove the q-Vandermonde identity, as well. First, observe that the product

[math]\displaystyle{ (1 + x)(1 + qx) \cdots \left (1 + q^{m + n - 1}x \right ) }[/math]

can be expanded by the q-binomial theorem as

[math]\displaystyle{ (1 + x)(1 + qx) \cdots \left (1 + q^{m + n - 1}x \right ) = \sum_k q^{\frac{k(k-1)}{2}} \binom{m + n}{k}_{\!\!q} x^k. }[/math]

Less obviously, we can write

[math]\displaystyle{ (1 + x)(1 + qx) \cdots \left (1 + q^{m + n - 1}x \right ) = \left((1 + x)\cdots (1 + q^{m - 1}x)\right) \left( \left(1 + (q^m x) \right) \left (1 + q(q^m x) \right ) \cdots \left (1 + q^{n - 1}(q^m x) \right )\right) }[/math]

and we may expand both subproducts separately using the q-binomial theorem. This yields

[math]\displaystyle{ (1 + x)(1 + qx) \cdots \left (1 + q^{m + n - 1}x \right ) = \left(\sum_i q^{\frac{i(i - 1)}{2}} \binom{m}{i}_{\!\!q} x^i \right) \cdot \left(\sum_i q^{mi + \frac{i(i - 1)}{2}} \binom{n}{i}_{\!\!q} x^i \right). }[/math]

Multiplying this latter product out and combining like terms gives

[math]\displaystyle{ \sum_k \sum_j \left(q^{j(m - k + j) + \frac{k(k - 1)}{2}} \binom{m}{k - j}_{\!\!q} \binom{n}{j}_{\!\!q}\right)x^k. }[/math]

Finally, equating powers of [math]\displaystyle{ x }[/math] between the two expressions yields the desired result.

This argument may also be phrased in terms of expanding the product [math]\displaystyle{ (A + B)^m(A + B)^n }[/math] in two different ways, where A and B are operators (for example, a pair of matrices) that "q-commute," that is, that satisfy BA = qAB.

References

• Richard P. Stanley (2011). Enumerative Combinatorics, Volume 1 (2 ed.). http://www-math.mit.edu/~rstan/ec/ec1.pdf. Retrieved August 2, 2011. 

• Exton, H. (1983), q-Hypergeometric Functions and Applications, New York: Halstead Press, Chichester: Ellis Horwood, 1983, ISBN 0853124914, ISBN 0470274530, ISBN 978-0470274538
• Gaurav Bhatnagar (2011). "In Praise of an Elementary Identity of Euler". Electronic Journal of Combinatorics 18 (2): 13. 
• Victor J. W. Guo (2008). "Bijective Proofs of Gould's and Rothe's Identities". Discrete Mathematics 308 (9): 1756. doi:10.1016/j.disc.2007.04.020. 
• Sylvie Corteel; Carla Savage (2003). "Lecture Hall Theorems, q-series and Truncated Objects". arXiv:math/0309108.