q-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

${(\genfrac{}{}{0ex}{}{m+n}{k})}_q=\sum _j{(\genfrac{}{}{0ex}{}{m}{k-j})}_q{(\genfrac{}{}{0ex}{}{n}{j})}_q{q}^{j(m-k+j)}.$

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 $B_q(n,k)$, is defined by

$B_q(n,k)=q^{-k(n-k)}{(\genfrac{}{}{0ex}{}{n}{k})}_{q^2}.$

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 $q^{-1}$. Using this q-binomial coefficient, the q-Vandermonde identity can be written in the form

$B_q(m+n,k)=q^{nk}\sum _j{q}^{-(m+n)j}{B}_q(m,k-j)B_q(n,j).$

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 $(1+x{)}^m(1+x{)}^n$ in two different ways. Following Stanley, we can tweak this proof to prove the q-Vandermonde identity, as well. First, observe that the product

$(1+x)(1+qx)\cdots (1+q^{m+n-1}x)$

can be expanded by the q-binomial theorem as

$(1+x)(1+qx)\cdots (1+q^{m+n-1}x)=\sum _k{q}^{\frac{k(k-1)}{2}}{(\genfrac{}{}{0ex}{}{m+n}{k})}_q{x}^k.$

Less obviously, we can write

$(1+x)(1+qx)\cdots (1+q^{m+n-1}x)=((1+x)\cdots (1+q^{m-1}x))((1+(q^{m}x))(1+q(q^{m}x))\cdots (1+q^{n-1}(q^{m}x)))$

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

$(1+x)(1+qx)\cdots (1+q^{m+n-1}x)=\left(\sum _i{q}^{\frac{i(i-1)}{2}}{(\genfrac{}{}{0ex}{}{m}{i})}_q{x}^i\right)\cdot \left(\sum _i{q}^{mi+\frac{i(i-1)}{2}}{(\genfrac{}{}{0ex}{}{n}{i})}_q{x}^i\right).$

Multiplying this latter product out and combining like terms gives

$\sum _k\sum _j\left(q^{j(m-k+j)+\frac{k(k-1)}{2}}{(\genfrac{}{}{0ex}{}{m}{k-j})}_q{(\genfrac{}{}{0ex}{}{n}{j})}_q\right)x^k.$

Finally, equating powers of $x$ between the two expressions yields the desired result. This argument may also be phrased in terms of expanding the product $(A+B{)}^m(A+B{)}^n$ 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 (PDF) (2 ed.). 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. arXiv:1102.0659.
• Victor J. W. Guo (2008). "Bijective Proofs of Gould's and Rothe's Identities". Discrete Mathematics. 308 (9): 1756–1759. arXiv:1005.4256. doi:10.1016/j.disc.2007.04.020.
• Sylvie Corteel; Carla Savage (2003). "Lecture Hall Theorems, q-series and Truncated Objects". arXiv:math/0309108.