Triangle Inequality for Indexed Summations

Theorem

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

Let $a,b$ be integers.

Let $\closedint a b$ denote the integer interval between $a$ and $b$.

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

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

Let $\vert f \vert$ be the absolute value of $f$.

Then we have the inequality of indexed summations:

$\ds \size {\sum_{i \mathop = a}^b \map f i} \le \sum_{i \mathop = a}^b \size {\map f i}$

Proof

The proof goes by induction on $b$.

Basis for the Induction

Let $b < a$.

Then all indexed summations are zero.

Because $\size 0 \le \size 0$ by definition of the standard absolute value, the result follows.

This is our basis for the induction.

Induction Step

Let $b \geq a$.

We have:

\(\ds \size {\sum_{i \mathop = a}^b \map f i}\)

\(=\)

\(\ds \size {\sum_{i \mathop = a}^{b - 1} \map f i + \map f b}\)

Definition of Indexed Summation

\(\ds \)

\(\leq\)

\(\ds \size {\sum_{i \mathop = a}^{b - 1} \map f i} + \size {\map f b}\)

Triangle Inequality

\(\ds \)

\(\leq\)

\(\ds \sum_{i \mathop = a}^{b - 1} \size {\map f i} + \size {\map f b}\)

Induction Hypothesis, Definition of Relation Compatible with Operation

\(\ds \)

\(=\)

\(\ds \sum_{i \mathop = a}^b \size {\map f i}\)

Definition of Indexed Summation

By the Principle of Mathematical Induction, the proof is complete.

$\blacksquare$

Also see

• Triangle Inequality for Summation over Finite Set
• Triangle Inequality for Series