As usual, denote $[n]_q=1+q+\cdots+q^{n-1}=\frac{\,\,1-q^n}{1-q}$ and $[n]_q!=[1]_q[2]_q\cdots[n]_q$. Furthermore, we write $$\binom{n}k_q=\frac{[n]_q!}{[k]_q!\cdot[n-k]_q!}.$$ As a follow up on this MO question, I propose a $q$-analogue identity.

Question. Can you show that $$\sum_{k=0}^nq^{(y-n+1)k}\binom{x+k}k_q\binom{y-k}{n-k}_q =\sum_{k=0}^nq^{n-k}\binom{x+y-k}{n-k}_q\,\,\,?$$

It would be great if we can see alternative proofs? I've a bias for combinatorial arguments. :-)

  • $\begingroup$ it is interesting for $x=0$: we get that two different $q$-analogs of $\sum \binom{y-k}{n-k}$ are equal. $\endgroup$ – Fedor Petrov May 19 '17 at 10:23
  • $\begingroup$ That's a cute observation, Fedor! $\endgroup$ – T. Amdeberhan May 19 '17 at 12:28

Both sides are equal to $\binom{x+y+1}{n}_q$. This enumerates lattice paths in an $n\times (x+y-n+1)$ rectangle, according to the area statistic. We will assume that these paths start at $(0,0)$ and end at $(x+y-n+1,n)$, and they are only directed East or North. Here are two ways to enumerate it:

First count: For each path there will be a unique $k$, so it has an East step of the form $(x,k)\to (x+1,k)$. The area generating function of these paths is precisely $$q^{y-n+1}\binom{x+k}{k}_q\binom{y-k}{n-k}_q.$$ Now, summing over all possible $k$, we enumerate all paths in the rectangle.

Second count: For each path there will be a unique $k$ so that it has an East step $(x+y-n,k)\to (x+y-n+1,k)$. Similarly the generating function of the areas of these paths is $$q^{n-k}\binom{x+y-k}{n-k}_q$$ and just like above, summing over all possible $k$ enumerates all paths.

  • $\begingroup$ Could you give a reference for these area generating functions? $\endgroup$ – მამუკა ჯიბლაძე May 18 '17 at 20:36
  • $\begingroup$ They are all immediate corollaries of counting lattice paths in a rectangle. Drawing a picture helps a lot :) $\endgroup$ – Gjergji Zaimi May 18 '17 at 20:37
  • 1
    $\begingroup$ @GjergjiZaimi: Very pleasant. $\endgroup$ – T. Amdeberhan May 18 '17 at 20:45

If we substitute $y:=v+n$ in the identity, the LHS becomes a convolution of two similar sequences, $$\sum_{k=0}^nq^{(v+1)k}\binom{x+k}{k}_q \binom{v+(n-k)}{n-k}_q =\sum_{k=0}^n q^{n-k}\binom{x+v+n-k}{n-k}_q \, .$$

In terms of the known series $$f_x(z):=\sum_{k=0}^\infty \binom{x+k}{k}_q \,z^k=\prod_{k=0}^x{1\over1-q^kz}$$ the identity reads $$f_x(q^{v+1}z)\cdot f_v(z)={1\over1-z}\cdot f_{x+v}(qz)=f_{x+v+1}(z)\, ,$$ which is straightforward.

($\prod_{k=v+1}^{v+1+x}\,\prod_{k=0}^{v}=\prod_{k=1}^{v+1+x}\,\prod_{k=0}^{0}=\prod_{k=0}^{v+x+1}$) $$*$$ rmk. Note that the latter also gives again the first identity of Gjergji's answer, since $[z^n]f_{x+v+1}(z)=\binom{ x+v+1+n}{n}_q=\binom{ x+y+1}{n}_q$.

  • $\begingroup$ You got to do what you wanted in Part I. :-) $\endgroup$ – T. Amdeberhan May 18 '17 at 20:47
  • 1
    $\begingroup$ Yes, I copied and pasted it partially ;) $\endgroup$ – Pietro Majer May 18 '17 at 21:10

Actually this is a partial case of $q$-Vandermonde identity. In the notation $$[a;b]_q^n:=(a-b)(a-qb)\dots (a-q^{n-1}b)=a^n(b/a;q)_n,$$ as in this terminology question, we have $$ [a;c]_q^n=\sum {\binom{n}{k}}_q[a;b]_q^{n-k}\,[b;c]_q^{k}, $$ which is an equivalent form of $q$-Vandermonde identity.

Substituting $a=q^{n-y-1}$, $b=1$, $c=q^{x+1}$ we get $$\sum_{k=0}^nq^{(y-n+1)k}\binom{x+k}k_q\binom{y-k}{n-k}_q=\binom{x+y+1}n_q,$$ replacing $x,y$ to $x+y-n,n$ (and $k$ to $n-k$ in the sum) we get that RHS also equals $\binom{x+y+1}n_q$.

  • $\begingroup$ This is also cool. $\endgroup$ – T. Amdeberhan May 19 '17 at 14:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.