# Can't prove statement jumped over in book proof, I actually think it might be wrong. But it is used throughout the book

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!

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

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.$

-

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.

-

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$

-