Summation of Sum of Mappings on Finite Set

From ProofWiki
Jump to: navigation, search

Theorem

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

Let $S$ be a finite set.

Let $f, g: S \to \mathbb A$ be mappings.

Let $h = f + g$ be their sum.


Then we have the equality of summations on finite sets:

$\displaystyle \sum_{s \mathop \in S} h \left({s}\right) = \sum_{s \mathop \in S} f \left({s}\right) + \sum_{s \mathop \in S} g \left({s}\right)$


Outline of Proof

Using the definition of summation on a finite set, we reduce this to Indexed Summation of Sum of Mappings.


Proof

Let $n$ be the cardinality of $S$.

Let $\sigma: \N_{< n} \to S$ be a bijection, where $\N_{< n}$ is an initial segment of the natural numbers.

By definition of summation, we have to prove the following equality of indexed summations:

$\displaystyle \sum_{i \mathop = 0}^{n - 1} h \left({\sigma \left({i}\right)}\right) = \sum_{i \mathop = 0}^{n - 1} f \left({\sigma \left({i}\right)}\right) + \sum_{i \mathop = 0}^{n - 1} g \left({\sigma \left({i}\right)}\right)$

By Sum of Mappings Composed with Mapping, $h \circ \sigma = f \circ \sigma + g \circ \sigma$.

The above equality now follows from Indexed Summation of Sum of Mappings.

$\blacksquare$


Also see