1
$\begingroup$

Prove that if $\sum \limits_{k=1}^{n} x_n=1$ then $\sum \limits_{k=1}^{n} x_n^2 \geq {1 \over n}$ where $\{x_k\}_1^n$ are real numbers which are not all the same.

I tried to prove it by induction. The base was trivial. Now, suppose for every numbers $\{x_k\}_1^n$ that satisfy $\sum \limits_{k=1}^{n} x_n=1$ the following inequality is true: $\sum \limits_{k=1}^{n} x_n^2 \geq {1 \over n}$.

Let $\{x_k\}_1^{n+1}$ be real numbers that satisfy $\sum \limits_{k=1}^{n+1} x_k$, and let us denote $y:=x_n +x_{n+1}$, so according to the induction hypothesis $\sum \limits_{k=1}^{n-1} x_k^2 +y^2\geq {1 \over n}$.

$$\sum \limits_{k=1}^{n+1} x_k^2= \sum \limits_{k=1}^{n-1} x_k^2+x_n+x_{n+1}+y^2-y^2\geq {1 \over n}+x_n^2+x_{n+1}^2-y^2=\frac{1}{n}-2x_n x_{n+1}$$

And I'm stuck. I thought that there must be an element in $\{x_k\}_1^{n+1}$ that is less or equal to $1 \over {n+1}$ (since $\sum \limits_{k=1}^{n+1} x_k$ and the elements in the sum are not all the same), but it didn't help much.

$\endgroup$
  • $\begingroup$ The inequality goes the other way. Think Cauchy-Schwarz. $\endgroup$ – Daniel Fischer May 8 '15 at 17:25
  • $\begingroup$ You can also apply the generalized mean inequality en.wikipedia.org/wiki/Generalized_mean $\endgroup$ – Darth Geek May 8 '15 at 17:27
  • 1
    $\begingroup$ Hint: $\sum_{i=1}^n \left(x_i - \frac1n\right)^2 \ge 0$ $\endgroup$ – achille hui May 8 '15 at 17:29
  • $\begingroup$ Thank you very much. That was helpful! $\endgroup$ – Chris May 8 '15 at 17:35
  • $\begingroup$ I would re-interpret the question as follows: Given $n$ variables $x(j)$, what is the minimum value for the sum of squares given the restraint that the sum over $x(j)$ equals $1$?. This is a very simple exercise that can be solved with the Lagrange multiplier method. It follows directly that the minimum is found when all the $x(j)$ have the same value, which is $1/n$. $\endgroup$ – M. Wind May 8 '15 at 17:42
5
$\begingroup$

This is false. For instance, $x_1 = 1$ and rest of $x_i$'s zero violates the inequality. Your inequality should be the other way around, which follows from Cauchy Schwarz inequality.

By Cauchy Schwarz, we have $$\left \vert\vec{a} \cdot \vec{b} \right \vert \leq \left \Vert \vec{a}\right \Vert \left \Vert \vec{b}\right \Vert$$ where $\vec{a},\vec{b} \in \mathbb{R}^n$.

Take $\vec{a} = \begin{bmatrix}x_1 & x_2 & \cdots & x_n\end{bmatrix}^T$, and $\vec{b} = \begin{bmatrix}1 & 1 & \cdots & 1\end{bmatrix}^T$. We then have $$\left \vert \vec{a} \cdot \vec{b} \right \vert = x_1 + x_2 + \cdots + x_n = 1$$ whereas $\left \Vert \vec{a}\right \Vert = \sqrt{x_1^2+x_2^2 + \cdots + x_n^2}$ and $\left \Vert \vec{b}\right \Vert = \sqrt{1+1+\cdots+1} = \sqrt{n}$. This gives us that $$\sqrt{x_1^2+x_2^2 + \cdots + x_n^2} \geq \dfrac1{\sqrt{n}} \implies x_1^2+x_2^2 + \cdots + x_n^2 \geq \dfrac1n$$


Here is a proof by induction. Clearly, base case is trivial. Assume that for some $n$, we have that $$x_1+x_2+\cdots+x_n = 1 \implies x_1^2+x_2^2 + \cdots + x_n^2 \geq \dfrac1n$$ Now consider $$x_1+x_2+\cdots+x_n+x_{n+1} = 1$$ Clearly for $n>1$, there exists one $x_i$, which is not $1$, say let it be $x_{n+1}$. We then have $$x_1+x_2+\cdots+x_n = 1-x_{n+1} \implies \dfrac{x_1}{1-x_{n+1}} + \dfrac{x_2}{1-x_{n+1}} + \cdots + \dfrac{x_n}{1-x_{n+1}} = 1$$ which from induction hypothesis gives us $$\dfrac{x_1^2}{(1-x_{n+1})^2} + \dfrac{x_2^2}{(1-x_{n+1})^2} + \cdots + \dfrac{x_n^2}{(1-x_{n+1})^2} \geq \dfrac1n$$ This gives us that $$x_1^2 + x_2^2 + \cdots +x_n^2 \geq \dfrac{(1-x_{n+1})^2}n$$ which gives us that \begin{align} x_1^2 + x_2^2 + \cdots +x_n^2 + x_{n+1}^2 & \geq \dfrac{(1-x_{n+1})^2}n + x_{n+1}^2 = \dfrac{1-2x_{n+1}+(n+1)x_{n+1}^2}n\\ & = \dfrac1{n(n+1)} \left((n+1)^2x_{n+1}^2 - 2(n+1)x_{n+1} + 1 + n\right)\\ & = \dfrac{((n+1)x_{n+1}-1)^2 + n}{n(n+1)} = \dfrac{((n+1)x_{n+1}-1)^2}{n(n+1)} + \dfrac1{n+1}\\ \geq \dfrac1{n+1} \end{align} which completes our induction.

$\endgroup$
1
$\begingroup$

You need to assume that the are non-negative.

We have, due to Cauchy-Schwarz inequality $$ \sqrt{n}(\sum_{k=1}^n x_k^2)^{1/2} =(\sum_{k=1}^n x_k^2)^{1/2} (\sum_{k=1}^n 1^2)^{1/2} \ge \sum_{k=1}^n x_k=1. $$ Hence $$ \sum_{k=1}^n x_k^2\ge \frac{1}{n}. $$

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.