Maximum of $a_1a_2+a_2a_3+\ldots+a_{n-1}a_n+a_na_1$ where $\sum a_i$ is constant

Question

Non-negative real numbers $a_1,a_2,\ldots,a_n$ are such that $a_1+\ldots +a_n=k$, where $k$ is a constant. Find the maximum value of $$a_1a_2+a_2a_3+\ldots+a_{n-1}a_n+a_na_1$$ For $n=2$ we can reach $\frac{k^2}{2}$ with $a_1=a_2=\frac{k}{2}$.

For $n=3$ we can reach $\frac{k^2}{3}$ with $a_1=a_2=a_3=\frac{k}{3}$.

For $n\geq 4$, I suspect $\frac{k^2}{4}$ is the limit, at least when $n$ is even, since we can split $k$ into $$S=a_1+a_3+\ldots+a_{n-1}$$ $$k-S=a_2+a_4+\ldots+a_n$$ Notice that the product $S(k-S)$ contains all the terms of the expression we want to maximise. In other words $$a_1a_2+a_2a_3+\ldots+a_{n-1}a_n+a_na_1$$ $$\leq (a_1+a_3+\ldots+a_{n-1})(a_2+a_4+\ldots+a_n)$$ $$=S(k-S)=\frac{k^2}{4}-(S-\frac{k}{2})^2\leq\frac{k^2}{4}$$

Answer 1

We claim that for $n\ge 4$, given that $\sum_{j=1}^nx_j=k$ and identifying $x_{n+1}:=x_1$, we have $$\sum_{j=1}^n x_{j}x_{j+1}\le \frac{k^2}{4}$$ Towards a proof, we divide the problem into 2 cases.

If $n=2k,\ k\in\mathbb N$ (that is $n$ is even), we just have

$$\sum_{j=1}^n x_{j}x_{j+1}\le (x_1+x_3+\cdots+x_{2k-1})(x_2+x_4+\cdots+x_{2k})\le \left(\frac{\sum_{j=1}^nx_{j}}{2}\right)^2=\frac{k^2}{4}$$

where the second inequality follows from the AM-GM inequality.

If $n=2k+1,\ k\in\mathbb N$ (that is $n$ is odd), rearrange the elements such that $x_1$ is the least element (if not, then just cyclically permute the elements until it is, and then note that cyclic permutations do not change any of the summations). Then \begin{align*}(x_1+x_3+\cdots +x_{2k+1})(x_2+x_4+\cdots +x_{2k})&\ge \sum_{j=1}^{n-1}x_jx_{j+1}+x_{2k+1}x_{2}\\&\ge \sum_{j=1}^{n-1}x_jx_{j+1}+x_{2k+1}x_1\\&=\sum_{j=1}^{n}x_jx_{j+1}\end{align*}

Hence $$\sum_{j=1}^{n}x_jx_{j+1}\le (x_1+x_3+\cdots +x_{2k+1})(x_2+x_4+\cdots +x_{2k})\le \left(\frac{\sum_{j=1}^nx_{j}}{2}\right)^2=\frac{k^2}{4}$$

where again the second inequality comes from the AM-GM inequality.

Thus for all cases, the inequality is proven. That this is the maximum value is seen by just putting in $$(x_1,\ x_2,\dots,\ x_n)=\left( \frac{k}{2},\ \frac{k}{2},\ 0,\ 0,\ \cdots,\ 0\right)$$

at which point the bound is reached.

Answer 2

I use the method of Lagrange multipliers.

Maximize $f(x_1,x_2,...,x_n)=x_1x_2+x_2x_3+...+x_{n-1}x_n+x_nx_1$

Subject to $g(x_1,x_2,...,x_n)=x_1+x_2+...+x_{n-1}+x_n=k$

$f_{x_i}=\lambda g_{x_i}$ for $i=1,2,...,n$ gives $x_i+x_{i+2}=\lambda$ for all $i=1,...,n-2$ and $x_{n-1}+x_1=\lambda$ and $x_n+x_2=\lambda$. Those last two equations are extremely confusing... So, from the constraint condition we find $x_i=\frac{k}{n}$ for all $i$, since the linear system has non-zero determinant and there is a unique solution. But then $f(\frac{k}{n},\frac{k}{n},...,\frac{k}{n})=n\frac{k^2}{n^2}=\frac{k^2}{n}$. This is not the answer unless $n=4$! Did we find the minumum? No. The minumum is zero. Anyway. The question asks the maximum. How can I save this method?

I hope this explanation works: Therefore, the maximum happens on the boundry of the closed region ($x_i\geq 0$) that the function $f$ is defined. This boundry is $x_i=0$ hyperplanes. Taking $x_n=0,x_{n-1}=...=x_3=0$ inductively we can reduce the problem to: Maximize $x_1x_2$, subject to $x_1+x_2=k$. But the answer of this question is well-known and it is $\frac{k^2}{4}$.

Explanation of the induction here for $n=4$: On hyperplane $x_4=0$, we have $$x_1x_2+x_2x_3+x_3x_4+x_4x_1=x_1x_2+x_2x_3=(x_1+x_3)x_2=x'_1x_2$$ with the condition $x'_1+x_2=k$. I hope this is convincing for the hackers.