Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

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$

share|improve this answer
    
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

Hint: Use Lagrange multiplier method.

share|improve this answer

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

Sequence $a_k=1-\frac{\lambda^2}{4a_{k-1}},\ k=2,3,\ldots,n$.

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.