4

So I am trying to prove that the taxicab distance using the triangular inequality.
$$d_1(p,q)=\|p-q\|_1=\sum_{i=1}^n|p_i-q_i|$$

So I am trying to show that: $|d_1(a,b)−d_1(c,b)| \le d(a,c)$

which is: $$\sum_{i=1}^n |a(i) - b(i)| - \sum_{i=1}^n |c(i) - b(i)| ≤ \sum_{i=1}^n |a(i) - c(i)|$$

How would I combine the 2 sum series on the left?

Thank you.

J. M. ain't a mathematician
  • 75,051
Laciel
  • 221
  • Hint: It is enough to show that for any fixed $i$, we have $|a(i)-b(i)| -|c(i)-b(i)| \le |a(i)-c(i)|$. It might be then slightly easier for you to handle the inequality you get by transferring the $|c(i)-b(i)|$ term to the right-hand side. – André Nicolas Oct 23 '11 at 19:11
  • I was originally doing that but maybe it because I don't know all the Properties of Absolute Value so I don't really know how to simplify. – Laciel Oct 23 '11 at 19:15
  • |a(i) - b(i)| ≤ |a(i) - c(i)| + |c(i) - b(i)| then I can do sqrt((a-b)^2) ≤ sqrt((a-c)^2) + sqrt((c-b)^2)

    I expanded that out but I don't know what to do from there.

     – Laciel Oct 23 '11 at 19:23

1 Answers1

3

It is enough to show that $$d(a,b) \leq d(a,c)+ d(c,b),$$ since then, we also have $d(a,c) - d(c,b) \leq d(a,b)$.

In other words, we aim to show that

$$ d(a,b) = \sum_{i=1}^n |a_i - b_i| \leq \sum_{i=1}^n \left( |a_i - c_i| + |c_i - b_i|\right), $$

and to do this, all we need to do is show $|x + y| \leq |x| + |y|$, where $x, y \in \mathbb{R}$ and $|\cdot|$ is the usual absolute value. I will leave it to you to fill in the details.

JavaMan
  • 13,153