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