title: Q-Vandermonde identity
text: # 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
  
      ${\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, 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)}{\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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): 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 \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.
  
  