How do I construct a bijection to prove the $q$-binomial theorem?

Question

\begin{align*} \sum_{k=0}^{n} q^{\binom{k}{2}} \binom{n}{k}_q x^k = \prod_{i=0}^{n-1} \left(1+xq^i\right),\quad \forall \ n\ge 1 \end{align*}

This problem can be solved by mathematical induction, but I want to find a combinatorial proof.

Answer 1

Here is a proof without induction (but no combinatorial proof, hence I will make this answer CW):

Let $$f(x) := \prod_{i=0}^{n-1} (1+q^i x) = (1+x)(1+qx) \cdots (1+q^{n-1} x).$$ Then one can easily check $$(1+x)\, f(qx) = (1+q^n x) \,f(x).$$ So, if $f(x) = \sum_{k=0}^{n} f_k x^k$ with coefficients $f_k \in \mathbb{Z}[q]$, then $$f_k \, q^k + f_{k-1} \, q^{k-1} = f_k + q^n\, f_{k-1}.$$ Equivalently, $$f_k = f_{k-1} \frac{q^n - q^{k-1}}{q^k - 1} = f_{k-1} \frac{q^{n-k+1} - 1}{q^k-1} q^{k-1}.$$ Also, $f_0 = 1$. Hence, $$f_k = \prod_{i=1}^{k} \frac{q^{n-i+1}-1}{q^i-1} ~ q^{\large \sum_{i=0}^{k-1} i} = \binom{n}{k}_q \,q^{k(k-1)/2}$$