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

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}$$

• You can do better than k^2/n: by letting a_1=a_2=k/2, you will obtain k^2/2 for n=2 and k^2/4 otherwise, which is better than k^2/n for n>4. I believe you cannot obtain better than this (and better than k^2/3 for n=3), but I don't see the proof for now. Oct 23, 2022 at 5:35
• @AshtonParks Welcome to Math SE. FYI, using an Approach0 search, I found $k=1$ handled in the AoPS can you use the adjustment method, & the somewhat related (but also more general) Maximum of $\sum_{cyc}x_1x_2x_3\cdots x_k$ given $x_1+x_2+\ldots+x_n=a$ for non-negative $x_1,\ldots,x_n$ for a positive integer $n$ and $1<k<n$. Oct 23, 2022 at 6:03
• Use Lagrange multipliers. Oct 23, 2022 at 6:33
• Thanks @bdx77. You're right, $\frac{k^2}{4}$ is a better limit. I've updated the question with this in mind. Oct 23, 2022 at 6:48
• Thank you @John Omielan, I hadn't heard of Approach Zero before. Seems useful. Oct 23, 2022 at 6:50

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.

• You don'T know calculus then. Oct 23, 2022 at 16:40
• I am sorry, what do you mean by that? Oct 23, 2022 at 16:42
• Very nice solution, @HackR. Oct 23, 2022 at 22:49

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.

• The boundary points have one coordinate equal to zero. How did you do induction? Oct 23, 2022 at 8:08
• They may have other coordinates equal to zero. For example, the hyperplane $x_n=0$ has the point $(*,*,...,*,0,0)$. Oct 23, 2022 at 8:16
• I agree with sir Mariano. There seems to be something missing from the induction, because I am not sure I follow? Maybe flesh it out a bit more? Oct 23, 2022 at 14:03
• I think the backlash here is more regarding the unclear answer than people "not liking calculus". First, your use of Lagrange Multipliers ignores the non-negativity constraint on each $x_i$ with no reason why. The rest of the answer is a bit confusing too, it could use line-breaks and less phrases like " Those last two equations are extremely confusing... So, from the constraint condition[...]"
– jDAQ
Oct 23, 2022 at 18:47
• I think you are missing my point. It is nice to have an alternative approach, but your answer is confusing. If you could clear it up maybe people would be convinced/understand it and upvote it.
– jDAQ
Oct 23, 2022 at 19:00