Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Trying a bit of combinatorics this winter break, and I don't understand a certain claim.

The claim is that for each $k$ there is a unique polynomial $P_k(x)$ of degree $k$ whose coefficients are in $\mathbb{Q}(q)$, the field of rational functions, such that $P_k(q^n)=\binom{n}{k}_q$ for all $n$.

Here $\binom{n}{k}_q$ is the $q$-binomial coefficient. I guess what is mostly troubling me is that $P_k(q^n)$ is a polynomial in $q^n$. I'm sure it's obvious, but why is the claim true? Thanks.

share|cite|improve this question
Consider a simple example of $\binom{2}{1}_q = 1 + q$. This is not a function of $q^2$. – Sasha Dec 19 '11 at 18:10
IOW: fix $k$ any positive integer, then there are rational functions $R_0,\dots,R_k$ such that $$\forall n\in\mathbb{N}:\quad {n \choose k}_q=R_0(q)+R_1(q)q^n+\cdots+R_k(q)q^{kn}.$$ – anon Dec 19 '11 at 18:52
@Sasha, if $P(x)=1+q^{-1}x$, then $P(q^2)=1+q$. – Mariano Suárez-Alvarez Dec 19 '11 at 23:40
up vote 2 down vote accepted

I think it could go something like this (but I'll bet there's also an inductive proof or even a more direct and beautiful formula): $$ [n]_q = \sum_{i=0}^{n-1}\;q^i = \frac{1-q^n}{1-q} = f(q^n) \qquad\text{for}\qquad 0 < n \in \mathbb{N} \qquad\text{and}\qquad f(x) = \frac{1-x}{1-q} \in \mathbb{Q}(q)[x] $$ Now if we note that $[0]_q=0$ and that $[a+b]_q=[a]_q+q^a[b]_q$ for $a,b\in\mathbb{N}$, then for $a=n-i$ and $b=1+i$, it follows that $[n-i]_q=[n]_q-q^{n-i}[1+i]_q$ for $0 \leq i \leq k < n$, so that $$ \binom{n}{k}_q = \prod_{i=0}^{k-1}\frac{[n-i]_q}{[1+i]_q} = \prod_{i=0}^{k-1}\frac{[n]_q-q^{n-i}[1+i]_q}{[1+i]_q} = P_k(q^n) %\qquad\text{for}\qquad %[m]_q! = \prod_{h=1}^{m} [h]_q $$ for $$ P_k(x) =\prod_{i=0}^{k-1}\frac{f(x)-x\cdot c_i q^{-i}}{c_i} =\prod_{i=0}^{k-1}\left(\frac{f(x)}{c_i}-\frac{x}{q^i}\right) \in \mathbb{Q}(q)[x] $$ since each $c_i=[1+i]_q\in\mathbb{Q}(q)$, and that, furthermore, $deg(P_k)=k$ since each term in the above product is linear. This simplifies to $$ P_k(x) = \prod_{i=1}^{k} \frac{1 - x (1+q-q^{1-i})}{1-q^i}. $$

share|cite|improve this answer
Thank you bgins. – Vika Jan 20 '12 at 23:42

The $q$-binomial coefficient satisfies the recurrence $$ \binom{n}{k}_q = q^k \binom{n-1}{k}_q + \binom{n-1}{k-1}_q, $$ which follows easily from the definition. We can assume inductively that each term on the right is a polynomial and therefore the LHS is a polynomial.

Edit: Unfortunately this does not seem to yield the uniqueness required in the question.

share|cite|improve this answer
In which order are you inducting (over $k$, then $n$?) and does this show that the LHS is a degree-$k$ polynomial in $q^n$ over $\mathbb{Q}(q)$? Yes it would certainly be nicer than my method if it works. – bgins Dec 19 '11 at 23:46
I am using induction on $n$ only, and I can assume everything is zero if $n<k$, or just assume that $\binom{k}{k}_q=1$. You can get the degree too, just make the induction hypothesis that $\binom{n}{k}$ is monic of degree $k(n-k)$. – Chris Godsil Dec 20 '11 at 0:02
But how do you get that $\binom{n}{k}_q$ is a polynomial of degree $k$ in $q^n$? If you add this to the induction hypothesis, then how do you show that $P_k(q^n)=q^{k}P_k(q^{n-1})+P_{k-1}(q^{n-1})$, i.e. that the RHS simplifies to the LHS (easily)? I didn't see how to do it (immediately), which is why I chose the "uglier" way. – bgins Dec 20 '11 at 13:08
Any polynomial in $q$ over $\mathbb{Z}$ is a polynomial in $q^n$ over $\mathbb{Q}(q)$. – Chris Godsil Dec 20 '11 at 14:17
But we also want to show the uniqueness of each $P_k(x)\in\mathbb{Q}(q)[x]$. In particular, its coefficients cannot depend on $n$. – bgins Dec 20 '11 at 15:45

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.