# Proving q-binomial identities

I was wondering if anyone could show me how to prove q-binomial identities? I do not have a single example in my notes, and I can't seem to find any online.

For example, consider: ${a + 1 + b \brack b}_q = \sum\limits_{j=0}^{b} q^{(a+1)(b-j)}{a+j \brack j}_q$

I haven't made much progress on this one, but here's one that I have managed to get something out of: ${2n \brack n}_q = \sum\limits_{k=0}^{n} q^{k^{2}}{n \brack k}_q$

Using the q-binomial theorem from my notes, which is as follows: $(1+qx)(1+q^{2}x)...(1+q^{n}x) = \sum\limits_{k=0}^{n} q^{k(k+1)/2}{n \brack k}_q x^{k}$, I have managed to show that the coefficient of $x^{n}$ is equal to: $\sum\limits_{k=0}^{n} q^{(2k^{2} - 2nk + n^{2} + n)/2} {n \brack k}_q {n \brack n-k}_q$, which is when I was working on the right hand side of the identity. In order to get here, I considered the product of $(1+qx)...(1+q^{n}x)(1+qx)...(1+q^{n}x)$, then tried obtaining the coefficient of $x^n$, as one would in the ordinary binomial proof. I've been trying to mimic the proofs of the regular binomial counterparts of these identities but without much luck.

Help would be appreciated, as I have a midterm exam coming up soon. Thanks :)

-
I don’t suppose that by any chance you read German? If you do, take a look at this and at these more extensive notes. –  Brian M. Scott Oct 15 '12 at 5:12
No I don't sadly =( - Just English & French. –  Nizbel99 Oct 15 '12 at 5:14
This is a shame, because the references you've given me look like just what I would need if they were in English. I can't seem to find anything comprehensive like this in English either. –  Nizbel99 Oct 15 '12 at 5:25
You can find a few ideas in answers to this question, this question, and this question. (I’ve not yet had time to look at your actual question.) –  Brian M. Scott Oct 15 '12 at 5:35
Thank you =) - I am taking a look now, although these look a lot more complex than what we've seen in class. I will continue to try and work through this problems as well, in the mean time :) –  Nizbel99 Oct 15 '12 at 5:39

You can prove

$${a + 1 + b \brack b}_q = \sum\limits_{j=0}^{b} q^{(a+1)(b-j)}{a+j \brack j}_q\tag{1}$$ by induction on $b$. Assume $(1)$. Then

\begin{align*} \sum\limits_{j=0}^{b+1} q^{(a+1)(b+1-j)}{a+j \brack j}_q&={a+b+1\brack b+1}_q+\sum\limits_{j=0}^{b} q^{(a+1)(b+1-j)}{a+j \brack j}_q\\ &={a+b+1\brack b+1}_q+q^{a+1}\sum_{j=0}^bq^{(a+1)(b-j)}{a+j\brack j}_q\\ &={a + 1 + b \brack b+1}_q+q^{a+1}{a+1+b\brack b}_q\\ &={a+2+b\brack b+1}_q \end{align*}

by the fundamental recurrence $${n+1\brack k}_q={n\brack k}_q+q^{n-k+1}{n\brack k-1}_q\;.$$ It’s worth mentioning the other fundamental Pascal-like recurrence: $${n+1\brack k}_q=q^k{n\brack k}_q+{n\brack k-1}_q\;.$$

I also found these slides of a talk that I think you might find very useful.

-
The slides look very helpful :) Thank you! –  Nizbel99 Oct 15 '12 at 13:04
@user43552: You’re welcome! (I also found them very helpful.) –  Brian M. Scott Oct 15 '12 at 13:05

$\newcommand\gauss[2]{\genfrac[]0{}{#1}{#2}_q}$Here's a straightforward implementation of the method I gave in a hint. The natural combinatorial interpretation of a Gaussian binomial coefficient $\gauss {a+b}b$ is that it counts the lattice paths from the origin to $(a,b)$ (where each step advances one of the two coordinates) with as weight the number of squares above the path, within the rectangle with the origin and $(a,b)$ as diagonally opposite corners. Counting with weight means summing over the indicated set the monomials $q^k$, where $k$ is the weight of the element. (I'm using Cartesian coordinates to tell which side is "above" the path.)

Now $\sum_{j=0}^b\binom{a+j}j$ counts the paths from the origin to one of the points $(a,j)$ for $0\leq j\leq b$, while $\binom{a+1+b}b$ counts the paths from the origin to $(a+1,b)$. Now it is not hard to see why $$\binom{a+1+b}b = \sum_{j=0}^b\binom{a+j}j,$$ as every path from the origin to $(a+1,b)$ there is a unique $j$ for which it contains a step $(a,j)\to(a+1,j)$, and once this $j$ is known, the path is entirely determined by the way it passes from the origin to $(a,j)$, because after arriving at $(a+1,j)$ it has no choice but to go straight up.

Now the Gaussian binomial coefficient $\gauss{a+1+b}b$ on the left tells us we want to attach as weight to such paths the number of squares above it, within the rectangle with sides $a+1$ and $b$. On the right the coefficient $\gauss{a+j}j$ counts the squares above the path within the recatangle with sides $a$ and $j$, and since the path makes a horizontal step $(a,j)\to(a+1,j)$, this number is equal to the number of squares above the (extended) path within the rectangle with sides $a+1$ and $j$. But then the path goes straight up for $b-j$ steps, each of which has $a+1$ squares to its left which are also above the path, and within the rectangle with sides $a+1$ and $b$. So we must multiply the terms coming from $j$ by $q^{(a+1)(b-j)}$ to account for the extra squares counted on the left, and this is exactly what your $q$-formula says.

-
Thank you :) - I didn't know about the combinatorial interpretation. It's actually quite helpful for a handful of these identities as well! –  Nizbel99 Oct 15 '12 at 13:05
I might have added, the combinatorial interpretation is often stated in terms of Young diagrams: the part of a $a\times b$ rectangle above a path from its bottom-left to top right corner is a Young diagram with at most $a$ columns and at most $b$ rows, and its size (number of squares) gives the associated weight. See for instance Stanley, Enumerative Combinatorics 1, 1.3.19. –  Marc van Leeuwen Oct 15 '12 at 14:01
+1. If you draw the picture this is a very elegant solution. –  dx7hymcxnpq Oct 19 '12 at 7:23

Your identity follows from this version of Pascal's rule:

$${n \brack k}_q = {n-1 \brack k}_q + q^{n-k} {n-1 \brack k-1}_q.$$

Expanding gives

\begin{align} {a + b + 1 \brack b}_q &= {a+b \brack b}_q + q^{a+1} {a+b \brack b-1}_q \\ &= {a+b \brack b}_q + q^{a+1} \left( {a+b-1 \brack b-1}_q + q^{a+1} {a+b-1 \brack b-2}_q \right) \\ &= \cdots \\ &= \sum_{j=0}^b q^{(b-j)(a+1)} {a+j \brack j}_q. \end{align}

You could of course turn this into a proper proof by induction.

-

You can use the $q$-Vandermonde identity to expand the left hand side of your equation

$$\binom{m + n}{k}_{\!\!q} = \sum_{j} \binom{m}{k - j}_{\!\!q} \binom{n}{j}_{\!\!q} q^{j(m-k+j)}\,,$$

$$\max(0, k - m) \le j \le \min(n, k).$$

-