# Maximum and minimum of $\sum\limits_{k=1}^{n-1}(x_{k}-a)(x_{k+1}-a)$ on $\sum\limits_{k=1}^{n-1}x_{k}=na$ and $x_k\ge 0$

Fix $a$ some positive number and $n$ some positive integer,and assume that $$x_{1}+x_{2}+\cdots+x_{n}=na,x_{i}\ge 0,i=1,2,\cdots,n$$ Find this function maximum and minimum $$f=\sum_{k=1}^{n-1}(x_{k}-a)(x_{k+1}-a)$$

My try: let $$y_{i}=\dfrac{x_{i}}{a}\Longrightarrow y_{1}+y_{2}+\cdots+y_{n}=n$$ then $$f=\dfrac{1}{a^2}\sum_{k=1}^{n-1}(y_{k}-1)(y_{k+1}-1)$$ $$\Longrightarrow f=\dfrac{1}{a^2}\left(y_{1}y_{2}+y_{2}y_{3}+\cdots+y_{n-1}y_{n}-2n+y_{1}+y_{n}+n-1\right)$$ so we only need to find the minimum and maximum value of the following $$g=y_{1}y_{2}+y_{2}y_{3}+\cdots+y_{n-1}y_{n}+y_{1}+y_{n}$$

I want to use AM-GM inequality, but I can't finish.

• Try Lagrange multiplier technique. – Mhenni Benghorbal Feb 18 '14 at 11:47
• can you post your Lagrange multiplier full methods?because sometimes this methods is not good to solve inequality – china math Feb 18 '14 at 11:52
• @chinamath. Where are inequalities ? – Claude Leibovici Feb 18 '14 at 12:03
• It is said this today University walks exam questions – china math Feb 18 '14 at 12:42
• $0<g<\dfrac{n(n+2)}{4}$ – chenbai Feb 18 '14 at 12:53

Plug $(0,n,0,\ldots,0)$ to see $\min g= 0$.
For the maximum, consider $n=2,3$ first, where the problem is immediately solved by AM-GM. The case $n=4$ is a bit more complicated, but not too hard. In the sequel we assume that $n\ge 5$. Since $g$ is continuous and is defined on a compact set, the maximum $g_0$ is attained at some point $(y_1,y_2,\ldots,y_n)$.

Claim. $y_3=\cdots=y_{n-2}$.
Proof. Suppose $y_k\not=y_{k+1}$ for some $3\le k\le n-3$. Then $g(\ldots,\frac{y_k+y_{k+1}}2,\frac{y_k+y_{k+1}}2,\ldots)>g_0$, a contradiction.

The following statement will be used frequently:

Claim. $n^2(n-5)/(n-4)^2\le(n+1)^2/4$, for $n\ge 5$.
Proof. For $n\ge 8$ it's plain since $n-5<n-4$ and $n-4\ge 4$. For $n=5,6,7$ we may check by direct computation.

Now let $y_3=u$, then $$g_0=(y_2+y_{n-1})u+y_1y_2+y_{n-1}y_n+y_1+y_n+(n-5)u^2$$ If $y_2\not=y_{n-1}$ and $\min\{y_1,y_n\}\not=0$, then $(y_1,y_n)\mapsto(y_1+\delta,y_n-\delta)$ will increase $g$ for some $\delta$ (maybe negative). Hence $y_2\not=y_{n-1}\Rightarrow\min\{y_1,y_n\}=0$. Similarly $y_1\not=y_n\Rightarrow\min\{y_2,y_{n-1}\}=0$. Now there are several cases:

Case 1. $y_2=y_{n-1}, y_1=y_n$. If $y_1=y_2=0$, then $$g_0=\frac{n^2(n-5)}{(n-4)^2}$$ which is no more than $(n+1)^2/4$ established in Case 2 and Case 3, a contradiction. Otherwise, if $y_1=y_n\not=0$, then by a perturbation $(y_1,y_n)\mapsto(y_1+\delta,y_n-\delta)$ the value of $g$ leaves unchanged, and the problem is reduced to Case 3; if $y_2=y_{n-1}\not=0$, it can be similarly reduced to Case 2.

Case 2. $y_2\not=y_{n-1}$. WLOG we may assume $y_n=0$.

• Subcase 2.1 If $y_1\not=0$, we have $y_1>y_n$, hence $y_{n-1}=0$ (otherwise $(y_2,y_{n-1})\mapsto(y_2+\delta,y_{n-1}-\delta)$ will increase $g$ for $\delta>0$). So \begin{align} g_0&=y_2u+y_1y_2+y_1+(n-5)u^2\\ &=\frac{y_2(n-y_1-y_2)}{n-4}+y_1y_2+y_1+\frac{(n-5)(n-y_1-y_2)^2}{(n-4)^2} \end{align} The last expression is a convex quadratic function in $y_1$, thus attains its maximum at $y_1=0$ or $y_1=n-y_2$. When $y_1=0$, \begin{align} &\frac{y_2(n-y_2)}{n-4}+\frac{(n-5)(n-y_2)^2}{(n-4)^2}\\ =&-\frac{(n-y_2)^2}{(n-4)^2}+\frac{n(n-y_2)}{n-4}\\ \le&\cases{(5/2)^2,\phantom{n^2(n-5)/(n-4)^2}n=5\\n^2(n-5)/(n-4)^2,\phantom{(5/2)^2}n\ge 6} \end{align} and when $y_1=n-y_2$ we have $$(n-y_2)y_2+n-y_2\le \frac{(n+1)^2}{4}$$ Now we conclude that(note that $(5/2)^2<(5+1)^2/4$) $$g_0\le\max\left\{\frac{n^2(n-5)}{(n-4)^2},~\frac{(n+1)^2}4\right\}=\frac{(n+1)^2}{4}$$

• Subcase 2.2 If $y_1=0$, then \begin{align} g_0&=(y_2+y_{n-1})u+(n-5)u^2\\ &=\Big(n-(n-4)u\Big)u+(n-5)u^2\\ &=-u^2+nu\le\frac{n^2}{4}<\frac{(n+1)^2}4 \end{align} which is strictly smaller than Subcase 2.1, hence cannot be a maximum.

Case 3. $y_1\not=y_n$. WLOG we may assume $y_{n-1}=0$.

• Subcase 3.1 If $y_2\not=0$, by the same reasoning in Subcase 2.1 we have $y_n=0$. Now it's reduced to Subcase 2.1, where $y_{n-1}=y_n=0$.
• Subcase 3.2 If $y_2=0$, then \begin{align} g_0&=y_1+y_n+(n-5)u^2\\ &=n-(n-4)u+(n-5)u^2\\ &\le\max\left\{n,~\frac{n^2(n-5)}{(n-4)^2}\right\}\\ &\le\max\left\{\frac{(n+1)^2}{4},~\frac{n^2(n-5)}{(n-4)^2}\right\}\\ &=\frac{(n+1)^2}{4} \end{align}

We may conclude that for $n\ge 5$, $g_0\le(n+1)^2/4$. And in fact $g_0=(n+1)^2/4$ since $g(\frac{n+1}2,\frac{n-1}2,0,0,\ldots,0)=(n+1)^2/4$.
Combining these results with the the case $n=3,4$, we may say that the maximum is $(n+1)^2/4$ for $n\ge 3$.

P.S. It's also worth mentioning that Lagrange multiplier method, mentioned in the comment, is not well applicable here. The result shows the extremal point is not a solution to the Lagrange multiplier equation.