# Addition Rule for Gaussian Binomial Coefficients/Formulation 1

Jump to navigation Jump to search

## Theorem

Let $\dbinom n m_q$ denote a Gaussian binomial coefficient.

Then:

$\dbinom n m_q = \dbinom {n - 1} m_q + \dbinom {n - 1} {m - 1}_q q^{n - m}$

## Proof

By definition of Gaussian binomial coefficient:

 $\displaystyle \binom n m_q$ $:=$ $\displaystyle \prod_{j \mathop = 0}^{m - 1} \dfrac {1 - q^{n - j} } {1 - q^{j + 1} }$ $\displaystyle$ $=$ $\displaystyle \dfrac {\paren {1 - q^n} \paren {1 - q^{n - 1} } \dotsm \paren {1 - q^{n - m + 1} } } {\paren {1 - q^m} \paren {1 - q^{m - 1} } \dotsm \paren {1 - q^1} }$

Thus:

 $\displaystyle \dbinom {n - 1} m_q + \dbinom {n - 1} {m - 1}_q q^{n - m}$ $=$ $\displaystyle \prod_{j \mathop = 0}^{m - 1} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } + q^{n - m} \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} }$ Definition of Gaussian Binomial Coefficient $\displaystyle$ $=$ $\displaystyle \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {\dfrac {1 - q^{n - 1 - \paren {m - 1} } } {1 - q^{\paren {m - 1} + 1} } + q^{n - m} }$ extracting $\displaystyle \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} }$ as a factor $\displaystyle$ $=$ $\displaystyle \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {\dfrac {1 - q^{n - m} } {1 - q^m} + q^{n - m} }$ simplifying $\displaystyle$ $=$ $\displaystyle \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {\dfrac {1 - q^{n - m} + q^{n - m} \paren {1 - q^m} } {1 - q^m} }$ placing over a common denominator $\displaystyle$ $=$ $\displaystyle \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {\dfrac {1 - q^{n - m} + q^{n - m} - q^{n - m} q^m} {1 - q^m} }$ $\displaystyle$ $=$ $\displaystyle \prod_{j \mathop = 0}^{m - 2} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} } \paren {\dfrac {1 - q^n} {1 - q^m} }$ $\displaystyle$ $=$ $\displaystyle \prod_{j \mathop = 0}^{m - 1} \dfrac {1 - q^{n - 1 - j} } {1 - q^{j + 1} }$ $\displaystyle$ $=$ $\displaystyle \binom n m_q$ Definition of Gaussian Binomial Coefficient

$\blacksquare$