I can't see this on here, so I am going to post my solution and would appreciate if anyone could give me some tips etc.


$||\mathbb{x}||_{\infty} = max\{|x_j| j\in[1,n]\} = |x_k|$

I have assigned $x_k$ to be the component of $\mathbb{x}$ with greatest absolute value.

Now $$|x_k|\leq\sqrt{x_k^2+x_1^2+...+x_{k-1}^2+x_{k+1}^2+...+x_{n}^2} = ||\mathbb{x}||_2$$

we need to show that

$$|x_1 + x_2+...+x_n|\leq |x_1| + |x_2|+...+|x_n|$$ $$\implies ||\mathbb{x}||_2= \sqrt{(x_1^2 + x_2^2+...+x_n^2)}\leq |x_1| + |x_2|+...+|x_n|=||\mathbb{x}||_1$$

to do this we will proceed by induction.

for the case $n=2$ $$|x_1|^2+|x_2|^2 \leq (|x_1|+|x_2|)^2 = |x_1|^2+|x_2|^2 + 2|x_1||x_2| $$

now suppose this is true for some n.

$$|x_1|^2+...+|x_n|^2+|x_{n+1}|^2\leq(|x_1|+...+|x_n|)^2 + |x_{n+1}|^2 \leq (|x_1|+...+|x_n|)^2 + (|x_{n+1}|^2 + |x_{n+1}|||x_{n}| + ...+ |x_{n+1}|||x_{1}|) = (|x_1| + |x_2|+...+|x_{n+1}|)^2$$

Is this a complete proof?

  • $\begingroup$ How do you get the last implication from the triangle inequality? $\endgroup$ – Clement C. Oct 21 '15 at 14:52
  • $\begingroup$ Right, I see. one second, i will update. I have a better attempt. I am treating scalars as vectors here. $\endgroup$ – user197848 Oct 21 '15 at 14:54
  • $\begingroup$ I think your proof is okay, except for the second proof you use the fact that $ \sqrt{a+b} \leq \sqrt{q}+\sqrt{b}$ for all $a,b \geq 0 $ instead of triangle inequality . $\endgroup$ – Nizar Oct 21 '15 at 15:05

The first part is correct (and works actually for any $p$-norm, not only $\ell_2$: $\lVert x\rVert_\infty \leq \lVert x\rVert_p$, for $p > 0$)

The induction argument appears to have a small issue (and the one just above, with the implication, looks strange and unmotivated: why does this implication hold?): namely, to get the sqare in the end, you should add $$ 2\lvert x_{n+1}\rvert (\lvert x_{1}\rvert+\dots+\lvert x_{n}\rvert)^2 $$ in the upper bound, not $\lvert x_{n+1}\rvert\lvert x_{1}\rvert\cdots\lvert x_{n}\rvert$.

I am pasting below an alternate proof of the inequality (as the intended goal of your question is allegedly to provide such a proof, as "[you] can't see this on here"):

For any sequence $x=(x_1,\dots,x_n)\in\mathbb{R}^n$, $p > 0 \mapsto \lVert{x}\rVert_p$ is non-increasing. In particular, for $0 < p \leq q <\infty$, $$ \left(\sum_i \lvert{x_i}\rvert^q\right)^{1/q} = \lVert{x}\rVert_q \leq \lVert{x}\rVert_p = \left(\sum_i \lvert{x_i}\rvert^p\right)^{1/p}\;. $$ To see why, one can easily prove that if $\lVert{x}\rVert_p = 1$, then $\lVert{x}\rVert_q^q \leq 1$ (bounding each term $\lvert{x_i}\rvert^q \leq \lvert{x_i}\rvert^p$), and therefore $\lVert{x}\rVert_q \leq 1 = \lVert{x}\rVert_p$.

Next, for the general case, apply this to $y = x/\lVert{x}\rVert_p$, which has unit $\ell_p$ norm, and conclude by homogeneity of the norm.

  • $\begingroup$ In my last edit, is the proof "good" for the last part? (I am currently reading though your answer) $\endgroup$ – user197848 Oct 21 '15 at 15:09
  • $\begingroup$ I think the extra term you add is not the right one -- it should most likely be $2\lvert x_{n+1}\rvert (\lvert x_{1}\rvert+\dots+\lvert x_{n}\rvert)^2$ $\endgroup$ – Clement C. Oct 21 '15 at 15:11

Your Answer

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