Proof: Triangle Inequality

Table of Contents

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$ .

Readers who viewed this page, also viewed:

Author Profile

The Life

Proof: Triangle Inequality