Chu-Vandermonde Identity for Gaussian Binomial Coefficients
Jump to navigation
Jump to search
Theorem
Let $q \in \R_{\ne 1}, r, s \in \R, n \in \Z$.
Then:
\(\ds \binom {r + s} n_q\) | \(=\) | \(\ds \sum_k \binom r k_q \binom s {n - k}_q q^{\left({r - k}\right) \left({n - k}\right)}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_k \binom r k_q \binom s {n - k}_q q^{\left({s - n + k}\right) k}\) |
where $\dbinom r k_q$ is a Gaussian binomial coefficient.
Proof
\(\ds \sum_{n \mathop \in \Z} \dbinom {r + s} n_q q^{n \left({n - 1}\right) / 2} x^n\) | \(=\) | \(\ds \prod_{k \mathop = 1}^{r + s} \left({1 + q^{k - 1} x}\right)\) | Gaussian Binomial Theorem | |||||||||||
\(\ds \) | \(=\) | \(\ds \prod_{k \mathop = 1}^r \left({1 + q^{k - 1} x}\right) \prod_{k \mathop = r + 1}^s \left({1 + q^{k - 1} x}\right)\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \prod_{k \mathop = 1}^r \left({1 + q^{k - 1} x}\right) \prod_{k \mathop = 1}^{s - r} \left({1 + q^{r + k - 1} x}\right)\) | Translation of Index Variable of Product |
Sources
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (previous) ... (next): $\S 1.2.6$: Binomial Coefficients: Exercise $58$