2
$\begingroup$

Let $S$ denote the set of all sequences of real numbers. For $x=(x_1,x_2,x_3,...)$, $y=(y_1,y_2,y_3,...)$ in $S$, consider $$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)?$

$\endgroup$
7
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ That's pretty cool! $\endgroup$ – Michael Greinecker Feb 14 '12 at 23:51
  • 1
    $\begingroup$ Thanks, a nice way to solve it! $\endgroup$ – William Feb 14 '12 at 23:58
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, most appreciate kannappan! $\endgroup$ – William Feb 14 '12 at 23:59
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Which is what my teacher managed to write up in three lines. +1! $\endgroup$ – user21436 Feb 14 '12 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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