Sum over Union of Finite Sets

Theorem

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

Let $S$ and $T$ be finite sets.

Let $f: S \cup T \to \mathbb A$ be a mapping.

Then we have the equality of summations over finite sets:

$\ds \sum_{u \mathop \in S \mathop \cup T} \map f u = \sum_{s \mathop \in S} \map f s + \sum_{t \mathop \in T} \map f t - \sum_{v \mathop \in S \mathop \cap T} \map f v$

Proof

Follows from:

Mapping Defines Additive Function of Subalgebra of Power Set

Power Set is Algebra of Sets

Inclusion-Exclusion Principle

$\blacksquare$

Also see

• Inclusion-Exclusion Principle