Addition Rule for Gaussian Binomial Coefficients/Formulation 1

From ProofWiki
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$


Sources