Product of Summations is Summation Over Cartesian Product of Products

== Theorem ==
This is a generalization of the distributive law:
:$\ds \prod_{a \mathop \in A} \sum_{b \mathop \in B_a} t_{a, b} = \sum_{c \mathop \in \prod \limits_{a \mathop \in A} B_a} \prod_{a \mathop \in A} t_{a, c_a}$
where the product of sets $\ds \prod_{a \mathop \in A} B_a$ is taken to be a cartesian product.
== Definition of Terms ==
In its simplest form $A$ is a range of positive natural numbers in $\closedint 1 n$.
$B$ is vector of sets, indexed by the elements of $A$.
$A$ also indexes elements of the cartesian product which are n-tuples.
The sets $B_a$ are finite sets, usually of integers.
These form the indexes of summation.
However in its usage in Product Form of Sum on Completely Multiplicative Function, $A$ may not be consecutive integers.
In that usage, $A$ are primes.
An extra level of abstraction is required, to map from the elements of a set to consecutive positive natural numbers that index the n-tuples formed from the Cartesian products.
== Cartesian Products ==
To be continued.
== Example ==
Let:
Then:
== Usage ==
Used in the derivation of the Euler product expression for the Riemann Zeta function.
== Proof ==
For simplicity, let $A = \closedint 1 n$.
This reduces the complexity without loss of generality, as if we wanted to use an arbitrary set we could store the actual elements in an $n$-tuple and index them.
So we can think of $\closedint 1 n$ as representing the actual elements.
Use induction on $n$:
For $n = 1$:
:$\ds \sum_{b \mathop \in B_1} t_{1, b} = \sum_{c \mathop \in B_1} t_{1, c}$
which is true, proving the case.
Assume the formula is true for $n$, and prove it for $n + 1$.
:$\ds \paren {\prod_{a \mathop = 1}^n \sum_{b \mathop \in B_a} t_{a, b} } \paren {\sum_{b \mathop \in B_{n + 1} } t_{n + 1, b} } = \paren {\sum_{c \mathop \in \prod \limits_{a \mathop = 1}^n B_a} \prod_{a \mathop = 1}^n t_{a, c_a} } \paren {\sum_{b \mathop \in B_{n + 1} } t_{n + 1, b} }$
We need this result which we will prove below,
:$\ds \paren {\sum_{c \mathop \in \prod \limits_{a \mathop = 1}^n B_a} \prod_{a \mathop = 1}^n t_{a, c_a} } \sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} = \sum_{c \mathop \in \paren {\prod \limits_{a \mathop = 1}^n B_a} \times X_{n + 1} } \prod_{a \mathop = 1}^{n + 1} t_{a, c_a}$
which gives:
This completes the induction case on $n$ while assuming:
:$\ds \paren {\sum_{c \mathop \in \prod \limits_{a \mathop = 1}^n B_a} \prod_{a \mathop = 1}^n t_{a, c_a} } \sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} = \sum_{c \mathop \in \paren {\prod \limits_{a \mathop = 1}^n B_a} \times X_{n + 1} } \prod_{a \mathop = 1}^{n + 1} t_{a, c_a}$
To prove this, use induction on the size $X_{n + 1}$.
If $X_{n + 1}$ has a single element:
:$\ds \paren {\sum_{c \mathop \in \prod \limits_{a \mathop = 1}^n B_a} \prod_{a \mathop = 1}^n t_{a, c_a} } t_{n + 1, k} = \sum_{c \mathop \in \paren {\prod \limits_{a \mathop = 1}^n B_a} \times \set k} \prod_{a \mathop = 1}^{n + 1} t_{a, c_a}$
which is true, proving the case for size $1$.
Now assume it is true for $X_{n + 1}$ and $Y_{n + 1}$ we will prove it for $Z_{n + 1}$.
This corresponds to the induction step if the size of $Y_{n + 1}$ is $1$.
So all we are doing is proving a more general case.
We do this because $X_{n + 1}$ and $Y_{n + 1}$ are then symmetrical, and so the proof is easier to understand.
:$Z_{n + 1} = X_{n + 1} \cup Y_{n + 1}$
Then:
:$\ds \sum_{b \mathop \in Z_{n + 1} } t_{n + 1, b} = \paren {\sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} + \sum_{b \mathop \in Y_{n + 1} } t_{n + 1, b} }$
Thus:
The cartesian product is:
Substituting back in:
:$\ds \sum_{c \mathop \in \paren {\paren {\prod \limits_{a \mathop = 1}^n B_a} \times X_{n + 1} \mathop \cup \paren {\prod \limits_{a \mathop = 1}^n B_a} \times Y_{n + 1} } } \prod_{a \mathop = 1}^{n + 1} t_{a,c_a} = \sum_{c \mathop \in \paren {\prod \limits_{a \mathop = 1}^n B_a} \times Z_{n + 1} } \prod_{a \mathop = 1}^{n + 1} t_{a, c_a}$
which is the of the assumption.
Category:Algebra