$\begingroup$

I have $n$ non-negative integers $x_1, \dotsc, x_n$ which satisfy the constraint $\sum x_i = S$

I want to derive a bound on $\sum x_i^2$. An easy bound can be calculated as:

$\sum x_i^2 \le (max_{x_i}) \sum x_i = S^2$

This bound works for non-negative reals. Is there a tighter bound for non-negative integers or is this the best we can do?

$\endgroup$ 2

1 Answer

$\begingroup$

If the integers are not necessarily distinct, then you can create an upper bound by making all but one of the integers $0$, and make the last integer $S$, which gives you an upper bound of $S^2$. This is the best we can do, as increasing any of the zero integers will get us a lower result by the fact that $(S-n)^2+n^2-S^2=S^2-2Sn+2n^2-S^2=2n(n-S)$, which is negative except at $n=0,S$, at which points the difference between the result and the upper bound is zero.

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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