10
$\begingroup$

$$\dfrac{x_1^2+ x_2^2 + \cdots + x_n^2}n \geq \left(\dfrac{x_1+x_2+\cdots+x_n}n\right)^2$$

I don't think AM, GM can be used here. And simple expansion doesn't help too. What should I do?

$\endgroup$
2
  • $\begingroup$ I used AM-GM in my answer (though calling it AM-GM is overkill, since AM-GM (the inequality with $n$ members instead of just $2$) is difficult to prove while $a^2+b^2\ge 2ab\Leftrightarrow (a-b)^2\ge 0$). $\endgroup$
    – user26486
    Commented Apr 26, 2015 at 13:44
  • $\begingroup$ Note that this is Sedrakyan's inequality (also known as Titu's Lemma): en.wikipedia.org/wiki/Sedrakyan%27s_inequality with $b_i = n$ for all $i\in \{1,\ldots, n\}.$ $\endgroup$ Commented Aug 14, 2022 at 15:23

5 Answers 5

13
$\begingroup$

This is an immediate consequence of Cauchy-Schwarz inequality. The Cauchy-Schwarz inequality states that if $\vec{a},\vec{b} \in \mathbb{R}^m$, then $$\left \vert \vec{a} \cdot \vec{b} \right \vert \leq \left \Vert \vec{a} \right \Vert \left \Vert \vec{b} \right \Vert$$ where equality holds iff $\vec{a}=\lambda \vec{b}$, where $\lambda \in \mathbb{R}$. In your case, take $\vec{a} = \begin{bmatrix} x_1 & x_2 & x_3 & \cdots & x_n\end{bmatrix}^T$ and $\vec{b} = \begin{bmatrix} 1 & 1 & 1 & \cdots & 1\end{bmatrix}^T$.

$\endgroup$
3
  • 2
    $\begingroup$ Equality holds only if $a=\lambda b$. Otherwise $|a\cdot b| \le \|a\| \|b\|$. $\endgroup$
    – Joel
    Commented Apr 24, 2015 at 15:08
  • 1
    $\begingroup$ @Joel Edited. ${}$ $\endgroup$
    – Adhvaitha
    Commented Apr 24, 2015 at 15:13
  • $\begingroup$ Looks good then. $\endgroup$
    – Joel
    Commented Apr 24, 2015 at 15:14
9
$\begingroup$

There are a lot of ways you can prove this. It is called QM-AM inequality (you may often see it stated as holding for $x_i\ge 0$, but then it clearly holds for any real $x_i$, since $|x_i|\ge x_i$).

In general, $a_i>0, k_2>k_1$ gives (Power Mean Inequality): $$\sqrt[k_2]{\frac{a_1^{k_2}+\cdots+a_n^{k_2}}{n}}\ge \sqrt[k_1]{\frac{a_1^{k_1}+\cdots+a_n^{k_1}}{n}}$$

$1)$ Cauchy-Schwarz inequality. Multiply both sides by $n^2$: $$(1+1+\cdots+1)(x_1^2+x_2^2+\cdots+x_n^2)\ge (x_1+x_2+\cdots+x_n)^2$$

$2)$ Jensen's inequality. Let $f(x)=x^2$. $f$ is convex (since $f''(x)=2\ge 0$), so $$\frac{f(x_1)+f(x_2)+\cdots+f(x_n)}{n}\ge f\left(\frac{x_1+x_2+\cdots+x_n}{n}\right)$$

$3)$ Chebyshev's inequality. Let wlog $x_1\ge x_2\ge \cdots \ge x_n$. Multiply both sides by $n^2$: $$n(x_1x_1+x_2x_2+\cdots+x_nx_n)\ge (x_1+x_2+\cdots+x_n)(x_1+x_2+\cdots+x_n)$$

$\endgroup$
3
$\begingroup$

Let $X$ be a r.v. uniform on $\{x_1,x_2, \ldots,x_n \}$.

Then notice that $$ V(X)=\dfrac{x_1^2+ x_2^2 + \cdots + x_n^2}n -\left(\dfrac{x_1+x_2+\cdots+x_n}n\right)^2 . $$ Since the variance is always non-negative, we conclude.

$\endgroup$
2
$\begingroup$

It's just $$\sum_{1\leq i<j\leq n}(x_i-x_j)^2\geq0$$

$\endgroup$
2
$\begingroup$

An inductive argument, applying the inequality $$ 2xy=x^2+y^2 -(x-y)^2\leq x^2+y^2. $$

Assume the result holds for some $n\in \mathbb{N}$ and let $a_{n+1}\in \mathbb{R}$, then \begin{align} (a_1+\cdots+a_n+a_{n+1})^2 &=(a_1+\cdots+a_n)^2+2(a_1+\cdots+a_n)a_{n+1} +{a_{n+1}}^2\\ &\leq n(a_1^2+\cdots+a_{n}^2)+ (a_1^2+\cdots+ a_{n}^2)+(n+1)a_{n+1}^2\\ &=(n+1)\left(a_1^2+\cdots+ a_{n+1}^2\right). \end{align}

$\endgroup$

You must log in to answer this question.

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