If I know sum of some K numbers (each of them from 0 to 9). Can I find lower bound of sum of squares of the same elements? I don't know value of each element, I'm just aware of their sum. Thanks.
Estimate sum of squares
3 Answers
The lower bound is achieved when the numbers are as nearly equal as possible (think about $5^2+5^2$ versus $9^2+1^2$). So if your $K$ numbers add up to $S$, let some of them be the least integer exceeding $S/K$, the rest, one less, and that will minimize the sum of squares.
-
0You can look at dinoboy's answer. Or, you can look at what happens if ou have a distribution other than the one I describe, and then you change two of the numbers to make them closer to that distribution, and show that this always lowers the sum of the squares. – 2014-11-16
The lower bound comes when they are as evenly distributed as possible. So if there are $K$ numbers that sum to $N$, the lower bound for the sum of squares is $K( \frac NK)^2=\frac {N^2}K$ This works if the numbers don't have to be whole. Otherwise, come as close as you can with some of them $\lfloor \frac NK \rfloor$ and some of them one more.
By Cauchy-Schwarz: $(x_1 + x_2 + ... + x_n)^2 \le (x_1^2 + x_2^2 + ... + x_n^2)(1 + 1 + ... + 1)$ $x_1^2 + x_2^2 + ... + x_n^2 \ge \frac{(x_1 + x_2 + ... + x_n)^2}{n}$ Thus the sum of the squares is always $\ge$ to the sum of the elements squared and then divided by $n$. Note that as equality occurs when the $x_i$ are equal, to minimize the sum of squares it suffices to make the $x_i$ as close as possible to the average. A more rigorous (but slightly more difficult) argument using Jensen's Inequality will conclude that the sum will be minimized when all the elements differ from each other by at most 1.