TAOCP 1.2.6 Exercise 58

Exercise 58. [M23] In the notation of Eq. (40), prove the $q$-nomial theorem:

$$ (1+x)(1+qx)\cdots(1+q^{n-1}x) = \sum_k \binom{n}{k}_q q^{k(k-1)/2}x^k. $$

Verified: no
Solve time: -

Solution

We proceed by induction on $n$. Define

$f_n(x) = (1+x)(1+qx)\cdots(1+q^{n-1}x).$

The base case is $n=0$. Then $f_0(x) = 1$, and the right-hand side reduces to $\sum_k \binom{0}{k}_q q^{k(k-1)/2} x^k = \binom{0}{0}_q q^{0} x^0 = 1$, as required.

Assume the formula holds for some integer $n$, that is,

$$ f_n(x) = \sum_{k=0}^{n} \binom{n}{k}_q q^{k(k-1)/2} x^k. $$

Consider $f_{n+1}(x) = f_n(x),(1+q^n x)$. By the induction hypothesis,

$$ f_{n+1}(x) = \left(\sum_{k=0}^{n} \binom{n}{k}q q^{k(k-1)/2} x^k\right) (1+q^n x) = \sum{k=0}^{n} \binom{n}{k}q q^{k(k-1)/2} x^k + \sum{k=0}^{n} \binom{n}{k}_q q^{k(k-1)/2} q^n x^{k+1}. $$

Reindex the second sum by setting $k' = k+1$, giving

$$ \sum_{k=1}^{n+1} \binom{n}{k-1}q q^{(k-1)(k-2)/2} q^n x^k = \sum{k=1}^{n+1} \binom{n}{k-1}_q q^{(k-1)(k-2)/2 + n} x^k. $$

Note that

$$ (k-1)(k-2)/2 + n = k(k-1)/2, $$

because

$$ (k-1)(k-2)/2 + n = \frac{k^2 -3k + 2}{2} + n = \frac{k^2 - k}{2} + (n - k +1) = k(k-1)/2 + (n - k +1). $$

However, in the $q$-binomial identity, the recurrence for the $q$-binomial coefficients is

$$ \binom{n+1}{k}_q = \binom{n}{k}_q + q^{n+1-k} \binom{n}{k-1}_q. $$

Using this, the coefficient of $x^k$ in $f_{n+1}(x)$ becomes

$$ \binom{n}{k}_q q^{k(k-1)/2} + q^k \binom{n}{k-1}_q q^{(k-1)(k-2)/2} = q^{k(k-1)/2} \left( \binom{n}{k}_q + q^{n+1-k} \binom{n}{k-1}_q \right) = \binom{n+1}{k}_q q^{k(k-1)/2}. $$

Thus,

$$ f_{n+1}(x) = \sum_{k=0}^{n+1} \binom{n+1}{k}_q q^{k(k-1)/2} x^k, $$

establishing the induction step.

This completes the proof.

∎