3
$\begingroup$

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?

  • 0
    Indeed. ${}{}{}$2012-02-08

2 Answers 2

5

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.

  • 0
    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?2012-02-08
2

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