General Distributivity Theorem

From ProofWiki
Jump to: navigation, search

Theorem

Let $\left({R, \circ, *}\right)$ be a ringoid.


Then for every pair of sequences $\left \langle {a_i} \right \rangle_{1 \le i \le m}, \left \langle {b_j} \right \rangle_{1 \le j \le n}$ of elements of $R$:

$\displaystyle \left({\sum_{i \mathop = 1}^m a_i}\right) * \left({\sum_{j \mathop = 1}^n b_j} \right) = \sum_{{1 \mathop \le i \mathop \le m} \atop {1 \mathop \le j \mathop \le n}} \left({a_i * b_j}\right)$

where:

$\displaystyle \sum_{i \mathop = 1}^m a_i$ is the summation $a_1 \circ a_2 \circ \cdots \circ a_m$
$m$ and $n$ are strictly positive integers: $m, n \in \Z_{> 0}$


Lemmata

The proof requires the following lemmata:

Lemma 1

Let $\left({R, \circ, *}\right)$ be a ringoid.

Then for every sequence $\left \langle {a_k} \right \rangle_{1 \mathop \le k \mathop \le n}$ of elements of $R$, and for every $b \in R$:

$\displaystyle \left({\sum_{j \mathop = 1}^n a_j}\right) * b = \sum_{j \mathop = 1}^n \left({a_j * b}\right)$


Lemma 2

Let $\struct {R, \circ, *}$ be a ringoid.

Then for every sequence $\sequence {a_k}_{1 \mathop \le k \mathop \le n}$ of elements of $R$, and for every $b \in R$:

$\displaystyle b * \paren {\sum_{j \mathop = 1}^n a_j} = \sum_{j \mathop = 1}^n \paren {b * a_j}$


Proof

Proof by induction:


For all $n \in \Z_{> 0}$, let $P \left({n}\right)$ be the proposition:

$\displaystyle \forall m \in \Z_{> 0}: \left({\sum_{i \mathop = 1}^m a_i}\right) * \left({\sum_{j \mathop = 1}^n b_j} \right) = \sum_{{1 \mathop \le i \mathop \le m} \atop {1 \mathop \le j \mathop \le n}} \left({a_i * b_j}\right)$


We have that $\left({R, \circ, *}\right)$ is a ringoid, and so:

$\forall a, b, c \in S: \left({a \circ b}\right) * c = \left({a * c}\right) \circ \left({b * c}\right)$
$\forall a, b, c \in R: a * \left({b \circ c}\right) = \left({a * b}\right) \circ \left({a * c}\right)$


Basis for the Induction

$P(1)$ is the case:

$\displaystyle \forall m \in \Z_{> 0}: \left({\sum_{i \mathop = 1}^m a_i}\right) * b_1 = \sum_{1 \mathop \le i \mathop \le m} \left({a_i * b_1}\right)$

This is demonstrated in Lemma 1.


This is our basis for the induction.


Induction Hypothesis

Now we need to show that, if $P \left({k}\right)$ is true, where $k \ge 2$, then it logically follows that $P \left({k+1}\right)$ is true.


So this is our induction hypothesis:

$\displaystyle \forall m \in \Z_{> 0}: \left({\sum_{i \mathop = 1}^m a_i}\right) * \left({\sum_{j \mathop = 1}^k b_j} \right) = \sum_{{1 \mathop \le i \mathop \le m} \atop {1 \mathop \le j \mathop \le k}} \left({a_i * b_j}\right)$


Then we need to show:

$\displaystyle \forall m \in \Z_{> 0}: \left({\sum_{i \mathop = 1}^m a_i}\right) * \left({\sum_{j \mathop = 1}^{k + 1} b_j} \right) = \sum_{{1 \mathop \le i \mathop \le m} \atop {1 \mathop \le j \mathop \le {k + 1}}} \left({a_i * b_j}\right)$


Induction Step

This is our induction step:

\(\displaystyle \left({\sum_{i \mathop = 1}^m a_i}\right) * \left({\sum_{j \mathop = 1}^{k + 1} b_j} \right)\) \(=\) \(\displaystyle \left({\sum_{i \mathop = 1}^m a_i}\right) * \left({\left({\sum_{j \mathop = 1}^k b_j} \right) \circ b_{k + 1} }\right)\) $\quad$ Definition of Summation $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({\sum_{i \mathop = 1}^m a_i}\right) * \left({\sum_{j \mathop = 1}^k b_j} \right)}\right) \circ \left({\left({\sum_{i \mathop = 1}^m a_i}\right) * b_{k + 1} }\right)\) $\quad$ as $\left({R, \circ, *}\right)$ is a ringoid $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \left({\left({\sum_{i \mathop = 1}^m a_i}\right) * \left({\sum_{j \mathop = 1}^k b_j} \right)}\right) \circ \sum_{1 \mathop \le i \mathop \le m} \left({a_i * b_{k+1} }\right)\) $\quad$ Basis for the Induction $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{{1 \mathop \le i \mathop \le m} \atop {1 \mathop \le j \mathop \le k}} \left({a_i * b_j}\right) \circ \sum_{1 \mathop \le i \mathop \le m} \left({a_i * b_{k+1} }\right)\) $\quad$ Induction Hypothesis $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{{1 \mathop \le i \mathop \le m} \atop {1 \mathop \le j \mathop \le {k + 1}}} \left({a_i * b_j}\right)\) $\quad$ Associativity of $\circ$ in $\left({R, \circ, *}\right)$ $\quad$


So $P \left({k}\right) \implies P \left({k+1}\right)$ and the result follows by the Principle of Mathematical Induction.


Therefore:

$\displaystyle \forall m, n \in \Z_{> 0}: \left({\sum_{i \mathop = 1}^m a_i}\right) * \left({\sum_{j \mathop = 1}^n b_j} \right) = \sum_{{1 \mathop \le i \mathop \le m} \atop {1 \mathop \le j \mathop \le n}} \left({a_i * b_j}\right)$

$\blacksquare$


The same result can be obtained by fixing $n$ and using induction on $m$, which requires Lemma 2 to be used for its base case.


Examples

Sum of $j$ from $m$ to $n$ by Sum of $k$ from $r$ to $s$

$\displaystyle \sum_{j \mathop = m}^n \sum_{k \mathop = r}^s j k = \frac 1 4 \left({n \left({n + 1}\right) - \left({m - 1}\right) m}\right) \left({s \left({s + 1}\right) - \left({r - 1}\right) r}\right)$

for $m \le n, r \le s$.


Warning

When using the General Distributivity Theorem, be careful not to conflate the indices.

The following is not a valid argument:

\(\displaystyle \left({\sum_{i \mathop = 1}^n a_i}\right) \left({\sum_{j \mathop = 1}^n \frac 1 {a_j} }\right)\) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \sum_{j \mathop = 1}^n \frac {a_i} {a_j}\) $\quad$ General Distributivity Theorem $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n \sum_{i \mathop = 1}^n \frac {a_i} {a_i}\) $\quad$ Change of Index Variable of Summation $\quad$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{i \mathop = 1}^n 1\) $\quad$ simplification $\quad$
\(\displaystyle \) \(=\) \(\displaystyle n\) $\quad$ $\quad$


Also see


Sources