q-Vandermonde identity

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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

\binom{m + n}{k}_{\!\!q} =\sum_{j} \binom{m}{k - j}_{\!\!q} \binom{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, km) ≤ j ≤ min(n, k).

Other conventions[edit]

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)} \binom{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^{n k}\sum_{j}q^{-(m+n)j} B_q(m,k - j) B_q(n,j).

Proofs of the identity[edit]

As with the (non-q) Chu-Vandermonde identity, there are several possible proofs of the q-Vandermonde identity. We give one proof here, using 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,[1] we can tweak this proof to prove the q-Vandermonde identity, as well. First, observe that the product

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

can be expanded by the q-binomial theorem as

(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.

Less obviously, we can write

(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)

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

(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).

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}} \binom{m}{k - j}_{\!\!q} \binom{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.


Proof by counting subspaces[edit]

Notes[edit]

  1. ^ Stanley (2011), Solution to exercise 1.100, p. 188.

References[edit]

  • Gaurav Bhatnagar (2011). "In Praise of an Elementary Identity of Euler". Electronic J. Combinatorics, P13, 44pp. 18 (2). arXiv:1102.0659.