Theorem: Product of Summations is Summation Over Cartesian Product of Products

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.
{{explain|In order to make this comprehensible, the precise nature of $A$ and $B$ need to be defined. Presumably $A$ is a set (of numbers?), and $B$ is a family of sets of numbers indexed by $A$? And the $t$s are elements of $B$ and are numbers? I'm having difficulty.}}

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:
{{begin-eqn}}
{{eqn | l = \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} }
      | r = \sum_{c \mathop \in \paren {\prod_{a \mathop = 1}^n B_a} \times B_{n + 1} } \prod_{a \mathop = 1}^{n + 1} t_{a, c_a}
      | c = 
}}
{{eqn | r = \sum_{c \mathop \in \prod_{a = 1}^{n + 1} B_a} \prod_{a \mathop = 1}^{n + 1} t_{a, c_a}
      | c = 
}}
{{end-eqn}}
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}$
{{explain|It is not clear from the above paragraph exactly what is being done}}
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:
{{begin-eqn}}
{{eqn | o = 
      | r = \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 Z_{n + 1} } t_{n + 1, b}
      | c = from {{LHS}} of assumption
}}
{{eqn | r = \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 X_{n + 1} } t_{n + 1, b} + \sum_{b \mathop \in Y_{n + 1} } t_{n + 1,b} }
      | c = substituting for $Z_{n + 1}$
}}
{{eqn | r = \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} + \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 Y_{n + 1} } t_{n + 1, b}
      | c = 
}}
{{eqn | r = \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} + \sum_{c \mathop \in \paren {\prod \limits_{a \mathop = 1}^n B_a} \times Y_{n + 1} } \prod_{a \mathop = 1}^{n + 1} t_{a, c_a}
      | c = using the assumption for $X$ and $Y$
}}
{{eqn | r = \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}
      | c = merging the two summations into one
}}
{{end-eqn}}
The cartesian product is:
{{begin-eqn}}
{{eqn | o = 
      | r = \paren {\prod_{a \mathop = 1}^n B_a} \times X_{n + 1} \cup \paren {\prod_{a \mathop = 1}^n B_a} \times Y_{n + 1}
      | c = 
}}
{{eqn | r = \paren {\prod_{a \mathop = 1}^n B_a} \times \paren {X_{n + 1} \cup Y_{n + 1} }
      | c = using $R \times P \cup R \times Q = R \times \paren {P \cup Q}$
}}
{{eqn | r = \paren {\prod_{a \mathop = 1}^n B_a} \times Z_{n + 1}
      | c = using $X_{n + 1} \cup Y_{n + 1} = Z_{n + 1}$
}}
{{end-eqn}}
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 {{RHS}} of the assumption.
{{qed}}
Category:Algebra
qbl85oec2smtnophlyv9yejrs2zrozi