Maximize $x_1x_2+x_2x_3+\cdots+x_nx_1$

Let $x_1,x_2,\ldots,x_n$ be $n$ non-negative numbers ($n>2$) with a fixed sum $S$.
What is the maximum of $x_1x_2+x_2x_3+\cdots+x_nx_1$?

Fixed This is carlop's solution simplifyid, so please upvote that solution.

For $n=3$ we have by C-S or rearrangement

$$x_1x_2+x_2x_3+x_3x_1 \leq x_1^2+x_2^2+x_3^2$$

Adding $2(x_1x_2+x_2x_2+x_3x_1)$ we get

$$3(x_1x_2+x_2x_3+x_3x_1) \leq (x_1+x_2+x_3)^2 \,.$$

For $n \geq 4$ even we have

$$x_1x_2+x_2x_3+....+x_{2k}x_1 \leq (x_1+x_3+..+x_{2k} )( x_2+x_4+...+x_{2k-1})$$

since any term on the LHS appears on the RHS.

Thus

$$\sqrt{x_1x_2+x_2x_3+....+x_{2k}x_1} \leq \frac{x_1+x_3+..+x_{2k} + x_2+x_4+...+x_{2k-1}}{2} =\frac{S}{2}$$

For $n \geq 4$ odd

Since the LHS sum is cyclic, without loss of generality we can assume that $x_{2k+1}$ (otherwise reorder them) is the smallest term. Then $x_{2k+1} \leq x_4$ (here is where we need $n \geq 4$.)

$$x_1x_2+x_2x_3+....+x_{2k+1}x_1 \leq x_1x_2+x_2x_3+....+x_{2k}x_{2k+1}+x_{4}x_1 \leq (x_1+x_3+..+x_{2k} )( x_2+x_4+...+x_{2k-1})$$

Again BY AM_GM you get

$$\sqrt{x_1x_2+x_2x_3+....+x_{2k+1}x_1} \leq \frac{x_1+x_3+..+x_{2k+1} + x_2+x_4+...+x_{2k}}{2} = \frac{S}{2} $$

I have to solve this in 3 parts. First for $n=3$, then for $n=4$ and finally for $n>4$.

For $n=3$ we can take a tranformation $x'_1=x'_2=(x_1+x_2)/2$ and $x'_3=x_3$. $\sum x_i$ remains fixed while $\sum{x'_i*x'_{i+1}}-\sum{x_i*x_{i+1}} = (x_1+x_2)^2/4-x_1*x_2 = (x_1^2+2x_1x_2+x_2^2)/4-x_1*x_2 = (x_1^2-2x_1x_2+x_2^2)/4 = (x_1-x_2)^2/4$
which is $>0$ if $x_1$ differs from $x_2$.
So an optimal solution must have the first two terms equal (otherwise we can apply this transformation and obtain a higher value), but you can cycle the terms, so they must be all equal to $S/3$ for a total sum of $S^2/3$.

For $n=4$ the transformation $x'_1=x_1+x_3$, $x'_3=0$ doesn't change the result, so we take an optimal solution, sum the odd and even terms, and the problem becomes finding the maximum of $(\sum x_{odd})*(\sum x_{even})$, that is maximized if both terms are equal to $S/2$, for a total of $S^2/4$.

For $n>4$, I have to prove this lemma first:

For $n>4$, there is at least one optimal configuration that has at least one index $i$ such that $x_i=0$

Take a configuration that is optimal and such that every $x_i>0$ and $x_1 = max(x_i)$.
Now use the following transformation: $x'_2=x_2+x_4$, $x'_4=0$. $\sum x_i$ remains the same but $\sum{x'_i*x'_{i+1}}-\sum{x_i*x_{i+1}}=x_1*(x_2+x_4)+(x_2+x_4)*x_3+\sum_{i>4}{x_i*x_{i+1}}-\sum{x_i*x_{i+1}} = x_1*x_4-x_4*x_5 = x_4*(x_1-x_5) = x_4*(max(x_i)-x_5) \geq x_4*(x_5-x_5) = 0$
So we have another optimal solution with a $0$.

Given that at least an optimal solution contains a $0$ for every $n>4$, the maximum value of $\sum{x_i*x_{i+1}}$ must be non-increasing for $n$ (otherwise we can take a solution for $n$ with a $0$ inside, remove that $0$, and obtain a higher solution for $n-1$).

Now the value of the sum must be $\leq S^2/4$, but taking $x_1=x_2=S/2$ gives that sum, so that configuration is an optimal one, for a sum of $S^2/4$.

This proves that the maximum is $S^2/3$ if $n=3$ and $S^2/4$ otherwise.

I am not satisfied with this answer, because it breaks down to a lot of case analysis. I am still curious to see a simpler proof (or one that requires less space..).

This should be a comment, but I don't have the reppts.

Consider $x^n-Sx^{n-1}+e_2x^{n-2}+\ldots+(-1)^ne_n=\prod_{i=1}^n(x-x_i)$, rephrasing, quite wrongly, the question to be about finding the maximal $e_2$.

Let $x_i=\frac{S}{n}\forall i$. Then $(x-\frac{S}{n})^n=x^n-n(\frac{S}{n})x^{n-1}+{n\choose 2}(\frac{S}{n})^2x^{n-2}+\ldots$ so we can get as high as $\frac{n-1}{2n}S^2$; tending to but always smaller than $\frac{S^2}{2}$ in general.

This is $\frac{S^2}{3}$ for $n=3$, and $\frac{3}{8}S^2>\frac{S^2}{4}$ for $n=4$.

Edit: $e_2\geq x_1x_2+x_2x_3+\ldots+x_nx_1$, not necessarily equal. Keeping it up, as someone else may make the same error.