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{array}{rcl} \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}) \\ = & - 2 p_{1} + 2 q_{1} \\ \leq & 0 \end{array}

$\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{array}{rcl} \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{array}

$\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{array}{rcl} \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}) \\ = & 2 r_{1} - 2 q_{1} \\ < & 0 \end{array}

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

$\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{array}{rcl} \begin{aligned} \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}})}^{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{aligned} \end{array}

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

{(\sqrt{\sum_{l = 1}^{k + 1} (r_{l} - p_{l})^{2}})}^{2} - {(\sqrt{\sum_{l = 1}^{k} (q_{l} - p_{l})^{2}} + \sqrt{\sum_{l = 1}^{k} (r_{l} - q_{l})^{2}})}^{2} \leq 0 .

$\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{array}{rcl} \begin{aligned} {(\sqrt{\sum_{l = 1}^{k + 1} (r_{l} - p_{l})^{2}})}^{2} - {(\sqrt{\sum_{l = 1}^{k} (q_{l} - p_{l})^{2}} + \sqrt{\sum_{l = 1}^{k} (r_{l} - q_{l})^{2}})}^{2} \\ \leq & (r_{k + 1} - p_{k + 1})^{2} - (q_{k + 1} - p_{k + 1})^{2} - (r_{k + 1} - q_{k + 1})^{2} \\ - 2 \sqrt{\sum_{l = 1}^{k + 1} (q_{l} - p_{l})^{2}} \sqrt{\sum_{l = 1}^{k + 1} (r_{j} - q_{j})^{2}} \\ + 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}} \\ - 2 \sqrt{\sum_{l = 1}^{k + 1} (q_{l} - p_{l})^{2}} \sqrt{\sum_{l = 1}^{k + 1} (r_{j} - q_{j})^{2}} \\ + 2 \sqrt{\sum_{l = 1}^{k} (q_{l} - p_{l})^{2}} \sqrt{\sum_{l = 1}^{k} (r_{l} - q_{l})^{2}} . \end{aligned} \end{array}

$\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{array}{rcl} 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{array}

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

$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

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

prove

{(\sqrt{A_{k} B_{k}} + \sqrt{B_{k} D_{k}})}^{2} \leq {\sqrt{(A_{k} + C_{k}) (B_{k} + D_{k})}}^{2} .

$\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{array}{rcl} \begin{aligned} {(\sqrt{A_{k} B_{k}} + \sqrt{B_{k} D_{k}})}^{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}} \\ - 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} \\ = & - {(\sqrt{A_{k} D_{k}} - \sqrt{B_{k} C_{k}})}^{2} \\ \leq & 0 \end{aligned} \end{array}

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