Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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

2 Answers 2

up vote 5 down vote accepted

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.

share|improve this answer
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$.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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