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

3 Answers 3

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$
2
  • 3
    $\begingroup$ That's pretty cool! $\endgroup$ Feb 14, 2012 at 23:51
  • 1
    $\begingroup$ Thanks, a nice way to solve it! $\endgroup$
    – William
    Feb 14, 2012 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$
1
  • $\begingroup$ Thanks, most appreciate kannappan! $\endgroup$
    – William
    Feb 14, 2012 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$
1
  • $\begingroup$ Which is what my teacher managed to write up in three lines. +1! $\endgroup$
    – user21436
    Feb 14, 2012 at 23:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .