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

Question

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!

Answer 1

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.

Answer 2

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

Answer 3

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$