# Representing the $q$-binomial coefficient as a polynomial with coefficients in $\mathbb{Q}(q)$?

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.

-
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

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

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