Norm of Summation
Jump to navigation
Jump to search
Theorem
Let $\struct {X, \norm \cdot}$ be a normed vector space.
Let $\sequence {x_n}_{n \mathop \in \N}$ be a sequence in $X$.
Then:
- $\ds \norm {\sum_{k \mathop = 1}^n x_k} \le \sum_{k \mathop = 1}^n \norm {x_k}$ for all $n \in \N$.
Proof
The proof proceeds by induction.
For each $n \in \N$, let $\map P n$ be the proposition:
- $\ds \norm {\sum_{k \mathop = 1}^n x_k} \le \sum_{k \mathop = 1}^n \norm {x_k}$ for all $n \in \N$.
Basis for the Induction
$\map P 1$ is the case:
- $\ds \norm {\sum_{k \mathop = 1}^1 x_k} \le \sum_{k \mathop = 1}^1 \norm {x_k}$
This is immediate, since:
- $\ds \norm {\sum_{k \mathop = 1}^1 x_k} = \norm {x_1}$
and:
- $\ds \sum_{k \mathop = 1}^1 \norm {x_k} = \norm {x_1}$
Thus $\map P 1$ is seen to hold.
This is the basis for the induction.
Induction Hypothesis
Now it needs to be shown that if $\map P n$ is true, where $n \ge 1$, then it logically follows that $\map P {n + 1}$ is true.
So this is the induction hypothesis:
- $\ds \norm {\sum_{k \mathop = 1}^n x_k} \le \sum_{k \mathop = 1}^n \norm {x_k}$
from which it is to be shown that:
- $\ds \norm {\sum_{k \mathop = 1}^{n + 1} x_k} \le \sum_{k \mathop = 1}^{n + 1} \norm {x_k}$
Induction Step
This is the induction step:
We have:
\(\ds \norm {\sum_{k \mathop = 1}^{n + 1} x_k}\) | \(=\) | \(\ds \norm {x_{n + 1} + \sum_{k \mathop = 1}^n x_k}\) | ||||||||||||
\(\ds \) | \(\le\) | \(\ds \norm {x_{n + 1} } + \norm {\sum_{k \mathop = 1}^n x_k}\) | using the triangle equality for norms | |||||||||||
\(\ds \) | \(\le\) | \(\ds \norm {x_{n + 1} } + \sum_{k \mathop = 1}^n \norm {x_k}\) | using the induction hypothesis | |||||||||||
\(\ds \) | \(=\) | \(\ds \sum_{k \mathop = 1}^{n + 1} \norm {x_k}\) |
So $\map P n \implies \map P {n + 1}$ and the result follows by the Principle of Mathematical Induction.
$\blacksquare$