How can I use induction to prove the Triangle inequality?

Question

By using induction, I want to prove the following:

$||x_{1} + ... + x_{k}|| \leqq ||x_{1}|| + ... + ||x_{k}||$

with $(x_{1}, ... , x_{k}) \in R^{n}$

I started with:

$||x_{1} + ... + x_{k} + x_{k+1}|| \leqq ||x_{1}|| + ... + ||x_{k}|| + ||x_{k+1}||$

But, I'm not sure how to proceed, as I don't know how I should manipulate the terms inside the determinant symbols.

Answer 1

Notice The base case just states that $||x_1+x_2 || \leq ||x_1|| + ||x_2||$. Assume

$$ || x_1 + ... + x_n || \leq ||x_1|| + ... + ||x_n|| $$

We want to show that same when $n+1$. But,

$$ || x_1 + ... + x_n + x_{n+1} || = || (x_1 + ... + x_n) + x_{n+1} ||$$

Now apply the base case to the elements $X = x_1 + ... + x_n$ and $Y = x_{n+1}$. So we have

$$ || X + Y || \leq || X|| + ||Y|| $$

hence,

$$ || x_1 + ... + x_n + x_{n+1} || \leq ||x_1 + ... + x_n|| + ||x_{n+1}|| $$

Using the induction hypothesis, one has

$$ || x_1 + ... + x_n + x_{n+1} || \leq ||x_1 + ... + x_n|| + ||x_{n+1}|| \leq ||x_1|| + ... + ||x_n|| + || x_{n+1} || $$

and the result is proved.