This problem is a generalization of my answer to this question:

How to prove $\sum_{i=1}^r (r-1)a_i^2\geq\sum_{i,j=1\\i\neq j}^r a_ja_i$?

Let $s_m =\sum\limits_{i_1, i_2, ..., i_m, \text{ all }i_l\text{ distinct}} \prod\limits_{l=1}^m a_{i_l} $.

Show that $s_3 =\sum\limits_{u, v, w \text{ all distinct}} a_ua_va_w \le (n-1)(n-2)\sum\limits_{k=1}^n a_k^3 $.

Conjecture: Show that $s_m \le (n-1)(n-2)...(n-m+1)\sum\limits_{k=1}^n a_k^m = \prod\limits_{j=1}^{m-1}(n-j)\sum\limits_{k=1}^n a_k^m =\dfrac{(n-1)!}{(n-m)!}\sum\limits_{k=1}^n a_k^m $.

This is true for $m=2$ (as I showed in the linked answer) and $m=3$ (this problem).


Yes, it is true for arbitrary $m \ge 2$ and $a_1, \ldots ,a_n \ge 0$.

I'll start with an alternative proof for $m=2$: Using the AM-GM inequality we get $$ s_2 = \sum_{i \ne j} a_i a_j \le \sum_{i \ne j}\frac 12 \left( a_i^2 + a_j^2 \right) = \sum_{i \ne j} a_i^2 = \sum_{i=1}^n \sum_{\substack{j=1 \\ j \ne i}}^n a_i^2 = (n-1) \sum_{i=1}^n a_i^2. $$

This can be generalized to any integer $m \ge 2$: From the AM-GM inequality we get $$ s_m =\sum_{\substack{i_1, i_2, ..., i_m \\ \text{distinct}}} \left(\prod_{l=1}^m a_{i_l} \right) \le \sum_{\substack{i_1, i_2, ..., i_m \\ \text{distinct}}} \left(\frac 1m \sum_{l=1}^m a_{i_l}^m \right) = \frac 1m \sum_{l=1}^m \sum_{\substack{i_1, i_2, ..., i_m \\ \text{distinct}}} a_{i_l}^m $$ For symmetry reasons, the inner sum is independent of $l$. Therefore $$ s_m \le \sum_{\substack{i_1, i_2, ..., i_m \\ \text{distinct}}} a_{i_1}^m = (n-1)(n-2)\cdots(n-m+1) \sum_{i_1=1}^n a_{i_1}^m $$ The last equality holds because for each $i_1$ there are $(n-1)(n-2)\cdots(n-m+1)$ possible choices for $i_2, \ldots, i_m$.


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.