Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
Simple and correct, thanks! –  Pavel Podlipensky Nov 15 '12 at 4:58
    
@GerryMyerson do you have maybe a more foemal way to show that? –  Snufsan Nov 16 at 0:18
    
You 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. –  Gerry Myerson Nov 16 at 5:21

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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