Triangle Inequality for Summation over Finite Set

From ProofWiki
Jump to navigation Jump to 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 : S \to \mathbb A$ be a mapping.

Let $\size {\, \cdot\,}$ denote the standard absolute value.

Let $\size f$ be the absoute value of $f$.


Then we have the inequality of summations on finite sets:

$\ds \size {\sum_{s \mathop \in S} \map f s} \le \sum_{s \mathop \in S} \size {\map f s}$


Outline of Proof

Using the definition of summation, we reduce this to Triangle Inequality for Indexed Summations.


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 inequality of indexed summations:

$\ds \size {\sum_{i \mathop = 0}^{n - 1} \map f {\map \sigma i} } \le \sum_{i \mathop = 0}^{n - 1} \map {\paren {\size f \circ \sigma} } i$

By Absolute Value of Mapping Composed with Mapping:

$\size f \circ \sigma = \size {f \circ \sigma}$

The above equality now follows from Triangle Inequality for Indexed Summations.

$\blacksquare$


Also see