0
$\begingroup$

I'd like to find a cute proof for the following fact:

Let $x_1, \dotsc, x_n \in \mathbb{N}$ be such that $\sum_{i=1}^n x_i = X$ for some fixed $X \in \mathbb{N}$ and $x_i \leq v$ for all $1 \leq i \leq n$. Then $$\sum_{i=1}^n x_i^2 \leq \frac{X}{v} v^2=Xv$$

Thanks for any input.

$\endgroup$
  • 2
    $\begingroup$ This is immediate from arithmetic-quadratic mean inequality. $\endgroup$ – Wojowu Sep 10 '16 at 12:31
  • $\begingroup$ Thanks for this hint. Do you know a paper or a book where this is further explained? Because either I have to find a nice proof on my own or a good reference. $\endgroup$ – user136457 Sep 10 '16 at 12:33
  • $\begingroup$ Googling "arithmetic-quadratic mean inequality" should help you find a proof. $\endgroup$ – Wojowu Sep 10 '16 at 12:34
  • 2
    $\begingroup$ Your inequality goes the wrong way, let $\mu = X/n$, then $$0 \leqslant \sum_{i = 1}^n (x_i - \mu)^2 = \sum_{i = 1}^n x_i^2 - 2\mu \sum_{i = 1}^n x_i + n\mu^2 = \sum_{i = 1}^n x_i^2 - n\mu^2 = \sum_{i = 1}^n x_i^2 - \frac{X^2}{n}.$$ $\endgroup$ – Daniel Fischer Sep 10 '16 at 12:36
  • $\begingroup$ Oh, thanks for your correction. Actually, I wrote the wrong thing, I wanted to prove something different. I will change the question! Now it should be what I am looking for, and I hope it is correct now. $\endgroup$ – user136457 Sep 10 '16 at 12:40
6
$\begingroup$

$$Xv=\sum_{i=1}^nx_iv\geq\sum_{i=1}^nx_ix_i=\sum_{i=1}^nx_i^2$$

$\endgroup$
  • $\begingroup$ Wow, this is really nice! Thanks a lot. Exactly what I was looking for, indeed a cute, nice, short, beatiful proof. :-) $\endgroup$ – user136457 Sep 10 '16 at 12:47
1
$\begingroup$

Proceed as when maximizing entropy: Use lagrange multipliers to maximize $\sum_i x_i^2$ subject to the constraint $\sum_{i=1}^n x_i = X$. You then get a maximum for $x_i=\frac{X}{n}$.

This means:

$$\sum_{i=1}^n x_i^2 \leq \sum_{i=1}^n\frac{X^2}{n^2}=\frac{X^2}{n}=X\frac{X}{n}\leq X v$$

Where the last inequality comes from the fact that $x_i=\frac{X}{n}$ satisfies the requirements.

$\endgroup$
  • $\begingroup$ Thanks for your answer. It is good to know how one would proceed in general (for more difficult problems) but for this I think Wojowu's answer is nicer. $\endgroup$ – user136457 Sep 10 '16 at 12:57

Your Answer

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

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