12
$\begingroup$

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

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

3 Answers 3

20
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Could you give a reference for these area generating functions? $\endgroup$ Commented May 18, 2017 at 20:36
  • $\begingroup$ They are all immediate corollaries of counting lattice paths in a rectangle. Drawing a picture helps a lot :) $\endgroup$ Commented May 18, 2017 at 20:37
  • 1
    $\begingroup$ @GjergjiZaimi: Very pleasant. $\endgroup$ Commented May 18, 2017 at 20:45
11
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ You got to do what you wanted in Part I. :-) $\endgroup$ Commented May 18, 2017 at 20:47
  • 1
    $\begingroup$ Yes, I copied and pasted it partially ;) $\endgroup$ Commented May 18, 2017 at 21:10
7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ This is also cool. $\endgroup$ Commented May 19, 2017 at 14:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .