# Short “beautiful” proof for simple fact wanted

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.

• This is immediate from arithmetic-quadratic mean inequality. – Wojowu Sep 10 '16 at 12:31
• 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. – user136457 Sep 10 '16 at 12:33
• Googling "arithmetic-quadratic mean inequality" should help you find a proof. – Wojowu Sep 10 '16 at 12:34
• 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}.$$ – Daniel Fischer Sep 10 '16 at 12:36
• 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. – user136457 Sep 10 '16 at 12:40

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

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

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.

• 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. – user136457 Sep 10 '16 at 12:57