# How can I prove $d_1(x,y) \leq n d_\infty (x,y)$

$$d_\infty (x,y) = \max{|x_i - y_i| | i=1,2,...,n}$$ $$d_1 (x,y)= \sum_{i=1}^n |x_i - y_i|$$

$$d_\infty : \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}$$ $$d_1: \mathbb{R}^n \times \mathbb{R}^n \rightarrow \mathbb{R}$$

$$x,y\in \mathbb{R}^n$$

I would like to prove that $d_1(x,y) \leq n d_\infty (x,y)$.

Attempt:

Since $$d_1(x,y) = \sum_{i=1}^n |x_i - y_i|=|x_1 - y_1|+ \dots + |x_n - y_n|\leq \max|x_1 - y_1| +\dots + \max|x_i - y_i |=$$ $$= n\max |x_i - y_i |=nd_{\infty}(x,y).$$

• This is certainly false, let $(x_i)=(1)$ and $(y_i)=(0)$ the desired inequality leads to $n\leqslant \sqrt{n}$. The equality is true if you replace $d_{\infty}$ by $d_2$. – C. Falcon Oct 24 '16 at 22:04
• If you change $d_1$ for the euclidean metric then is true, are you sure you copied the problem correctly? You need to change, as it is by now, $\sqrt n$ by $n$. – Masacroso Oct 24 '16 at 22:07
• @Masacroso I believe the professor meant $n$ but incorrectly wrote $\sqrt{n}$. – ozarka Oct 24 '16 at 22:16
• If the problem state that you need to use the Cauchy-Schwarz inequality then the real problem is $d_1(x,y)\le \sqrt n d_2(x,y)$ as @C.Falcon commented. For this case you need this inequality to prove it. – Masacroso Oct 24 '16 at 22:18
• Is there a way of proving this without Cauchy-Schwarz inequality? Intuitively I don't see how the sum of non-negative terms would be less than $n \max|x_i - y_i|$ for $i=1,2,...,n$ – ozarka Oct 24 '16 at 22:21

As C. Falcon says, you should change $d_{\infty}$ by $d_{2}$. By Cauchy-Schwarz we have $$(\sum_{i=1}^n (|x_i - y_i|\cdot 1))^2\le (\sum_{i=1}^n |x_i - y_i|^2)(1^2+\cdots 1^2).$$
Then $$\sum_{i=1}^n |x_i - y_i|\le \sqrt{n}(\sqrt{\sum_{i=1}^n |x_i - y_i|^2}).$$
Hence $d_{1}(x,y)\le \sqrt{n}d_{2}(x,y)$.
• If I am asked to prove $d_1(x,y) \leq n d_\infty (x,y)$, what would be the approach without using Cauchy-Schwarz. – ozarka Oct 24 '16 at 22:23
• @ozarka hint: $\max\{|x_{i}-y_{i}|\}\ge |x_{i}-y_{i}|$ for $i=1, 2,..., n$. – Xam Oct 24 '16 at 22:31
• Yeah, your attempt is ok but it's $n \max\{|x_{i}-y_{i}|\}$ instead of $n$ for $\max\{|x_{i}-y_{i}|\}$. – Xam Oct 24 '16 at 22:42