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.

I wish to prove that the metric $d(x,y)=\sum^\infty_{n=1}\frac{1}{2^n}\frac{|x_n-y_i|}{1+|x_n-y_n|}$

This is a metric on infinite sequences, x,y and z are sequences with terms $x_i$ and so forth.

The problem is the triangle inequality requirement, $d(x,y)\le d(x,z)+d(z,y)$

$\sum^\infty_{n=1}\frac{1}{2^n}\frac{|x_n-y_i|}{1+|x_n-y_n|}= \sum^\infty_{n=1}\frac{1}{2^n}\frac{|x_n-z_n+z_n-y_i|}{1+|x_n-z_n+z_n-y_n|}$

$\le\sum^\infty_{n=1}\frac{1}{2^n}\frac{|x_n-z_i|}{1+|x_n-z_n+z_n-y_n|}+\sum^\infty_{n=1}\frac{1}{2^n}\frac{|z_n-y_i|}{1+|x_n-z_n+z_n-y_n|}$

Now I want to show something like $\frac{1}{1+|x_n-z_n+z_n-y_n|}=\frac{1}{1+|x_n-y_n|}\le\frac{1}{1+|x_n-z_n|}$

$\iff1+|x_n-y_n|\ge1+|x_n-z_n|$

So, I've been playing with this for a while and have got nowhere. The term with coefficient $\frac{1}{2^n}$ is itself a metric, so it should be true (the series part isn't important).

But why can't $x=3,y=2,z=1$ be valid, then $1+|3-2|=2\ge1+|3-1|=3$ which is false! Even if you change the inequality sign (so the other way instead) just set y=1 and z=2 and the result is contradicted!

share|improve this question
    
What's $i$ in the definition of $d$? –  littleO May 3 at 21:42
    
@littleO where did you see the i? –  Alec Teal May 3 at 21:43
    
Check "Introductory function Analysis" by E. Kreyszig, he shows it" –  PtF May 3 at 21:54
    
@Alec: There are $i$'s all over the place that should be $n$'s. –  TonyK May 3 at 22:00

3 Answers 3

Note that $\frac{d}{da}\frac{a}{1+a} = \frac{1}{(a+1)^2} > 0$, so $\frac{a}{1+a} \leq \frac{b}{1+b}$ if $b \geq a$. Let $$b := d(x,z) + d(z,y),\quad a:= d(x,y).$$ By the above, we have \begin{align*} \frac{d(x,y)}{1+d(x,y)} &\leq \frac{d(x,z) + d(z,y)}{1+d(x,z)+d(y,z)}\\ &= \frac{d(x,z)}{1+d(x,z) + d(y,z)} + \frac{d(y,z)}{1+d(y,z)+d(x,z)} \\ &\leq \frac{d(x,z)}{1+d(x,z)} + \frac{d(y,z)}{1+d(y,z)}. \end{align*} The last inequality follows because $d(\cdot,\cdot) \geq 0.$

share|improve this answer

But why can't $x=3,y=2,z=1$ be valid, then $1+|3−2|=2≥1+|3−1|=3$ which is false! Even if you change the inequality sign (so the other way instead) just set $y=1$ and $z=2$ and the result is contradicted!

Yes, at this point in your proof your inequality is not true. That means you "threw away information" earlier on when you used the Triangle Inequailty the first time. Notice that if you put in $x = 3, y = 2, z = 1$ into the original expression it is still true, because $$ \frac{|x - y|}{1 + |x - y|} + \frac{|y - z|}{1 + |y - z|} = \frac{1}{1 + 1} + \frac{1}{1 + 1} \ge \frac{2}{1 + 2} = \frac{|x - z|}{1 + |x - z|}. $$


What you need to show is the following:

$$ \frac{|a|}{1 + |a|} + \frac{|b|}{1 + |b|} \ge \frac{|a + b|}{1 + |a + b|} $$ Since $\frac{x}{1 + x}$ is an increasing function for $x \ge 0$, it's equivalent to show that, for $a, b \ge 0$, $$ \frac{a}{1 + a} + \frac{b}{1 + b} \ge \frac{a + b}{1 + a + b} $$ There is surely a more clever way to show this, but the easiest thing to do when you aren't sure is just to multiply it out. (Edit: See snarski's answer for the cleaner approach, which is actually pretty obvious now I see it.) If you do this you get \begin{align*} &(a + ab)(1 + a + b) + (b + ab)(1 + a + b) \\ &\quad \ge (a + b)(1 + a + b + ab) \\ &(a + a^2 + 2ab + a^2b + ab^2) + (b + b^2 + 2ab + a^2b + b^2a) \\ &\quad \ge a + b + a^2 + b^2 + 2ab + a^2b + b^2a \\ \end{align*} This simplifies to: $$ a^2b + 2ab + b^2a \ge 0 $$ i.e. $ab(a + 2 + b) \ge 0$, which is true. Read the algebra backwards and you have a proof of the desired inequality.

share|improve this answer

Claim Let $f:[0,\infty)\to [0,\infty)$ be a monotone increasing, subbaditive, positive function except with $f(0)=0$. Let $d:X\times X\to [0,\infty)$ be any metric. Then $f\circ d$ is also a metric.

Proof Recall subadditive means $f(x+y)\leqslant f(x)+f(y)$. Since $f(z)=0\iff z=0$, $f\circ d=0$ iff $x=y$. It is clear $f\circ d$ is positive and symmetric.

Now pick $x,y,z$, three points in $X$. Then $$f(d(x,z))\leqslant f(d(x,y)+d(y,z))\leqslant f(d(x,y))+f(d(y,z))$$

so the triangle inequality holds.$\blacktriangleleft$

Corollary Let $e:[0,\infty)\to [0,\infty)$ be $\min(1,x)$, and $f:[0,\infty)\to [0,\infty)$ be $\dfrac{x}{1+x}$. If $d$ is a metric, so is $f\circ d$ and $e\circ d$.

In particular,

Claim Suppose $f:[0,\infty)\to [0,\infty)$ satisfies the hypothesis of the claim, and additionaly suppose $f\leqslant 1$ everywhere, and for each $i=0,1,2,\ldots$ let $(X_i,d_i)$ be a metric space. Let $X=\prod\limits_{i\geqslant 0}X_i$. Then $(X,d)$ is a metric space with $d:X\times X\to[0,\infty)$ defined by $$d(\{x_i\},\{y_i\})=\sum_{i\geqslant 0}2^{-i}D_i(x_i,y_i)$$ $D_i=f\circ d_i$.

Proof It is clear the series will converge everywhere, absolutely. We need only check the triangle inequality. But for each $i$, we have $$D_i(x_i,z_i)\leqslant D_i(x_i,z_i)+D_i(z_i,y_i)$$

so multiplying by $2^{-i}$ and summing finishes the proof. $\blacktriangleleft$

share|improve this answer

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.