8
$\begingroup$

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

  • 0
    I'm not at all expert at $q$-identities, but a basic yet useful approach seems to be to take a proof of the $q=1$ specialisation of the identity, try to interpret it combinatorially (try to find sets naturally counted by your expressions), turn the proof into a bijective one (if it isn't one already), and then interpret a factor $q^k$ as putting a weight $k$ on the corresponding element; hopefully the bijection will preserve (appropriately defined) weights.2012-10-15

4 Answers 4

1

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

4

$\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 for 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.

  • 0
    +1. If you draw the picture this is$a$very elegant solution.2012-10-19
3

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.

  • 0
    @user43552: You’re welcome! (I also found them very helpful.)2012-10-15
1

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.