Product of Summations is Summation Over Cartesian Product of Products

From ProofWiki
Jump to navigation Jump to search

Theorem

This is a generalization of the distributive law:

$\displaystyle \prod_{a \mathop \in A} \sum_{b \mathop \in B_a} t_{a, b} = \sum_{c \mathop \in \prod_{a \mathop \in A} B_a} \prod_{a \mathop \in A} t_{a, c_a}$

where the product of sets $\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:

\(\displaystyle A\) \(=\) \(\displaystyle \set {1, 2}\)
\(\displaystyle B_1\) \(=\) \(\displaystyle \set {1, 2}\)
\(\displaystyle B_2\) \(=\) \(\displaystyle \set {1, 2}\)


Then:

\(\displaystyle \prod_{a \mathop \in A} \sum_{b \mathop \in B_a} t_{a, b}\) \(=\) \(\displaystyle \paren {t_{1, 1} + t_{1, 2} } \paren {t_{2, 1} + t_{2, 2} }\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{c \mathop \in \prod_{a \mathop \in A} B_a} \prod_{a \mathop \in A} t_{a, c_a}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{c \mathop \in \set {\tuple {m, n}: m \mathop \in B_1 \land n \mathop \in B_2} } t_{1, c_1} t_{2, c_2}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{c \mathop \in \set {\tuple {1, 1}, \tuple {1, 2}, \tuple {2, 1}, \tuple {2, 2} } } t_{1, c_1} t_{2, c_2}\)
\(\displaystyle \) \(=\) \(\displaystyle t_{1, 1} t_{2, 1} + t_{1, 1} t_{2, 2} + t_{1, 2} t_{2, 1} + t_{1, 2} t_{2, 2}\)


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$:

$\displaystyle \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$.

$\displaystyle \paren {\prod_{a \mathop \in \closedint 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_{a \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 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,

$\displaystyle \paren {\sum_{c \mathop \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} = \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$

which gives:

\(\displaystyle \paren {\prod_{a \mathop \in \closedint 1 n} \sum_{b \mathop \in B_a} t_{a, b} } \paren {\sum_{b \mathop \in B_{n + 1} } t_{n + 1, b} }\) \(=\) \(\displaystyle \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times B_{n + 1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{c \mathop \in \prod_{a \in \closedint 1 {n + 1} } B_a} \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}\)


This completes the induction case on $n$ while assuming:

$\displaystyle \paren {\sum_{c \mathop \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} = \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} } \prod_{a \mathop \in \closedint 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:

$\displaystyle \paren {\sum_{c \mathop \in \prod_{a \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } t_{n + 1, k} = \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times \set k} \prod_{a \mathop \in \closedint 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:

$\displaystyle \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:

\(\displaystyle \) \(\) \(\displaystyle \paren {\sum_{c \mathop \in \prod_{a \mathop \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \mathop \in Z_{n + 1} } t_{n + 1, b}\) from left hand side of assumption
\(\displaystyle \) \(=\) \(\displaystyle \paren {\sum_{c \in \prod_{a \mathop \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 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} }\) substituting for $Z_{n + 1}$
\(\displaystyle \) \(=\) \(\displaystyle \paren {\sum_{c \in \prod_{a \mathop \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \mathop \in X_{n + 1} } t_{n + 1, b} + \paren {\sum_{c \mathop \in \prod_{a \mathop \in \closedint 1 n} B_a} \prod_{a \mathop \in \closedint 1 n} t_{a, c_a} } \sum_{b \in Y_{n + 1} } t_{n + 1, b}\)
\(\displaystyle \) \(=\) \(\displaystyle \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a} + \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Y_{n + 1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}\) using the assumption for $X$ and $Y$
\(\displaystyle \) \(=\) \(\displaystyle \sum_{c \mathop \in \paren {\paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} \mathop \cup \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Y_{n + 1} } } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}\) merging the two summations into one


The cartesian product is:

\(\displaystyle \) \(\) \(\displaystyle \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} \cup \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Y_{n + 1}\)
\(\displaystyle \) \(=\) \(\displaystyle \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times \paren {X_{n + 1} \cup Y_{n + 1} }\) using $R \times P \cup R \times Q = R \times \paren {P \cup Q}$
\(\displaystyle \) \(=\) \(\displaystyle \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Z_{n + 1}\) using $X_{n + 1} \cup Y_{n + 1} = Z_{n + 1}$


Substituting back in:

$\displaystyle \sum_{c \mathop \in \paren {\paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times X_{n + 1} \mathop \cup \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Y_{n + 1} } } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a,c_a} = \sum_{c \mathop \in \paren {\prod_{a \mathop \in \closedint 1 n} B_a} \times Z_{n+1} } \prod_{a \mathop \in \closedint 1 {n + 1} } t_{a, c_a}$

which is the right hand side of the assumption.

$\blacksquare$