Binomial Theorem/Ring Theory

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\left({R, +, \odot}\right)$ be a ringoid such that $\left({R, \odot}\right)$ is a commutative semigroup.


Let $n \in \Z: n \ge 2$. Then:

$\displaystyle \forall x, y \in R: \odot^n \left({x + y}\right) = \odot^n x + \sum_{k \mathop = 1}^{n-1} \binom n k \left({\odot^{n-k} x}\right) \odot \left({\odot^k y}\right) + \odot^n y$

where $\dbinom n k = \dfrac {n!} {k! \ \left({n - k}\right)!}$ (see Binomial Coefficient).


If $\left({R, \odot}\right)$ has an identity element $e$, then:

$\displaystyle \forall x, y \in R: \odot^n \left({x + y}\right) = \sum_{k \mathop = 0}^n \binom n k \left({\odot^{n - k} x}\right) \odot \left({\odot^k y}\right)$


Proof

First we establish the result for when $\left({R, \odot}\right)$ has an identity element $e$.

For $n = 0$ we have:

$\displaystyle \odot^0 \left({x + y}\right) = e = {0 \choose 0} \left({\odot^{0 - 0} x}\right) \odot \left({\odot^0 y}\right) = \sum_{k \mathop = 0}^0 {0 \choose k} x^{0 - k} \odot y^k$


For $n = 1$ we have:

$\displaystyle \odot^1 \left({x + y}\right) = \left({x + y}\right) = {0 \choose 1} \left({\odot^{1 - 0} x}\right) \odot \left({\odot^0 y}\right) + {1 \choose 1} \left({\odot^{1 - 1} x}\right) \odot \left({\odot^1 y}\right) = \sum_{k \mathop = 0}^1 {1 \choose k} x^{1 - k} \odot y^k$


Basis for the Induction

For $n = 2$ we have:

\(\displaystyle \odot^2 \left({x + y}\right)\) \(=\) \(\displaystyle \left({x + y}\right) \odot \left({x + y}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({x \odot x}\right) + \left({x \odot y}\right) + \left({y \odot x}\right) + \left({y \odot y}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle \left({x \odot x}\right) + 2 \left({x \odot y}\right) + \left({y \odot y}\right)\) $+$ is commutative in $R$
\(\displaystyle \) \(=\) \(\displaystyle \odot^2 x + 2 \left({\odot^1 x}\right) \odot \left({\odot^1 y}\right) + \odot^2 y\)
\(\displaystyle \) \(=\) \(\displaystyle \odot^2 x + {2 \choose 1} \left({\odot^{2-1} x}\right) \odot \left({\odot^1 y}\right) + \odot^2 y\)

This is the basis for the induction.


Induction Hypothesis

This is our inductive hypothesis:

$\displaystyle \forall n \ge 2: \odot^n \left({x + y}\right) = \odot^n x + \sum_{k \mathop = 1}^{n - 1} {n \choose k} \left({\odot^{n - k} x}\right) \odot \left({\odot^k y}\right) + \odot^n y$


Induction Step

This is the induction step:

\(\displaystyle \odot^{n + 1} \left({x + y}\right)\) \(=\) \(\displaystyle \left({x + y}\right) \odot \left({\odot^n \left({x + y}\right)}\right)\)
\(\displaystyle \) \(=\) \(\displaystyle x \odot \left({\odot^n x + \sum_{k \mathop = 1}^{n - 1} {n \choose k} \left({\odot^{n - k} x}\right) \odot \left({\odot^k y}\right) + \odot^n y}\right)\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle ~ y \odot \left({\odot^n x + \sum_{k \mathop = 1}^{n - 1} {n \choose k} \left({\odot^{n - k} x}\right) \odot \left({\odot^k y}\right) + \odot^n y}\right)\) Inductive Hypothesis
\(\displaystyle \) \(=\) \(\displaystyle \odot^{n + 1} x + \sum_{k \mathop = 1}^{n - 1} {n \choose k} \left({\odot^{n + 1 - k} x}\right) \odot \left({\odot^k y}\right) + x \odot \left({\odot^n y}\right)\)
\(\displaystyle \) \(\) \(\, \displaystyle + \, \) \(\displaystyle ~ y \odot \left({\odot^n x}\right) + \sum_{k \mathop = 1}^{n - 1} {n \choose k} \left({\odot^{n - k} x}\right) \odot \left({\odot^{k + 1} y}\right) + \odot^{n + 1} y\)
\(\displaystyle \) \(=\) \(\displaystyle \odot^{n + 1} x + \sum_{k \mathop = 1}^n {n \choose k} \left({\odot^{n + 1 - k} x}\right) \odot \left({\odot^k y}\right) + \sum_{k \mathop = 0}^{n - 1} {n \choose k} \left({\odot^{n - k} x}\right) \odot \left({\odot^{k + 1} y}\right) + \odot^{n + 1} y\)
\(\displaystyle \) \(=\) \(\displaystyle \odot^{n + 1} x + \sum_{k \mathop = 1}^n {n \choose k} \left({\odot^{n + 1 - k} x}\right) \odot \left({\odot^k y}\right) + \sum_{k \mathop = 1}^n {n \choose k - 1} \left({\odot^{n - k} x}\right) \odot \left({\odot^{k + 1} y}\right) + \odot^{n + 1} y\)
\(\displaystyle \) \(=\) \(\displaystyle \odot^{n + 1} x + \sum_{k \mathop = 1}^n {n + 1 \choose k} \left({\odot^{n + 1 - k} x}\right) \odot \left({\odot^k y}\right) + \odot^{n + 1} y\) Pascal's Rule

The result follows by the Principle of Mathematical Induction.

$\blacksquare$


Sources