How to prove $|x_i - x_j| \geq |y_i - y_j| - 2 ||x - y||_\infty $

Question

Let $x$ and $y$ be two real vectors of length $n$. Let subscripts $i$ and $j$ denote the $i$-th and $j$-th elements of a vector.

How can we prove $$|x_i - x_j| \geq |y_i - y_j| - 2 ||x - y||_\infty $$

for any $i$ and $j$. Here, $|| x ||_\infty = \max_{1 \leq i \leq n}|x_i|$.

Thanks.

Answer 1

You just have to add "zeroes" in the form of $\pm x_i$ and $\pm x_j$ and use the triangle inequality. \begin{align*} 0&\leq|y_i-y_j|=|y_i+x_i-x_i+x_j-x_j-y_j|\\&\leq|x_i-x_j|+|y_i-x_i|+|x_j-y_j| \\& \leq |x_i-x_j|+2 \max_{1\leq k \leq n} |x_k-y_k|\\&\leq |x_i-x_j|+2||x-y||_{\infty} \end{align*} Re-arranging yields the desired result.