Triangle Inequality for Indexed Summations
Jump to navigation
Jump to search
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$