# Unusual version of the binomial theorem?

This was an old problem I had years ago, but never really solved. Maybe it can be cracked here?

The situation is as follows.

Denote by $\mathbb{Q}(q)[X,Y]$ the algebra of polynomials over $\mathbb{Q}(q)$, the field of rational functions. Moreover, $X$ and $Y$ are indeterminates but do not commute. Let $\mathbf{Q}[x,y]=\mathbb{Q}(q)[X,Y]/I$, with $I$ being the (two-sided) ideal generated by $YX-qXY$. So $\mathbf{Q}[X,Y]$ is the ring whose generators satisfy the relation $YX=qXY$.

Why then is $(X+Y)^n=\sum_i\binom{n}{i}_qX^iY^{n-i}$ an identity in $\mathbf{Q}[X,Y]$?

Thank you for the tips. I expand \begin{align*} (X+Y)^{n+1} &= (X+Y)^n(X+Y)\\ &= (X+Y)^nX+(X+Y)^nY\\ &= \sum_i\binom{n}{i}_qX^{i}Y^{n-i}X+\sum_i \binom{n}{i}_qX^iY^{n-i+1}\\ &= \sum_iq^{n-i}\binom{n}{i}_qX^{i+1}Y^{n-i}+\sum_i \binom{n}{i}_qX^iY^{n-i+1}. \end{align*}

I also find \begin{align*} \sum_i\binom{n+1}{i}_qX^iY^{n+1-i} &= X^{n+1}+Y^{n+1}+\sum_{i=1}^n\binom{n+1}{i}_qX^iY^{n+1-i}\\ &= X^{n+1}+Y^{n+1}+\sum_{i=1}^n\left[q^i\binom{n}{i}_q+\binom{n}{i-1}_q\right]X^iY^{n+1-i}\\ &= \sum_{i=0}^nq^i\binom{n}{i}_qX^iY^{n+1-i}+\sum_{i=1}^{n+1}\binom{n}{i-1}_qX^iY^{n+1-i}. \end{align*} I also prove the commutation formula $$Y^{k+1}X=YY^kX=Yq^kXY^k=q^kYXY^k=q^kqXYY^k=q^{k+1}XY^{k+1}.$$

How does one reorder the monomials now to get the equality?

-
Have you tried induction? –  Qiaochu Yuan Feb 7 '12 at 7:16
You used that $(X+Y)^nX$ is $\sum_i\binom{n}{i}_qX^{i+1}Y^{n-i}$. It isn't. Write it out explicitely for small $n$ and you'll see! –  Mariano Suárez-Alvarez Feb 8 '12 at 4:42
@MarianoSuárez-Alvarez Thanks, I've tried to fix it, and the sums still don't quite match up. What follows next? –  Kally Feb 8 '12 at 4:52
Cool. Now, in that line where you fixed the mistake, pick one of the first sum and change the summation index $i$ so that it becomes $i+1$, so that the monomials appearing in the two sums look the same: $X^iY^{n+1-i}$. –  Mariano Suárez-Alvarez Feb 8 '12 at 4:53
@MarianoSuárez-Alvarez Right, I see it now. And using the other recursion identity $\binom{n}{i}_q=\binom{n-1}{i}_q+q^{n-i}\binom{n-1}{i-1}_q$ instead gives the equality. –  Kally Feb 8 '12 at 5:02

Prove it by induction. The case when $n=1$ is trivial, so:

• we assume it works for $n\geq1$ and compute $$(X+Y)^{n+1}=(X+Y)^n(X+Y)=(X+Y)^nX+(X+Y)^nY.$$

• Using the induction hypothesis, you can expand $(X+Y)^n$ in both places in the last member of the equation, and

• then you can use the commutation formula $$Y^kX=q^kXY^k$$ (which you can prove by induction...) to reorder the variables in every monomial.

• Finally, collect the two sums you have, and use the well-known recursion identities for the Gaussian polynomials to conclude what you want.

This is, except for step three, exactly the same as the usual inductive proof of the binomial theorem.

-
Thanks Mariano! I've added what I could do based on your outline. Can you explain how the reordering of the variables in each monomial works? –  Kally Feb 8 '12 at 4:39

A short answer is that the Gaussian binomial coefficients $\binom ni_q$ are defined precisely so as to make this identity hold. Without using commutativity, $(X+Y)^n$ works out to a sum of $2^n$ distinct terms, one for every word of length $n$ in the alphabet $\{X,Y\}$, interpreted as a product. Such a product $P$ can be rewritten, by repeatedly using the commutation relation $YX=qXY$, to the form $q^wX^iY^{n-i}$, where $i$ is the number of letters $X$ in $P$, and the "weight" $w$ of $P$ is the number of times a letter $Y$ precedes a letter $X$ in $P$ (to be precise, the number of pairs of positions with $Y$ in the leftmost position of the pair and $X$ in the rightmost position). This is easy to show by induction on the weight: each application of the commutation relation reduces the weight of the word by $1$.

Now $\binom ni_q$ can be defined as the sum, over all such words $P$ of length $n$ with $i$ occurrences of $X$, of $q^w$ where $w$ is the weight of $P$. Then $$(X+Y)^n=\sum_i\binom{n}{i}_qX^iY^{n-i}$$ is obvious. To see that this matches the algebraic definition, it suffices that $\binom n0_q=1=\binom nn_q$ and $$\binom ni_q=\binom{n-1}{i-i}_q+q^i\binom{n-1}i_q \quad\text{for }0<i<n,$$ since prefixing an $X$ to a word leaves its weight unchanged, and prefixing a $Y$ increases its weight by the number of letters $X$ it contains. An equivalent combinatorial definition is that $\binom ni_q$ is the sum, over all paths$~p$ diagonally across an $i\times(n-i)$ rectangle, of $q^{a(p)}$, where $a(p)$ is the area of the rectangle below the path$~p$.

-