4
$\begingroup$

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.

  • 0
    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.2011-10-23
  • 0
    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.2011-10-23
  • 0
    |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.2011-10-23

1 Answers 1

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.

  • 0
    |x+y|≤|x|+|y| Can I apply this to |a−b|?2011-10-23
  • 0
    If you can show $|x+y| \leq |x| + |y|$, then let $x = a-b$ and $y = b$, so that $$|(a-b) + b| \leq |a-b| + b.$$2011-10-23
  • 0
    How does that show that ai−bi ≤ |ai−ci|+|ci−bi|? I don't see how that helps. ai−bi ≤|ai−bi|+ bi ≤ |ai−ci|+|ci−bi|2011-10-23
  • 0
    This helps specifically in your case since we would have $$|a_i - b_i| = |(a_i - c_i) + (c_i - b_i)| \leq |a_i - c_i| + |c_i - b_i|.$$2011-10-23
  • 0
    I'm sorry, I still don't understand why |ai−bi|=|(ai−ci)+(ci−bi)|2011-10-23
  • 0
    The $a_i, b_i, c_i$ are real numbers, so $-c_i + c_i = 0$.2011-10-23
  • 0
    Wow. That is a stupid overlook on my part. Thank you, very much for your help.2011-10-23
  • 0
    No, not a problem!2011-10-23