Gaussian Binomial Theorem
Theorem
Let $n \in \Z_{>0}$ be a (strictly) positive integer.
\(\ds \sum_{k \mathop \in \Z} \dbinom n k_q q^{k \paren {k - 1} / 2} x^k\) | \(=\) | \(\ds \prod_{k \mathop = 1}^n \paren {1 + q^{k - 1} x}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \paren {1 + x} \paren {1 + q x} \paren {1 + q^2 x} \cdots \paren {1 + q^{n - 1} x}\) |
where $\dbinom n k_q$ denotes a Gaussian binomial coefficient.
Real Numbers
Let $r \in \R$ be a real number.
- $\ds \sum_{k \mathop \in \Z} \dbinom r k_q q^{k \paren {k - 1} / 2} x^k = \prod_{k \mathop \ge 0} \dfrac {1 + q^k x} {1 + q^{r + k} x}$
where:
- $\dbinom r k_q$ denotes a Gaussian binomial coefficient
- $x \in \R: \size x < 1$
- $q \in \R: \size q < 1$.
Negation of Upper Index
Let $r \in \R$ be a real number.
\(\ds \prod_{k \mathop \ge 0} \dfrac {1 + q^{k + r + 1} x} {1 + q^k x}\) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \dbinom {-r - 1} k_q q^{k \left({k - 1}\right) / 2} \left({-q^{r + 1} x}\right)^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \dbinom {k + r} x^k\) |
where:
- $\dbinom r k_q$ denotes a Gaussian binomial coefficient.
- $x \in \R: \left\lvert{x}\right\rvert < 1$
- $q \in \R: \left\lvert{q}\right\rvert < 1$.
Proof
The proof proceeds by induction.
For all $n \in \Z_{\ge 1}$, let $\map P n$ be the proposition:
- $\ds \prod_{k \mathop = 1}^n \paren {1 + q^{k - 1} x} = \sum_{k \mathop \in \Z} \dbinom n k_q q^{k \paren {k - 1} / 2} x^k$
Basis for the Induction
$\map P 1$ is the case:
\(\ds \prod_{k \mathop = 1}^1 \paren {1 + q^{k - 1} x}\) | \(=\) | \(\ds 1 + x\) | ||||||||||||
\(\ds \sum_{k \mathop \in \Z} \dbinom 1 k_q q^{k \paren {k - 1} / 2} x^k\) | \(=\) | \(\ds \dbinom 1 0_q q^{0 \paren {0 - 1} / 2} x^0 + \dbinom 1 1_q q^{1 \paren {1 - 1} / 2} x^1\) | Gaussian Binomial Coefficient of 1: for all other $k$, $\dbinom 1 k_q = 0$ | |||||||||||
\(\ds \) | \(=\) | \(\ds q^{0 \paren {-1} / 2} + q^{1 \times 0 / 2} x^1\) | Gaussian Binomial Coefficient of 1: $\dbinom 1 0_q = \dbinom 1 1_q = 0$ | |||||||||||
\(\ds \) | \(=\) | \(\ds q^0 + q^0 x\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds 1 + x\) |
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
Induction Hypothesis
Now it needs to be shown that, if $\map P r$ is true, where $r \ge 1$, then it logically follows that $\map P {r + 1}$ is true.
So this is the induction hypothesis:
- $\ds \prod_{k \mathop = 1}^r \paren {1 + q^{k - 1} x} = \sum_{k \mathop \in \Z} \dbinom r k_q q^{k \paren {k - 1} / 2} x^k$
from which it is to be shown that:
- $\ds \prod_{k \mathop = 1}^{r + 1} \paren {1 + q^{k - 1} x} = \sum_{k \mathop \in \Z} \dbinom {r + 1} k_q q^{k \paren {k - 1} / 2} x^k$
Induction Step
This is the induction step:
\(\ds \prod_{k \mathop = 1}^{r + 1} \paren {1 + q^{k - 1} x}\) | \(=\) | \(\ds \prod_{k \mathop = 1}^r \paren {1 + q^{k - 1} x} \times \paren {1 + q^r x}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \dbinom r k_q q^{k \paren {k - 1} / 2} x^k \times \paren {1 + q^r x}\) | Induction Hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \dbinom r k_q q^{k \paren {k - 1} / 2} x^k + q^r x \sum_{k \mathop \in \Z} \dbinom r k_q q^{k \paren {k - 1} / 2} x^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \dbinom r k_q q^{k \paren {k - 1} / 2} x^k + \sum_{k \mathop \in \Z} \dbinom r k_q q^r q^{k \paren {k - 1} / 2} x^{k + 1}\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \dbinom r k_q q^{k \paren {k - 1} / 2} x^k + \sum_{k \mathop \in \Z} \dbinom r {k - 1}_q q^r q^{\paren {k - 1} \paren {k - 2} / 2} x^k\) | Translation of Index Variable of Summation | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \paren {\dbinom r k_q q^{k \paren {k - 1} / 2} + q^r q^{-\paren {k - 1} } \dbinom r {k - 1}_q q^{k \paren {k - 1} / 2} } x^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \paren {\dbinom r k_q + q^{r + 1 - k} \dbinom r {k - 1}_q} q^{k \paren {k - 1} / 2} x^k\) | ||||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop \in \Z} \dbinom {r + 1} k_q q^{k \paren {k - 1} / 2} x^k\) | Addition Rule for Gaussian Binomial Coefficients |
So $\map P r \implies \map P {r + 1}$ and the result follows by the Principle of Mathematical Induction.
Therefore:
- $\forall n \in \Z_{\ge 1}: \ds \prod_{k \mathop = 1}^n \paren {1 + q^{k - 1} x} = \sum_{k \mathop \in \Z} \dbinom n k_q q^{k \paren {k - 1} / 2} x^k$
$\blacksquare$
Also known as
Some sources give this as the $q$-nomial theorem.
Some refer to it as the $q$-binomial theorem.
Source of Name
This entry was named for Carl Friedrich Gauss.
Sources
- 1989: Ephraim J. Borowski and Jonathan M. Borwein: Dictionary of Mathematics ... (previous) ... (next): $q$-binomial
- 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$