Summation over Cartesian Product as Double Summation

From ProofWiki
Jump to: navigation, search

Theorem

Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.

Let $S, T$ be finite sets.

Let $S \times T$ be their cartesian product.

Then we have an equality of summations over finite sets:

$\displaystyle \sum_{s \mathop \in S} \sum_{t \mathop \in T} f \left({s, t}\right) = \sum_{\left({s, t}\right) \mathop \in S \times T} f \left({s, t}\right)$


Outline of proof

We use induction on the cardinality of $T$. In the induction step, we use Sum over Disjoint Union of Finite Sets and Summation of Sum of Mappings on Finite Set.


Proof


Also see