# Find the maximum and minimum of $\sum_{i=1}^{n-1}x_ix_{i+1}$ subject to $\sum_{i=1}^nx_i^2=1$.

Find the maximum and minimum of

$$\sum_{i=1}^{n-1}x_ix_{i+1}$$ subject to $$\sum_{i=1}^nx_i^2=1$$ for all $n\in\mathbb{N}-\{1,0\}$.

-

Answer: max is $\displaystyle\cos{\frac{\pi}{n+1}}$, min is $\displaystyle -\cos{\frac{\pi}{n+1}}$.

It can be used Lagrange multiplier method.

Let $\mathbf{x}=(x_1,x_2, \ldots,x_n)$.

We have function $f(\mathbf{x}) = x_1 x_2 + x_2x_3+\cdots + x_{n-1}x_n \rightarrow \max$,
and we have condition $g(\mathbf{x}) = x_1^2 + x_2^2+\cdots+x_n^2-1 = 0$.

We create other function $$F(\mathbf{x},\lambda) = f(\mathbf{x}) + \lambda \cdot g(\mathbf{x}).$$

If $F(\mathbf{x},\lambda)$ has extremum somewhere, then all partial derivatives must be 0 here. So, we have (n+1) conditions:

$\left\{ \begin{array}{r} x_2 + 2\lambda x_1 = 0, \\ x_1 + x_3 + 2\lambda x_2 = 0, \\ x_2 + x_4 + 2\lambda x_3 = 0, \\ \cdots \\ x_{n-2}+x_n+2\lambda x_{n-1} = 0, \\ x_{n-1}+2\lambda x_n = 0; \\ x_1^2 + x_2^2+\cdots+x_n^2-1 = 0. \end{array} \right.$

We can consider $\lambda$ as parameter for first $n$ equations. Then the system of first $n$ linear equations has 3-diagonal matrix

$M_n(\lambda) = \left( \begin{array}{cccccc} 2\lambda & 1 & 0 & \cdots & 0 & 0 \\ 1 & 2\lambda & 1 & \ddots & 0 & 0 \\ 0 & 1 & 2\lambda & \ddots & 0 & 0 \\ \vdots & \ddots & \ddots & \ddots & \ddots & \vdots \\ 0 & 0 & 0 & \ddots & 2\lambda & 1\\ 0 & 0 & 0 & \cdots & 1 & 2\lambda \\ \end{array} \right).$

We see that $\det M_1(\lambda) = 2\lambda$, $\det M_2(\lambda) = 4\lambda^2-1$,
$\det M_{n+1}(\lambda) = 2\lambda \det M_n(\lambda) - \det M_{n-1}(\lambda)$.
It is recurrent formula for Chebyshev polynomials of the second kind (by definition).
So, for $\lambda_j = \cos(j\pi/(n+1))$ we have $\det M_n(\lambda_j) = \frac{\sin(j\pi)}{\sin(j\pi/(n+1))}=0$, where $j=1,\ldots,n$.

It is easy to see that for $\lambda = \lambda_j$, $j=1,\ldots,n$, we have $\mathbf{x}_j = (x_{j1}, \ldots, x_{jn} )$, where $x_{jk} = C_j \sin \frac{(n+1-j)k\pi}{n+1}$, $k=1,\ldots,n$.

Condition $g(\mathbf{x}_j)=0$ implies $C_j = \sqrt{2/(n+1)}$.

$f(\mathbf{x}_j) = \cos \frac{(n+1-j)\pi}{n+1}$.

So, $\max\limits_{g(\mathbf{x})=0} f(\mathbf{x}) = \max\limits_{j=1,\ldots,n} \cos\frac{(n+1-j)\pi}{n+1} = \cos \frac{\pi}{n+1}$. (It is attained when $j = n$).

$\min\limits_{g(\mathbf{x})=0} f(\mathbf{x}) = \min\limits_{j=1,\ldots,n} \cos\frac{(n+1-j)\pi}{n+1} = \cos \frac{n\pi}{n+1} = -\cos \frac{\pi}{n+1}$. (It is attained when $j = 1$).

$\max\limits_{g(\mathbf{x})=0} |f(\mathbf{x})| = \cos \frac{\pi}{n+1}$. (obviously).

$\min\limits_{g(\mathbf{x})=0} |f(\mathbf{x})| = \min\limits_{j=1,\ldots,n} \left|\cos\frac{(n+1-j)\pi}{n+1} \right| =$ $\left\{ \begin{array}{cl} 0, & \mbox{when } n \mbox{ is odd}, (\mbox{ when } j=(n+1)/2) \\ \cos \frac{n\pi}{2n+2}, & \mbox{when } n \mbox{ is even}, (\mbox{ when } j=n/2 + 1). \end{array} \right.$

Examples:

$n=2$: $f_{max} = \cos{\frac{\pi}{3}}$, $$(x_1,x_2) = \left( \sqrt{\frac{2}{3}} \sin{\frac{\pi}{3}}, \sqrt{\frac{2}{3}} \sin{\frac{2\pi}{3}}\right);$$

$n=3$: $f_{max} = \cos{\frac{\pi}{4}}$, $$(x_1,x_2,x_3) = \left( \sqrt{\frac{2}{4}} \sin{\frac{\pi}{4}}, \sqrt{\frac{2}{4}} \sin{\frac{2\pi}{4}}, \sqrt{\frac{2}{4}} \sin{\frac{3\pi}{4}} \right);$$

$n=4$: $f_{max} = \cos{\frac{\pi}{5}}$, $$(x_1,x_2,x_3,x_4) = \left( \sqrt{\frac{2}{5}} \sin{\frac{\pi}{5}}, \sqrt{\frac{2}{5}} \sin{\frac{2\pi}{5}}, \sqrt{\frac{2}{5}} \sin{\frac{3\pi}{5}}, \sqrt{\frac{2}{5}} \sin{\frac{4\pi}{5}} \right);$$

$n=5$: $f_{max} = \cos{\frac{\pi}{6}}$, $$(x_1,x_2,x_3,x_4,x_5) = \left( \sqrt{\frac{2}{6}} \sin{\frac{\pi}{6}}, \sqrt{\frac{2}{6}} \sin{\frac{2\pi}{6}}, \sqrt{\frac{2}{6}} \sin{\frac{3\pi}{6}}, \sqrt{\frac{2}{6}} \sin{\frac{4\pi}{6}}, \sqrt{\frac{2}{6}} \sin{\frac{5\pi}{6}} \right);$$

$\cdots$

-
I dont' get the first sentence. Are you saying that the maximum and the minimum is attained by constant functions? – leonbloy Dec 28 '12 at 19:06
Yes @leonbloy, I say that $\max\limits_{(x_1,\ldots,x_n)\in \Omega} \left\{ \sum\limits_{j=1}^{n-1} x_j x_{j+1}\right\} = \cos{\frac{\pi}{n+1}}$, where $\Omega = \{(x_1,\ldots,x_n) \in \mathbb{R}^n, x_1^2+\ldots+x_n^2=1\}$. It can be attained when $x_j = \sqrt{2/(n+1)}\sin{\frac{j\pi}{n+1}}$, $j=1,\ldots,n$. – Oleg567 Dec 28 '12 at 19:49
@leonbloy: ... and $\min\limits_{(x_1,\ldots,x_n)\in\Omega} \left \{ \sum\limits_{j=1}^{n-1} x_j x_{j+1} \right\} = - \cos \frac{\pi}{n+1}$; it can be attained when $x_j = (-1)^j \sqrt{2/(n+1)} \sin\frac{j\pi}{n+1}$, $j=1,\ldots,n$. – Oleg567 Dec 28 '12 at 21:24
$M_n(\lambda)$ first is a matrix and later it seems to be the determinant of a matrix – miracle173 Jan 5 '13 at 9:48
@miracle173: thank you, I fixed it now. – Oleg567 Jan 5 '13 at 12:34

We can write the original expression as

$-1/r + (1/r)(\sum_{i=1}^{n}x_i^2+r\sum_{i=1}^{n-1}x_ix_{i+1})$

And completing the squares we get a sequence $\{a_n\}$ with

$\sum_{i=1}^{n}x_i^2+r\sum_{i=1}^{n-1}x_ix_{i+1}=\sum_{k=1}^{n-1}(\sqrt{a_k}x_k+\frac{r}{2\sqrt{a_k}}x_{k+1})^2$.

From

we can pick $r=\pm\frac1{\cos{\frac{\pi}{n+1}}}$ for maximum and minimum. It remains to verify we can attain equality.

-