# Euclidean distance proof

How can I show that the Euclidean distance satisfies the triangle inequality?

Where the Euclidean distance is given by: $$d(p,q) = \sqrt{(p_1-q_1)^2 + \cdots + (p_n-q_n)^2}$$

Triangle Inequality: $\forall x,y,z\Bigl( d(x,z) \leq d(x,y) + d(y,z)\Bigr)$.

Let ${\bf p} = (p_1,\dots,p_n)$ and ${\bf q}=(q_1,\dots,q_n)$. Recall that ${\bf p \cdot q} = p_1q_1 + \cdots + p_nq_n$ and $|{\bf p}|=\sqrt{{\bf p \cdot p}}$ and finally $d({\bf p}, {\bf q})=|{\bf p}-{\bf q}|$.

First, let's establish the Cauchy-Schwarz inequality: $|{\bf p \cdot q}| \leq |{\bf p}| |{\bf q}|$.

Consider $|{\bf p}-c{\bf q}|^2 = ({\bf p}-c{\bf q}) {\bf \cdot} ({\bf p}-c{\bf q}) = c^2 {\bf q \cdot q} - 2c {\bf p \cdot q} + {\bf p \cdot p}=|{\bf q}|^2c^2-2({\bf p\cdot q})c+|{\bf p}|^2$.

This is a quadratic in $c$ and since $|{\bf p}-c{\bf q}|^2 \geq 0$ we have $|{\bf q}|^2c^2-2({\bf p\cdot q})c+|{\bf p}|^2 \geq 0$. Thus this quadratic either has a repeated real root or complex roots. Thus its discriminant is non-positive. So $(-2({\bf p \cdot q}))^2-4|{\bf q}|^2|{\bf p}|^2 \leq 0$. This means $4({\bf p\cdot q})^2 \leq 4|{\bf q}|^2|{\bf p}|^2$. Canceling the 4's and taking square roots give us the required result.

Use Cauchy-Schwarz as follows: $|{\bf p}+{\bf q}|^2=({\bf p}+{\bf q}){\bf \cdot}({\bf p}+{\bf q})=|{\bf p}|^2+2({\bf p\cdot q})+|{\bf q}|^2 \leq |{\bf p}|^2+2|{\bf p\cdot q}|+|{\bf q}|^2$ $\leq |{\bf p}|^2+2|{\bf p}||{\bf q}|+|{\bf q}|^2=(|{\bf p}|+|{\bf q}|)^2$. This gives you $|{\bf p}+{\bf q}| \leq |{\bf p}|+|{\bf q}|$.

Now consider 3 points ${\bf p}$, ${\bf q}$, and ${\bf r}$. $d({\bf p}, {\bf r})=|{\bf p}-{\bf r}|=|{\bf p}-{\bf q}+{\bf q}-{\bf r}| \leq |{\bf p}-{\bf q}| + |{\bf q}-{\bf r}|=d({\bf p},{\bf q})+d({\bf q},{\bf r})$

• Could you please explain the line "Thus this quadratic either has a repeated real root or complex roots." It is not obvious to me. – R_D Aug 29 at 4:53
• $0 \leq |p-cq|^2 = Ac^2+Bc+C$ where $A,B,C$ are the numbers $A=|q|^2$, $B=-2p.q$, and $C=|p|^2$. Notice we have a quadratic $Ax^2+Bx+C \geq 0$ here. So if you draw the graph of $y=Ax^2+Bx+C$, the parabola can at most bounce off of the $x$-axis (if =0) and otherwise is strictly above the $x$-axis (where >0). Such a quadratic cannot have distinct real roots. If it hits 0 at one point, it must have a repeated real root. If it never hits 0, it must have complex roots. These two cases occur (remembering the quadratic formula) when $B^2-4AC \leq 0$ – Bill Cook Aug 29 at 14:17