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.

This is a space $S$ that consists of the set of all sequences of real numbers and $x=(x_1,x_2,x_3,...), y=(y_1,y_2,y_3,...)$ etc. and the metric $d$ is defined as

$$d(x,y)=\sum_{i=1}^\infty \frac{1}{2^i}\frac{|x_i-y_i|}{1+|x_i-y_i|}$$

I need to show that $d$ is a metric on the space $S$, I have verified the 3 properties of the metric, but how would I show that $d(x,y) \le d(x,z) +d(z,y)?$


I was given a hint and to try show that for $a,b,c \in \mathbb R$

$$\frac{|a-b|}{1+|a-b|}\le \frac{|a-c|}{1+|a-c|} + \frac{|c-b|}{1+|c-b|} (1)$$

I tried multiplying $(1)$ by $(1+|a-b|)(1+|a-c|)(1+|c-b|)$ to get rid of the denominators, but either way I cant seem to get anywhere. How would i go about proving that $d(x,y) \le d(x,z) +d(z,y)?$

share|improve this question

3 Answers 3

The function $u:x\mapsto\frac{x}{1+x}$ is nondecreasing on $x\geqslant0$ and, by the triangular inequality, $x=|a-b|$, $y=|a-c|$ and $z=|c-b|$ are such that $x\leqslant y+z$. Hence, $u(x)\leqslant u(y+z)$. Now, $u(y+z)=\frac{y}{1+y+z}+\frac{z}{1+y+z}\leqslant\frac{y}{1+y}+\frac{z}{1+z}=u(y)+u(z)$.

This shows that $u(x)\leqslant u(y)+u(z)$.

The same proof applies to every nondecreasing concave function $u:x\mapsto u(x)$ defined on $x\geqslant0$ such that $u(0)=0$.

share|improve this answer
3  
That's pretty cool! –  Michael Greinecker Feb 14 '12 at 23:51
1  
Thanks, a nice way to solve it! –  William Feb 14 '12 at 23:58

Note that We can define that $d(x,y):=|x-y|$ and we'll have to prove that, $$\dfrac{d(x,y)}{1+d(x,y)} \le \dfrac{d(x,z)}{1+d(x,z)}+\dfrac{d(y,z)}{1+d(z,y)}$$

A take on this will be to prove that:

$$\dfrac{a}{1+a} +\dfrac{b}{1+b} \le \dfrac{a+b}{1+a+b}$$

Proof:

$$\begin{align} \dfrac{a+b}{1+a+b}-\dfrac{a}{1+a}&= \dfrac{b}{(1+a)(1+a+b)}\tag{1}\\&=\dfrac{b}{(1+b)(1+a)+a(1+a)}\tag{2}\\&\le\dfrac{b}{1+b}\end{align}$$

Alternatively, look at the solutions of the quiz conducted for the course I am crediting. It has an alternative proof.

share|improve this answer
    
Thanks, most appreciate kannappan! –  William Feb 14 '12 at 23:59

While Didier's answer is more elegant and more generally applicable, you can also prove your inequality in this case just by grinding through the algebra. Multiplying out gives $$|a-b|(1+|a-c|)(1+|c-b|) \leq |a-c|(1+|a-b|)(1+|c-b|) + |c-b|(1+|a-b|)(1+|a-c|)$$ or $$|a-b|+|a-b||a-c| + |a-b||c-b| + |a-b||a-c||c-b| \leq |a-c|+|a-b||a-c| + |a-c||c-b| + |a-b||a-c||c-b| + |c-b|+|a-b||c-b| + |a-c||c-b| + |a-b||a-c||c-b|$$ Now, every term on the left hand side except for $|a-b|$ shows up on the right hand side, so they can all be subtracted out: $$|a-b| \leq |a-c|+|a-c||c-b|+|c-b|+|a-c||c-b|+|a-b||a-c||c-b|$$ or, collecting terms, $$|a-b| \leq |a-c|+|c-b|+2|a-c||c-b| + |a-b||a-c||c-b|$$ But by the triangle inequality, you know that $|a-b| \leq |a-c|+|c-b|$, and the additional terms here are all products of absolute values so they're non-negative, which proves the lemma you're after.

share|improve this answer
    
Which is what my teacher managed to write up in three lines. +1! –  user21436 Feb 14 '12 at 23:50
    
thanks, most appreciated! –  William Feb 15 '12 at 0:10

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.