# Proof: Triangle Inequality

Let’s prove $$|PR| \leq |PQ| + |QR|$$ for the destances among 3 points $$P, Q, R \in \mathbb{R}^n$$.

Denote $$P$$ by $$(p_1, \cdots , p_n )$$, $$Q$$ by $$(q_1, \cdots , q_n )$$, $$R$$ by $$(r_1, \cdots , r_n )$$ .

## When $$n=1$$

Let’s show $$\sqrt{(r_1-p_1)^2} – \sqrt{(q_1 – p_1)^2} – \sqrt{(r_1 – q_1)^2} \leq 0$$ . This expression is symmetry for $$p_1, r_1$$, then suppose $$p_1 \leq r_1$$ .

### If $$q_1 \lt p_1 \leq r_1$$

\begin{eqnarray} && \sqrt{(r_1-p_1)^2} – \sqrt{(q_1 – p_1)^2} – \sqrt{(r_1 – q_1)^2}\\ &=& (r_1 – p_1) – (p_1 – q_1) – (r_1 – q_1) \\ &=& -2p_1+2q_1 \\ &\leq&0 \end{eqnarray}

### If $$p_1 \leq q_1 \leq r_1$$

\begin{eqnarray} && \sqrt{(r_1-p_1)^2} – \sqrt{(q_1 – p_1)^2} – \sqrt{(r_1 – q_1)^2}\\ &=& (r_1 – p_1) – (q_1 – p_1) – (r_1 – q_1) \\ &=& 0 \end{eqnarray}

### If $$p_1 \leq r_1 \lt q_1$$

\begin{eqnarray} && \sqrt{(r_1-p_1)^2} – \sqrt{(q_1 – p_1)^2} – \sqrt{(r_1 – q_1)^2}\\ &=& (r_1 – p_1) – (q_1 – p_1) – (q_1 – r_1) \\ &=& 2r_1-2q_1 \\ &\lt&0 \end{eqnarray}

## When $$0 \lt n$$

Suppose the triangle inequality for $$n = k$$.

Then,

$\sqrt{\sum_{l=1}^{k} (r_l – p_l)^2} \leq \sqrt{\sum_{l=1}^{k} (q_l – p_l)^2} – \sqrt{\sum_{l=1}^{k} (r_l – q_l)^2} .$

So,

\begin{eqnarray}\begin{split}\sum_{l=1}^{k} (r_l – p_l)^2 & \leq &\left(\sqrt{\sum_{l=1}^{k} (q_l – p_l)^2} + \sqrt{\sum_{l=1}^{k} (r_l – q_l)^2} \right)^2 \\ & \leq& \sum_{l=1}^{k} (q_l – p_l)^2 + \sum_{l=1}^{k} (r_l – q_l)^2\\&& + 2 \sqrt{\sum_{l=1}^k (q_l-p_l)^2} \sqrt{ \sum_{l=1}^k (r_j-q_j)^2}.\end{split}\end{eqnarray}

Now, let’s prove

$\left(\sqrt{\sum_{l=1}^{k+1} (r_l – p_l)^2}\right)^2 – \left(\sqrt{\sum_{l=1}^{k} (q_l – p_l)^2}+\sqrt{\sum_{l=1}^{k} (r_l – q_l)^2}\right)^2 \leq 0 .$

With the inequation for $$n=k$$ and one for $$n=1$$, the expression can be writte as follows.

\begin{eqnarray}\begin{split} & & \left(\sqrt{\sum_{l=1}^{k+1} (r_l – p_l)^2}\right)^2 – \left(\sqrt{\sum_{l=1}^{k} (q_l – p_l)^2}+\sqrt{\sum_{l=1}^{k} (r_l – q_l)^2}\right)^2 \\ & \leq & (r_{k+1}-p_{k+1})^2 – (q_{k+1}-p_{k+1})^2 – (r_{k+1}-q_{k+1})^2 \\ && \quad – 2 \sqrt{\sum_{l = 1}^{k+1} (q_l-p_l)^2}\sqrt{\sum_{l = 1}^{k+1} (r_j-q_j)^2}\\ && \quad + 2 \sqrt{\sum_{l = 1}^{k} (q_l-p_l)^2}\sqrt{\sum_{l = 1}^{k} (r_l-q_l)^2}\\ &\leq& 2 \sqrt{(q_{k+1} – p_{k+1})^2 (r_{k+1} – q_{k+1})^2}\\ && \quad – 2 \sqrt{\sum_{l = 1}^{k+1} (q_l-p_l)^2} \sqrt{\sum_{l = 1}^{k+1} (r_j-q_j)^2}\\ && \quad + 2 \sqrt{\sum_{l = 1}^{k} (q_l-p_l)^2} \sqrt{\sum_{l = 1}^{k} (r_l-q_l)^2}. \end{split}\end{eqnarray}

Now, define $$A_k$$, $$B_k$$, $$C_k$$, $$D_k$$ as follows.

\begin{eqnarray} A_k &=&(q_{k+1} – p_{k+1})^2 \\ B_k&=&(r_{k+1} – q_{k+1})^2\\ C_k &=& \sum_{l=1}^k (q_l-p_l)^2\\ D_k&=&\sum_{l=1}^{k} (r_l-q_l)^2 \end{eqnarray}

With these $$A, B, C, D$$, the last inequation is writte n as:

$2\sqrt{A_k B_k} – 2\sqrt{(A_k+C_k)(B_k+D_k)} + 2\sqrt{B_k D_k}.$

To prove

$\sqrt{A_k B_k} – \sqrt{(A_k+C_k)(B_k+D_k)} + \sqrt{B_k D_k} \leq 0$

prove

$\left(\sqrt{A_k B_k}+\sqrt{B_k D_k}\right)^2 \leq \sqrt{(A_k+C_k)(B_k+D_k)}^2 .$ \begin{eqnarray}\begin{split} && \left(\sqrt{A_k B_k}+\sqrt{B_k D_k}\right)^2 – \sqrt{(A_k+C_k)(B_k+D_k)}^2\\ &\leq& A_k B_k + B_k D_k + 2\sqrt{A_k B_k C_k D_k}\\&&\quad – A_k B_k – C_k D_k – A_k D_k – B_k D_k\\ &=&2\sqrt{A_k B_k C_k D_k} – A_k D_k – B_k C_k \\ &=& – \left( \sqrt{A_k D_k} – \sqrt{B_k C_k} \right)^2\\ &\leq&0 \end{split} \end{eqnarray}

Thus, the inequation is also true for $$n=k+1$$.