# Prove that if $\sum \limits_{k=1}^{n} x_n=1$ then $\sum \limits_{k=1}^{n} x_n^2 \geq {1 \over n}$

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.

• The inequality goes the other way. Think Cauchy-Schwarz. – Daniel Fischer May 8 '15 at 17:25
• You can also apply the generalized mean inequality en.wikipedia.org/wiki/Generalized_mean – Darth Geek May 8 '15 at 17:27
• Hint: $\sum_{i=1}^n \left(x_i - \frac1n\right)^2 \ge 0$ – achille hui May 8 '15 at 17:29
• Thank you very much. That was helpful! – Chris May 8 '15 at 17:35
• 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$. – M. Wind May 8 '15 at 17:42

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.
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}.$$