The largest sum of products of pairs of number's terms

Question

Someone, please, make that title more readable. My lack of math English does not let me.

---

Given $A = a_1 + ... + a_k;\ A, a_i > 0$ what is $\max\left(\sum_{i<j}a_i a_j\right)$?

An obvious upper bound is $\dfrac{A^2}{2}$, because $\sum_{i<j}a_i a_j = \dfrac{A^2 - \sum_i a_i^2}{2}$.

Something tells me the maximum is when $\forall i\ a_i = \dfrac{A}{k}$, but I cannot prove it properly.

Answer 1

Hint: formulate this as a constraint maximization problem and apply Lagrange Multipliers. The $a_i$ are the input and they’re subject to the constraint that $\sum a_i=A$.

Answer 2

Since you already have the intuition that they all has to be equal to each other, I will argue why this is true.

You already noted that \begin{equation} 2\sum_{i<j}a_ia_j= A^2 - \sum_{i}^{k}a_i^2 \end{equation} hence equivalently we are trying to minimize $\sum a_i^2$. Now suppose we have a minimal solution where there exists $a_i,a_j$ such that $a_i\neq a_j$. Without loss of generality, say $a_1>a_2$.

Let $a=\frac{a_1+a_2}{2}$. Compare $(a_1,a_2,a_3,\dots, a_k)$ and $(a,a, a_3, \dots, a_k)$. Since $a_3^2+a_4^2 +\dots + a_k^2$ part is equal: \begin{equation} \begin{aligned} a_1^2+a_2^2 > a^2 + a^2&\iff a_1^2 + a_2^2 > \frac{(a_1+a_2)^2}{2} \\&\iff a_1^2 + a_2^2 > 2a_1a_2\\ &\iff (a_1-a_2)^2 > 0 \end{aligned} \end{equation} which is true and contradicts that we started with a minimal solution.