# Prove $\sum_{i=0}^{n}(-1)^{i}q^{(i+1)i/2}{n\choose i}_{q}{n+m-i\choose n}_{q}=1$

Show that for any non-negative integers $$n, m$$ such that $$n\le m$$, we have $$\sum_{i=0}^{n}(-1)^{i}q^{(i+1)i/2}{n\choose i}_{q}{n+m-i\choose n}_{q}=1$$ where $${n\choose i}_{q}$$ is the Gaussian binomial coefficient.

I have noticed that the expression $${n\choose i}_{q}{n+m-i\choose n}_{q}$$ is symmetric with respect to $$n$$ and $$m$$. Also, $$(-1)^{i}q^{(i+1)i/2}{n\choose i}_{q}$$ is the coefficient of $$t^{i}$$ in $$\prod_{j=0}^{n-1}(1-q^{j+1}t)$$ and $${n+m-i\choose n}_{q}$$ is the coefficient of $$t^{n}$$ in $$\prod_{j=0}^{m-i}(1-q^{j}t)^{-1}$$. I have been working on this problem for days yet still have no solutions though this should not be very hard.

• I believe I have an answer, which I'll try and put up by tomorrow once I proof check it. Just letting you know my progress. Commented Apr 7, 2023 at 19:47
• This is true for all non-negative integers $n,m$. The restriction to $n\le m$ is not needed. Commented Jun 16, 2023 at 23:49

We provide a combinatorial proof of the given fact. The proof technique uses a combinatorial interpretation for the Gaussian binomial coefficient which you should try and match with yours. Use the Wikipedia page for the $$q$$-binomial coefficient to connect the inversions and lattice path interpretations. Use this page to connect the lattice path and the tiling interpretation. I won't be using any of these, but I can map my interpretation to the lattice path one easily.

The following interpretation will be used. Let $$[n] = \{1,2,\ldots,n\}$$ for $$n \geq 1$$. Given $$n,k \geq 1$$, let $$S^n_k$$ be the set of subsets of $$[n]$$ that have size $$k$$ (There will be no such subset for $$k>n$$). Given $$S \in S^n_k$$, define the weight of $$S$$ to be $$w(S) = q^{\sum_{i \in S}\#\{j \notin S : j < i\}}$$ For example, the weight of $$\{2,4\}$$ is $$q^{1+2}= q^3$$. The weight of $$\{1,2,3,5\}$$ is $$q^{0+0+0+1} = q^1$$. Then, we have $$\binom{n}{k}_q = \sum_{S \in S^n_k} w(S)$$

Here is the appropriate link to the lattice path interpretation. For $$S \in S^n_k$$, we must have $$n \geq k$$ (otherwise $$S^n_k$$ is empty). Consider the lattice $$\mathbb Z^2$$, and recall the lattice path interpretation : for every lattice path from $$(0,0)$$ to $$(k,n-k)$$, the weight of the lattice path is found by calculating the total number of squares that are on the left side of the path, and raising $$q$$ to that power. We then sum over all lattice paths to get $$\binom{n}{k}_q$$.

In this case, given $$S$$, go up if that particular element is in $$S$$, and go right otherwise. This gives a lattice path. You can easily go backwards. For example, say you're given $$\{1,2,3,5\} \in S^{5}_4$$. Then, the path is up-up-up-right-up, so you get $$(0,0) \to (1,0) \to (2,0) \to (3,0) \to (3,1) \to (4,1)$$ There's only one box to the left of this path, so the weight is $$1$$, as desired.

If you're given $$\{2,4\} \in S^{4}_2$$, then the path is right-up-right-up, so $$(0,0) \to (0,1) \to (1,1) \to (1,2) \to (2,2)$$. This will have three blocks to its right, as desired.

For an example the other way, let the path be up-up-right-up-right-up, then the set is $$\{1,2,4,6\} \in S^6_4$$. You can check that the weights of both equal $$3$$.

Thus, this bijection is well defined.

We now use the given definition of the $$q$$-binomial coefficient to write $$\sum_{i=0}^n (-1)^i q^{\frac{i(i+1)}{2}} \binom{n}{i}_q \binom{n+m-i}{n}_q = \sum_{i=0}^n \sum_{S \in S^n_i} \sum_{S' \in S^{n+m-i}_n} (-1)^i q^{\frac{i(i+1)}2} w(S)w(S')$$

Now, what we will do is write down a map $$f$$ that will behave as a signed involution. For $$i \geq 1$$, let $$\mathcal S_i = S^n_i \times S^{n+m-i}_n$$. For $$i=0$$, let $$\mathcal S_0 = (\emptyset \times (S^{n+m}_n)) \setminus (\emptyset, [n])$$. We have removed the element $$(\emptyset, [n])$$. If you observe, when $$S = \emptyset, S' = [n]$$ then ($$i=0$$, and) the contribution of this term to the sum in the summation above is exactly $$q^0 = 1$$. This the only term with the contribution $$1$$, hence we exclude it and focus on the rest.

We will find a map $$f : \bigcup_{i=0}^n \mathcal S_i \to \bigcup_{i=0}^n \mathcal S_i$$

Such that :

• $$f(f(x)) = S$$ for all $$S \in \bigcup_{i=0}^n \mathcal S_i$$.

• For $$(S,S') \in \bigcup_{i=0}^n \mathcal S_i$$, if we let $$W(S,S') = q^{\frac{(|S|)(|S|+1)}{2}} w(S)w(S')$$, then $$W(S,S') = W(f(S,S'))$$ for all $$(S,S')$$.

• For $$(S,S') \in \bigcup_{i=0}^n \mathcal S_i$$, if $$f(S,S') = (S_1,S'_1)$$ then $$|S| - |S_1| = \pm 1$$.

Assuming the existence of such a map, $$f$$ is a bijection but it inverts the sign of the weight because of the last bullet point. Hence, $$\sum_{i=0}^n \sum_{S \in S^n_i} \sum_{S' \in S^{n+m-i}_n} (-1)^i q^{\frac{i(i+1)}2} w(S)w(S') = 1 + \sum_{(S,S') \in \bigcup_{i=0}^n \mathcal S_i} (-1)^{|S|}W(S,S') \\ = 1 - \sum_{(S,S') \in \bigcup_{i=0}^n \mathcal S_i} (-1)^{|S|}W(S,S') \\ =1$$

Therefore, all we need to do is construct such a map $$f$$. While the construction is somewhat unobvious, it is worth keeping in mind that I came up with the idea by observing terms which cancel for small values of $$n$$ and $$m$$, followed by the creation of $$f$$.

Anyhow, here's the description of $$f$$. Given $$(S,S')$$, consider the following quantities :

• The smallest element of $$S$$, call it $$\min S$$. Let $$\min \emptyset = +\infty$$.

• Let $$\max S'$$ be the largest element of $$S'$$. Suppose that $$r_{S'}$$ is the largest number such that all of the numbers $$\max S', \max S'-1, \ldots, \max S' - r+1$$ are all in $$S'$$. We call $$r$$ as the "run size" of $$S'$$. For example, the run size of $$\{1,2,3,5\}$$ is $$1$$ because the number below $$5$$ is not part of this set. On the other hand, the run size of $$\{2,3,6,7\}$$ is $$2$$, the run size of $$\{1,3,4,5\}$$ is $$3$$, and so on.

We break the analysis into two cases : either the $$r_{S'} < \min S$$, or $$r_{S'} \geq \min S$$.

• If $$r_{S'} < \min S$$, then we describe $$f(S,S') = (S_1,S'_1)$$. We have $$S_1 = S \cup \{r_{S'}\}$$, and $$S'_1 = (S_1 \setminus \{\max S_1\}) \cup \{\max S_1 - r_{S'}\}$$.

• Suppose $$r_{S'} \geq \min S$$,then we describe $$f(S,S') = (S_1,S'_1)$$. In this case, $$S_1 = S \setminus \{\min S\}$$ and $$S'_1 = (S' \setminus \{\max S' - \min S + 1\}) \cup \{\max S' + 1\}$$.

Let me give some examples of this bijection to make it utterly clear what is going on.

• Suppose that $$S = \emptyset$$ and $$S' = \{2,4,5\}$$. Then $$r_{S'} = 2$$ and $$\min S = +\infty$$. We are as in the first case, so $$S_1 = \emptyset \cup \{2\} = \{2\}$$, and $$S'_1 = \{2,4,5\} \setminus \{5\} \cup \{3\} = \{2,3,4\}$$. So, $$f(\emptyset, \{2,4,5\}) = (\{2\},\{2,3,4\})$$.

• To show the involutory property, let's just go the other way. Suppose that $$S = \{2\}$$ and $$S' = \{2,3,4\}$$. Then, $$r_{S'} = 3$$ and $$\min S = 2$$. We are in the second case, so $$S_1$$ comes by removing $$\min S$$ i.e. $$S_1 = \emptyset$$ and $$S'_1$$ comes from removing $$4-2+1 = 3$$ and adding $$4+1 = 5$$, so that we get back $$S'_1 = \{2,4,5\}$$.

• A more complicated example : Suppose that $$S = \{3,7\}$$ and $$S' = \{2,4,5,6,8,9,10\}$$. Then, $$r_{S'} = 3$$ and $$\min S = 3$$. We are in the second case, so $$f(S,S') = (S_1,S'_1)$$ where $$S_1$$ comes from removing the minimum i.e. $$S_1 = \{7\}$$ and $$S'_1$$ comes from removing $$10-3+1$$ i.e. $$8$$ and replacing it by $$10+1$$ i.e. $$11$$ so that $$S'_1 = \{2,4,5,6,9,10,11\}$$.

Let's now prove the properties of $$f$$ that we asserted. Given a pair $$(S,S')$$, suppose that it fits the first case i.e. $$r_{S'} < \min S$$. Then, following the procedure to get $$S_1,S'_1 = f(S,S')$$, by definition we have $$S_1 = S \cup \{r_{S'}\}$$ and $$S'_1 = S \setminus \{\max S_1\} \cup \{\max S_1 - r_{S'}\}$$. Following this, observe that $$\min S_1 = r_{S'}$$. We have $$\max S'_1 = \max S' - 1$$, and because the elements in the "run" of $$S'$$ were kept on in $$S_1$$, we actually added to that run by adding the element $$\max S_1 - r_{S'}$$. In other words, one can check that $$r_{S'_1} \geq r_{S'} = \min S_1$$. Therefore, we are in the second case, and one easily checks by going back that $$f(f(S,S')) = (S,S')$$, whenever $$(S,S')$$ are as in the first case. If they are in the second case, a similar analysis holds.

The third bullet point is obvious, since while forming $$f(S,S') = (S_1,S'_1)$$, $$S_1$$ is formed by either removing an element in $$S$$ or inserting an element into $$S$$ that is not in $$S$$.

The second bullet point is proved by cases. Let us illustrate this by an example.

If $$(S,S') = (\{2,3\}, \{4,5,7\})$$ then $$f(S,S') = (\{1,2,3\},\{4,5,6\})$$. We have $$W(S,S') = q^{3 + 2+10} = q^{15}$$ and $$W(f(S,S')) = q^{6+0+9} = q^{15}$$ as well. Observe that the weight of the $$S$$ component went down by $$2 = |S|- r_{S'}+1$$, and the weight of the $$S'$$ component went down by $$1= r_{S'}$$. The total decrease is by $$|S|+1$$. However, this is compensated by the fact that the power of $$q$$ related to $$|S|$$ went up by exactly that amount.

Suppose that $$(S,S')$$ are as in the first case i.e. $$r_{S'} < \min S$$. Then, if $$f(S,S') = (S_1,S'_1)$$, we see that $$w(S_1) = w(S \cup \{r_{S'}\}) = w(S)q^{(r_{S'}-1)-(|S_1|-1)} = w(S)q^{r_{S'}-|S|-1}$$. This is because when we add $$r_{S'}$$, then $$r_{S'} = \min S_1$$ by definition, so this adds $$r_{S'}-1$$ to the power in $$q$$. On the other hand, every other element in $$S'$$ is bigger than $$r_{S'}$$ so when $$r_{S'}$$ is added, the weight corresponding to that element decreases from the weight corresponding to $$S$$ by $$1$$ ,amd there are $$|S|$$ such elements.

On the other hand, $$w(S'_1) = w(S' \setminus \{\max S'\}) \cup \{\max S' - r_{S'}\}$$ When we replace $$\max S'$$ by $$\max S_1 -r_{S'}$$, then this costs one power of $$q$$. For every element between these as well, one power of $$q$$ is removed. Thus, in total, a total exponent of $$r_{S'}$$ is lost. All in all, we get $$w(S'_1) = w(S')q^{-r_S}$$.

Therefore, $$w(S'_1)w(S_1) = w(S)w(S')q^{-(|S|+1)}\\ \implies W((S,S')) = w(S)w(S')q^{|S|(|S|+1)/2} = w(S)w(S')q^{(|S|+1)(|S|+2)/2}q^{-(|S|+1)} = w(S_1)w(S'_1)q^{(|S'|)(|S'|+1)/2} = W(f(S,S'))$$ as desired. Something similar applies to the second case.

Note that this proof may have been somewhat surprising, especially for those who are used to more power-series based proofs. Another important point is that this proof works even when $$m, if we assume that $$\binom{n}{k}_q = 0$$ for $$k>n$$. The same proof works, except that you only need to consider $$\mathcal S_i$$ for $$i=0,1,\ldots,\min\{m,n\}$$. That is, we get $$\sum_{i=0}^{\min\{m,n\}} (-1)^i q^{i(i+1)/2}\binom{n}{i}_q \binom{m+n-i}{n}_q = 1$$

We show the q-binomial identity \begin{align*} \color{blue}{\sum_{k=0}^n(-1)^kq^{\binom{k+1}{2}}\binom{n}{k}_q\binom{n+m-k}{n}_q=1}\tag{1} \end{align*} is a q-Vandermonde identity in disguise. But that's not all. A special twist using a tricky transformation is needed in order to show (1) for non-negative integers $$n\leq m$$.

We start with the left-hand side of (1) and obtain \begin{align*} \color{blue}{\sum_{k=0}^{n}}&\color{blue}{(-1)^kq^{\binom{k+1}{2}}\binom{n}{k}_q\binom{n+m-k}{n}_q}\\ &=\sum_{k=0}^{n}(-1)^kq^{\binom{k+1}{2}}\binom{n}{k}_q\binom{n+m-k}{n}_q\tag{2.1}\\ &=\sum_{k=0}^n(-1)^kq^{\binom{k+1}{2}}\binom{n}{k}_qq^{(n+m-k)(m-k)-\binom{m-k}{2}} (-1)^{m-k}\binom{-n-1}{m-k}_q\tag{2.2}\\ &\,\,\color{blue}{=(-1)^mq^{\binom{m+1}{2}+mn}\sum_{k=0}^m(-1)^k\binom{n}{k}_q\binom{-n-1}{m-k}_q q^{k(k-m-n)}}\tag{2.3}\\ \end{align*} The representation (2.3) has already a nice shape and looks like a q-Vandermonde identity. But an additional twist is needed, to get the right one as these identities come in different flavours. Thanks to @SarveshRavichandranIyer who cleverly added a transformation $$q\to q^{-1}$$ in his answer of this related post we will also use this idea and show the validity of (1).

Comment: In the following we use some identities which can all be derived from \begin{align*} \binom{n}{k}_q=\frac{\left(1-q^n\right)\left(1-q^{n-1}\right)\cdots\left(1-q^{n-k+1}\right)} {\left(1-q\right)\left(1-q^2\right)\cdots\left(1-q^k\right)} \end{align*}

• In (2.1) we use the q-binomial identity $$\binom{n}{k}_q=\binom{n}{n-k}_q$$.

• In (2.2) we use the q-binomial identity \begin{align*} \binom{-n}{k}_q=q^{-nk-\binom{k}{2}}(-1)^k\binom{n+k-1}{k}_q \end{align*}

• In (2.3) we do some simplifications and set the upper limit of the sum to $$m$$ which is admissible since $$\binom{n}{k}_q=0$$ if $$m>n$$.

We conclude from (2.3) in order to show (1) we have to show the validity of \begin{align*} \color{blue}{\sum_{k=0}^m\binom{n}{k}_q\binom{-n-1}{m-k}_qq^{k(k-m-n)+mn}=(-1)^mq^{\binom{m+1}{2}}}\tag{3} \end{align*}

We start with the q-Vandermonde identity \begin{align*} \sum_{k=0}^t\binom{n}{k}_q\binom{m}{q-k}_qq^{k(m-t+k)}=\binom{n+m}{t}_q\tag{4} \end{align*}

Using the q-binomial coefficients from (3) the q-Vandermonde identity (4) becomes \begin{align*} \sum_{k=0}^m\binom{n}{k}_q\binom{-n-1}{m-k}_qq^{k(k-m-n-1)} =\binom{-1}{m}_q=(-1)^mq^{-\binom{m+1}{2}}\tag{5.1} \end{align*}

Here we use the special case $$\binom{-1}{m}$$ of the identity $$\binom{-n}{m}$$ we already applied in (2.2). Note, that (5.1) and (3) look very similar, but they are not identical.

Now we use the trick from @SarveshRavichandranIyer and transform the identity (5.1) by substituting $$q$$ with $$q^{-1}$$ and get the identity \begin{align*} \sum_{k=0}^m\binom{n}{k}_{q^{-1}}\binom{-n-1}{m-k}_{q^{-1}}q^{-k(k-m-n-1)} =(-1)^mq^{\binom{m+1}{2}}\tag{5.2} \end{align*} We continue and substitute back, but this time by using the q-binomial identity \begin{align*} \binom{n}{q}_{q^{-1}}=q^{-nk+k^2}\binom{n}{k}_q\tag{5.3} \end{align*} Using (5.3) in identity (5.2) we obtain \begin{align*} \sum_{k=0}^n&q^{-nk+k^2}\binom{n}{k}_qq^{-(-n-1)(m-k)+(m-k)^2}\binom{-n-1}{m-k}_q q^{-k(k-m-n-1)}\\ &=(-1)^mq^{\binom{m+1}{2}} \end{align*} and after collecting terms we finally get \begin{align*} \color{blue}{\sum_{k=0}^n\binom{n}{k}_q\binom{-n-1}{m-k}_qq^{k(k-m-n)+mn}=(-1)^mq^{\binom{m+1}{2}}}\\ \end{align*} which proves the claim (3) and therefore also (1).

• +1, thank you for citing the answer in the earlier post! Commented Apr 16, 2023 at 6:55
• @SarveshRavichandranIyer: My pleasure! I've learned from your approach and will routinely add this transformation in my tool box. :-) Commented Apr 16, 2023 at 7:02