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 \in A} \sum_{b \in B_a} t_{a,b} = \sum_{c \in \prod_{a \in A} B_a} \prod_{a \in A}t_{a,c_a} $

where the product of sets $\prod_{a \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 from $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

$\displaystyle A = \{ 1, 2 \} \wedge B_1 = \{ 1, 2 \} \wedge B_2 = \{ 1, 2 \} $
$\displaystyle \prod_{a \in A} \sum_{b \in B_a} t_{a,b} $
$\displaystyle = (t_{1,1}+t_{1,2}) (t_{2,1}+t_{2,2}) $
$\displaystyle = \sum_{c \in \prod_{a \in A} B_a} \prod_{a \in A}t_{a,c_a} $
$\displaystyle = \sum_{c \in \{(m, n) | m \in B_1 \wedge n \in B_2\}} t_{1,c_1}t_{2,c_2} $
$\displaystyle = \sum_{c \in \{(1,1),(1,2),(2,1),(2,2)\}} t_{1,c_1}t_{2,c_2} $
$\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 Rieman Zeta function.


Proof

For simplicity, let $A = \{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 $1..n$ as representing the actual elements.

Use induction on $n$ : For n = 1.

$\displaystyle \sum_{b \in B_1} t_{1,b} = \sum_{c \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 (\prod_{a \in \{1..n\}} \sum_{b \in B_a} t_{a,b})(\sum_{b \in B_{n+1}} t_{n+1,b}) = (\sum_{c \in \prod_{a \in \{1..n\}} B_a} \prod_{a \in \{1..n\}}t_{a,c_a}) (\sum_{b \in B_{n+1}} t_{n+1,b}) $

We need this result which we will prove below,

$\displaystyle (\sum_{c \in \prod_{a \in \{1..n\}} B_a} \prod_{a \in \{1..n\}}t_{a,c_a}) \sum_{b \in X_{n+1}} t_{n+1,b} = \sum_{c \in (\prod_{a \in \{1..n\}} B_a) \times X_{n+1}} \prod_{a \in \{1..n+1\}}t_{a,c_a}$

which gives,

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

This completes the induction case on $n$, but assuming,

$\displaystyle (\sum_{c \in \prod_{a \in \{1..n\}} B_a} \prod_{a \in \{1..n\}}t_{a,c_a}) \sum_{b \in X_{n+1}} t_{n+1,b} = \sum_{c \in (\prod_{a \in \{1..n\}} B_a) \times X_{n+1}} \prod_{a \in \{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 (\sum_{c \in \prod_{a \in \{1..n\}} B_a} \prod_{a \in \{1..n\}}t_{a,c_a}) t_{n+1,k} = \sum_{c \in (\prod_{a \in \{1..n\}} B_a) \times \{k\}} \prod_{a \in \{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.

$\displaystyle Z_{n+1} = X_{n+1} \cup Y_{n+1} $

Then:

$\displaystyle \sum_{b \in Z_{n+1}} t_{n+1,b} = (\sum_{b \in X_{n+1}} t_{n+1,b} + \sum_{b \in Y_{n+1}} t_{n+1,b}) $

Starting with the left hand side of the assumption,

$\displaystyle (\sum_{c \in \prod_{a \in \{1..n\}} B_a} \prod_{a \in \{1..n\}}t_{a,c_a}) \sum_{b \in Z_{n+1}} t_{n+1,b} $

Substituting for $Z_{n+1}$:

$\displaystyle = (\sum_{c \in \prod_{a \in \{1..n\}} B_a} \prod_{a \in \{1..n\}}t_{a,c_a}) (\sum_{b \in X_{n+1}} t_{n+1,b} + \sum_{b \in Y_{n+1}} t_{n+1,b}) $
$\displaystyle = (\sum_{c \in \prod_{a \in \{1..n\}} B_a} \prod_{a \in \{1..n\}}t_{a,c_a}) \sum_{b \in X_{n+1}} t_{n+1,b} + (\sum_{c \in \prod_{a \in \{1..n\}} B_a} \prod_{a \in \{1..n\}}t_{a,c_a}) \sum_{b \in Y_{n+1}} t_{n+1,b}$

Use the assumption for X and Y:

$\displaystyle = \sum_{c \in (\prod_{a \in \{1..n\}} B_a) \times X_{n+1}} \prod_{a \in \{1..n+1\}}t_{a,c_a} + \sum_{c \in (\prod_{a \in \{1..n\}} B_a) \times Y_{n+1}} \prod_{a \in \{1..n+1\}}t_{a,c_a}$

Merge the two summations into one:

$\displaystyle = \sum_{c \in ((\prod_{a \in \{1..n\}} B_a) \times X_{n+1} \cup (\prod_{a \in \{1..n\}} B_a)\times Y_{n+1})} \prod_{a \in \{1..n+1\}}t_{a,c_a}$

The cartesian product is:

$\displaystyle (\prod_{a \in \{1..n\}} B_a)\times X_{n+1} \cup (\prod_{a \in \{1..n\}} B_a)\times Y_{n+1}$

Use $ R\times P \cup R\times Q = R \times (P \cup Q)$ to give:

$\displaystyle = (\prod_{a \in \{1..n\}} B_a)\times (X_{n+1} \cup Y_{n+1})$

Use $ X_{n+1} \cup Y_{n+1} = Z_{n+1} $

$\displaystyle = (\prod_{a \in \{1..n\}} B_a)\times Z_{n+1}$

Substituting back in:

$\displaystyle \sum_{c \in ((\prod_{a \in \{1..n\}} B_a)\times X_{n+1} \cup (\prod_{a \in \{1..n\}} B_a)\times Y_{n+1})} \prod_{a \in \{1..n+1\}}t_{a,c_a} = \sum_{c \in (\prod_{a \in \{1..n\}} B_a)\times Z_{n+1}} \prod_{a \in \{1..n+1\}}t_{a,c_a}$

which is the right hand side of the assumption.

$\blacksquare$