Prove or disprove inequality between 1-norm, 2-norm and infinity norm. Prove or disprove:
$$
v\in R^n \Rightarrow ||v||_1||v||_{\infty}\leq \frac{1+\sqrt n}{2}||v||^2_2.
$$
Can someone help me with this? I have used several cases to verify it but cannot come up with proof. 
 A: Since $v$ and its entrywise absolute value $|v|$ have the same norms, we may assume that $v=(v_1,v_2,\ldots,v_n)$ with $v_1\ge v_2\ge\cdots\ge v_n\ge0$. The inequality in question can hence be rewritten as
\begin{aligned}
(v_1+v_2+\cdots+v_n)v_1
&\le\frac{1+\sqrt{n}}{2}(v_1^2+v_2^2+\cdots+v_n^2),\\
v_1v_2+\cdots+v_1v_n
&\le\frac{\sqrt{n}-1}{2}v_1^2+\frac{\sqrt{n}+1}{2}v_2^2+\cdots+\frac{\sqrt{n}+1}{2}v_n^2\\
&=\frac12\left[\frac{v_1^2}{\sqrt{n}+1}+(\sqrt{n}+1)v_2^2\right]
+\cdots+\frac12\left[\frac{v_1^2}{\sqrt{n}+1}+(\sqrt{n}+1)v_n^2\right]\\
\end{aligned}
which is true because of the AM-GM inequality.
A: Here is a proof which also shows that the inequality is tight.
Instead of $|x_i|$, consider w.l.o.g. $x_i \ge 0$. Further, let $x_{\rm max} = x_n$.
Denote $\sqrt{\sum_{i=1}^{n-1} x_i^2} = ||\bar v||_2$.
First, by Cauchy-Schwarz
$$||v||_1 = \sum_{i=1}^{n-1} 1 \cdot x_i  + x_n\le \sqrt{\sum_{i=1}^{n-1} 1} \sqrt{\sum_{i=1}^{n-1} x_i^2} + x_n=  \sqrt{n-1} ||\bar v||_2 + x_n
$$ 
This gives 
$$
\frac{||v||_1||v||_{\infty}}{||v||^2_2} \le \frac{\sqrt{n-1} ||\bar v||_2 x_n+ x_n^2}{||\bar v||_2^2 + x_n^2}
$$
Now the function 
$$
f(x_n) = \frac{ax_n + x_n^2}{b + x_n^2}
$$
has a maximum value (see appendix below) of $\frac12 (\sqrt{\frac{a^2+b}{b}} +1)$. Inserting  $a = \sqrt{n-1} ||\bar v||_2$ and $b =  ||\bar v||_2^2$ gives 
$$
\frac{||v||_1||v||_{\infty}}{||v||^2_2} \le 
\frac12 (\sqrt{\frac{(n-1) ||\bar v||_2^2 +||\bar v||_2^2}{||\bar v||_2^2}} +1) = \frac12 (\sqrt{n} +1)
$$
This proves the claim. $\qquad \Box$
Note that the bound is tight. From the appendix below, the tight bound is taken 
at $$x^*_n = \frac{a}{-1+\sqrt{\frac{b+a^2}{b}}} = ||\bar v||_2\frac{\sqrt{n-1}}{-1+\sqrt{n}} $$ Further, the Cauchy-Schwarz inequality above is tight for $x_1 = x_2 = \cdots = x_{n-1}$. Hence we have that $x^*_n  = x_1 (1+\sqrt{n})$ is the selection of values where the claim is obeyed with equality. Indeed, one can check that both sides equal:
\begin{align}
{\rm LHS:}&||v||_1||v||_{\infty} = ((n-1)x_1 + x_n^*)x_n^* = x_1^2 (1+{\sqrt{n}})(n+{\sqrt{n}})\\
{\rm RHS:}&\frac{1+\sqrt n}{2}||v||^2_2 = \frac{1+\sqrt n}{2}((n-1)x_1^2+ (x_n^*)^2) \\
& = x_1^2({1+\sqrt n}) \frac{n-1 + (1+\sqrt{n})^2}{2}  = x_1^2 (1+{\sqrt{n}})(n+{\sqrt{n}})
\end{align}

Appendix :
The maximum value of the function 
$
f(x) = \frac{ax + x^2}{b + x^2}
$
can be obtained without calculus as follows. For simplicity, let $x = ay$ and $b =a^2 c$. Then we require $
f(y) = \frac{y + y^2}{c + y^2} \le m
$ or alternatively 
$$0 \le -(y + y^2) + m(c + y^2) = (m-1)(y - \frac{1}{2(m-1)})^2 + mc - \frac{1}{4(m-1)}$$
To guarantee this inequality, the tight case is that the square term gets zero, and also $mc - \frac{1}{4(m-1)}$ (which is unbounded w.r.t. $m$) gets zero. This gives $m = \frac12 (1 + \sqrt{\frac{c+1}{c}})$. Reinserting $c = b/a^2$ gives the highest value of $f(x)$ which is $\frac12 (\sqrt{\frac{a^2+b}{b}} +1)$, as stated above. The bound is then taken where the square term gets zero, i.e. at $x^* = a y =  \frac{a}{2(m-1)} = \frac{a}{-1+\sqrt{\frac{c+1}{c}}} = \frac{a}{-1+\sqrt{\frac{b+a^2}{b}}} $
