Change of Variables in Summation over 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$ and $T$ be finite sets.

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

Let $g: T \to S$ be a bijection.


Then we have an equality of summations over finite sets:

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


Proof

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

Let $\N_{<n}$ be an initial segment of the natural numbers.

Let $h : \N_{<n} \to T$ be a bijection.

By definition of summation:

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

By Composite of Bijections is Bijection, the composition $g \circ h : \N_{<n} \to S$ is a bijection.

By definition of summation:

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

$\blacksquare$


Also see