Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
    
|x+y|≤|x|+|y| Can I apply this to |a−b|? –  Laciel Oct 23 '11 at 19:25
    
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.$$ –  JavaMan Oct 23 '11 at 19:38
    
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| –  Laciel Oct 23 '11 at 19:42
    
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|.$$ –  JavaMan Oct 23 '11 at 19:48
    
I'm sorry, I still don't understand why |ai−bi|=|(ai−ci)+(ci−bi)| –  Laciel Oct 23 '11 at 19:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.