Proving the triangle inequality for the $l_2$ norm $\|x\|_2 = \sqrt{x_1^2+x_2^2+\ldots+x_n^2}$

Question

I want to prove the triangle inequality for the $l_2$-norm $\|x\|_2$: $$\|x\|_2 = \sqrt{x_1^2+x_2^2+\ldots+x_n^2}$$

---

\begin{align} \sqrt {\sum_{i=1}^n (x_i + y_i)^2 } &\leqslant \sqrt {\sum_{i=1}^n x_i^2} + \sqrt {\sum_{i=1}^n y_i^2} \\ \sum_{i=1}^n {(x_i + y_i)}^2 &\leqslant \sum_{i=1}^n x_i^2 + 2\sqrt {\sum_{i=1}^n x_i^2} \sqrt {\sum_{i=1}^n y_i^2 } + \sum_{i=1}^n y_i^2 \\ \sum_{i=1}^n (x_i^2 + 2x_i y_i + y_i^2) &\leqslant \sum_{i=1}^n x_i^2 + 2\sqrt {\sum_{i=1}^n x_i^2 } \sqrt {\sum_{i=1}^n y_i^2 } + \sum_{i=1}^n y_i^2 \\ \sum_{i=1}^n x_i^2 + \sum_{i=1}^n y_i^2 + 2\sum_{i=1}^n x_i y_i &\leqslant \sum_{i=1}^n x_i^2 + \sum_{i=1}^n y_i^2 + 2\sqrt {\sum_{i=1}^n x_i^2 } \sqrt {\sum_{i=1}^n {y_i^2} } \\ \sum_{i=1}^n x_i y_i &\leqslant \sqrt {\sum_{i=1}^n x_i^2 } \sqrt {\sum_{i=1}^n y_i^2 } \end{align} After this I squared both sides and multiplied out. It gets really messy, and then I got stuck. I think you have to realize some factorization and then conclude $0\leq$ some terms.

How do I finish this proof? All help is greatly appreciated!

Answer 1

You want to prove that $$\lVert x+y\rVert \leq \lVert x\rVert+\lVert y\rVert$$

We use $\langle x,y\rangle$ to denote the inner (dot) product $$x\cdot y=\sum_{k=1}^n x_ky_k$$ Note that $$\lVert x+y\rVert ^2=\lVert x\rVert^2+2\langle x,y\rangle+\lVert y\rVert ^2$$

Continuing, use the Cauchy-Schwarz inequality, you get $$\lVert x\rVert^2+2\langle x,y\rangle+\lVert y\rVert ^2\leq \lVert x\rVert^2+2 \lVert x\rVert \cdot \lVert y\rVert +\lVert y\rVert ^2=\left(\lVert x\rVert+\lVert y\rVert\right)^2 $$ and since all is positive, we can obtain your inequality by taking square roots. The last equation you got is almost $$|\langle x,y\rangle|\leq \lVert x\rVert \cdot \lVert y\rVert $$

which is known as the Cauchy-Schwarz inequality. The Cauchy-Schwarz inequality is true for any inner product space, and here you have the canonical proof. Your inequality is a particular case of the Minkowski inequality for $L_p$ norms.

ADD To clear out the proof in Wikiepdia

Recall that the nature of roots of the polynomial $aX^2+bX+c$ are intimately related to its discriminant: $\Delta=b^2-4ac$ which appears in the formula $$X=\frac{-b\pm\sqrt{\Delta}}{2a}$$

If a quadratic polynomial is proven to satisfy $p(X)\geq 0$ then $\Delta \leq 0$: either there is one real root $\Delta=0$ or there are no real roots ($\Delta<0$) because the square root of the negative discriminant will give rise to complex numbers.

Answer 2

I did exactly what you did above. That was actually a very good proof--better than using $u$ and $v$ since it is more abstract, hence more generalized than the latter one. You should proceed with your work, for you are almost there.

To continue with what you wrote above, you should notice that the left side of the very last equation you got is the inner product of vector $x$ and vector $y$: ${}=x^\text Ty=\|x\|\,\|y\|\cos(\theta)$ where $\theta$ is the angle between $x$ and $y$. Now $\cos(\theta)$ is always less than or equal to 1. Hence you have the inequality. Hope this helps.