Kvant Math Problem 257
The inequality can be written as
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m06s
Source on kvant.digital
Problem
For which natural numbers $n \ge 2$ does the inequality $$x_1^2 + x_2^2 \ldots + x_n^2 \ge p(x_1x_2 + x_2x_3 + \ldots + x_{n-1}x_n)$$ hold for all real numbers $x_1$, $x_2$, $\ldots$, $x_n$ if
- $p=1$;
- $p=\dfrac{4}{3}$;
- $p=\dfrac{6}{5}$?
Nguyen Cong Quy (Hanoi)
Exploration
The inequality can be written as
$$Q_n(x_1,\ldots,x_n) = \sum_{i=1}^n x_i^2 - p\sum_{i=1}^{n-1}x_ix_{i+1} \ge 0.$$
We must determine, for each prescribed value of $p$, all $n\ge2$ for which $Q_n$ is nonnegative for every real vector.
The first step is to test small values of $n$.
For $n=2$,
$$Q_2=x_1^2+x_2^2-px_1x_2.$$
The corresponding matrix is
$$\begin{pmatrix} 1&-\frac p2\[2mm] -\frac p2&1 \end{pmatrix},$$
whose determinant equals $1-\frac{p^2}{4}$. Hence $Q_2\ge0$ for all $x_1,x_2$ iff $p\le2$. All three values $1,\frac43,\frac65$ satisfy this.
For $n=3$ and $p=1$,
$$Q_3=x_1^2+x_2^2+x_3^2-x_1x_2-x_2x_3.$$
Using
$$2Q_3=(x_1-x_2)^2+(x_2-x_3)^2+x_1^2+x_3^2,$$
the form is nonnegative.
The structure suggests considering the symmetric tridiagonal matrix
$$A_n= \begin{pmatrix} 1&-\frac p2&&&0\ -\frac p2&1&-\frac p2\ &\ddots&\ddots&\ddots\ 0&&-\frac p2&1 \end{pmatrix}.$$
The problem becomes: for which $n$ is $A_n$ positive semidefinite?
The determinants of leading principal minors satisfy
$$D_k=D_{k-1}-\frac{p^2}{4}D_{k-2}, \qquad D_0=D_1=1.$$
This recurrence can be solved, but there is a more transparent route. The eigenvectors of such matrices are known to be
$$v_j=(\sin\theta,\sin2\theta,\ldots,\sin n\theta), \qquad \theta=\frac{j\pi}{n+1},$$
with eigenvalues
$$\lambda_j = 1-p\cos\frac{j\pi}{n+1}.$$
The smallest eigenvalue is
$$\lambda_{\min} = 1-p\cos\frac{\pi}{n+1}.$$
Hence
$$Q_n\ge0 \text{ for all }x_i \iff 1-p\cos\frac{\pi}{n+1}\ge0.$$
So the condition is
$$p\cos\frac{\pi}{n+1}\le1.$$
Now substitute the three values of $p$.
For $p=1$, the inequality is automatic.
For $p=\frac43$,
$$\cos\frac{\pi}{n+1}\le\frac34.$$
Since $\cos\frac{\pi}{4}=\frac{\sqrt2}{2}<\frac34$ and $\cos\frac{\pi}{5}\approx0.809>\frac34$, the threshold is between $n=3$ and $n=4$. Thus only $n=2,3$ work.
For $p=\frac65$,
$$\cos\frac{\pi}{n+1}\le\frac56.$$
Since
$$\cos\frac{\pi}{5}\approx0.809<\frac56, \qquad \cos\frac{\pi}{6}=\frac{\sqrt3}{2}\approx0.866>\frac56,$$
the threshold is between $n=4$ and $n=5$. Thus only $n=2,3,4$ work.
The step most likely to hide an error is the derivation of the eigenvalues. It must be checked carefully.
Problem Understanding
We must determine all natural numbers $n\ge2$ such that
$$\sum_{i=1}^n x_i^2 \ge p\sum_{i=1}^{n-1}x_ix_{i+1} \qquad \text{for all real }x_1,\ldots,x_n,$$
for each of the three values
$$p=1,\qquad p=\frac43,\qquad p=\frac65.$$
This is a Type A problem. We must classify all admissible $n$.
The inequality is the nonnegativity of a quadratic form associated with a tridiagonal matrix. The core difficulty is determining exactly when this matrix is positive semidefinite.
The expected answer is that admissible $n$ are those satisfying
$$p\cos\frac{\pi}{n+1}\le1.$$
For the three specified values this yields
$$p=1:\ \text{all }n\ge2,$$
$$p=\frac43:\ n=2,3,$$
$$p=\frac65:\ n=2,3,4.$$
Proof Architecture
The first lemma states that the inequality is equivalent to positive semidefiniteness of a tridiagonal symmetric matrix $A_n$.
The second lemma states that for $1\le j\le n$, the vector with coordinates $\sin\frac{ij\pi}{n+1}$ is an eigenvector of $A_n$.
The third lemma computes the corresponding eigenvalue as $1-p\cos\frac{j\pi}{n+1}$.
The fourth lemma states that the smallest eigenvalue equals $1-p\cos\frac{\pi}{n+1}$ because $\cos t$ decreases on $(0,\pi)$.
The final step shows that the quadratic form is nonnegative for all vectors iff this smallest eigenvalue is nonnegative, then evaluates the resulting condition for each prescribed value of $p$.
The hardest direction is proving the eigenvalue formula rigorously.
Solution
Consider the quadratic form
$$Q_n(x_1,\ldots,x_n) = \sum_{i=1}^n x_i^2 - p\sum_{i=1}^{n-1}x_ix_{i+1}.$$
Let
$$A_n= \begin{pmatrix} 1&-\frac p2&0&\cdots&0\ -\frac p2&1&-\frac p2&\ddots&\vdots\ 0&-\frac p2&1&\ddots&0\ \vdots&\ddots&\ddots&\ddots&-\frac p2\ 0&\cdots&0&-\frac p2&1 \end{pmatrix}.$$
Then
$$Q_n(x)=x^TA_nx.$$
Hence the required inequality holds for all real $x_1,\ldots,x_n$ exactly when $A_n$ is positive semidefinite.
For $j=1,\ldots,n$, put
$$\theta_j=\frac{j\pi}{n+1}$$
and define
$$v^{(j)} = (\sin\theta_j,\sin2\theta_j,\ldots,\sin n\theta_j)^T.$$
For an interior index $k$,
$$(A_nv^{(j)})_k = \sin(k\theta_j) -\frac p2\sin((k-1)\theta_j) -\frac p2\sin((k+1)\theta_j).$$
Using
$$\sin((k-1)\theta)+\sin((k+1)\theta) = 2\sin(k\theta)\cos\theta,$$
we obtain
$$(A_nv^{(j)})_k = \bigl(1-p\cos\theta_j\bigr)\sin(k\theta_j).$$
For $k=1$,
$$(A_nv^{(j)})_1 = \sin\theta_j-\frac p2\sin2\theta_j.$$
Since $\sin2\theta=2\sin\theta\cos\theta$,
$$(A_nv^{(j)})_1 = \bigl(1-p\cos\theta_j\bigr)\sin\theta_j.$$
For $k=n$,
$$(A_nv^{(j)})_n = \sin(n\theta_j)-\frac p2\sin((n-1)\theta_j).$$
Because
$$(n+1)\theta_j=j\pi,$$
we have
$$\sin((n-1)\theta_j) = \sin((n+1)\theta_j-2\theta_j) = -\cos(j\pi)\sin2\theta_j,$$
and
$$\sin(n\theta_j) = \sin((n+1)\theta_j-\theta_j) = -\cos(j\pi)\sin\theta_j.$$
Therefore
$$(A_nv^{(j)})_n = -\cos(j\pi) \bigl(\sin\theta_j-\tfrac p2\sin2\theta_j\bigr) = \bigl(1-p\cos\theta_j\bigr)\sin(n\theta_j).$$
Thus
$$A_nv^{(j)} = \lambda_jv^{(j)}, \qquad \lambda_j=1-p\cos\theta_j.$$
The vectors $v^{(j)}$ are nonzero eigenvectors corresponding to $n$ distinct eigenvalues, hence they form a basis of eigenvectors of the symmetric matrix $A_n$.
Since
$$0<\theta_1<\theta_2<\cdots<\theta_n<\pi$$
and $\cos t$ decreases on $(0,\pi)$,
$$\cos\theta_1>\cos\theta_2>\cdots>\cos\theta_n.$$
Consequently
$$\lambda_1<\lambda_2<\cdots<\lambda_n,$$
and the smallest eigenvalue is
$$\lambda_{\min} = 1-p\cos\frac{\pi}{n+1}.$$
A symmetric matrix is positive semidefinite iff all its eigenvalues are nonnegative. Hence
$$Q_n(x)\ge0\ \text{for all }x \iff 1-p\cos\frac{\pi}{n+1}\ge0.$$
Equivalently,
$$p\cos\frac{\pi}{n+1}\le1.$$
We now examine the three values of $p$.
For $p=1$,
$$\cos\frac{\pi}{n+1}\le1$$
for every $n\ge2$. Thus every $n\ge2$ is admissible.
For $p=\frac43$,
$$\cos\frac{\pi}{n+1}\le\frac34.$$
Since
$$\cos\frac{\pi}{4}=\frac{\sqrt2}{2}<\frac34$$
and
$$\cos\frac{\pi}{5}> \frac34,$$
the inequality holds exactly when
$$n+1\le4,$$
that is,
$$n=2,3.$$
For $p=\frac65$,
$$\cos\frac{\pi}{n+1}\le\frac56.$$
Since
$$\cos\frac{\pi}{5}<\frac56$$
and
$$\cos\frac{\pi}{6}=\frac{\sqrt3}{2}>\frac56,$$
the inequality holds exactly when
$$n+1\le5,$$
that is,
$$n=2,3,4.$$
Therefore the complete classification is
$$\boxed{\begin{aligned} &p=1:\quad n=2,3,4,\ldots,\[1mm] &p=\frac43:\quad n=2,3,\[1mm] &p=\frac65:\quad n=2,3,4. \end{aligned}}$$
Verification of Key Steps
The eigenvalue computation depends on the identity
$$\sin((k-1)\theta)+\sin((k+1)\theta) = 2\sin(k\theta)\cos\theta.$$
Substituting this identity into the $k$-th coordinate gives
$$\sin(k\theta)-\frac p2\cdot2\sin(k\theta)\cos\theta = (1-p\cos\theta)\sin(k\theta),$$
which confirms the interior coordinates exactly.
The boundary coordinate $k=n$ is delicate. Since $(n+1)\theta_j=j\pi$,
$$\sin(n\theta_j) = \sin(j\pi-\theta_j) = (-1)^{j+1}\sin\theta_j,$$
and similarly
$$\sin((n-1)\theta_j) = (-1)^{j+1}\sin2\theta_j.$$
Substituting these relations yields
$$(A_nv^{(j)})_n = (-1)^{j+1} \bigl(\sin\theta_j-\tfrac p2\sin2\theta_j\bigr) = (1-p\cos\theta_j)\sin(n\theta_j),$$
so the eigenvalue formula remains valid at the endpoint.
The classification for $p=\frac43$ and $p=\frac65$ relies on monotonicity. Since $\cos t$ decreases on $(0,\pi)$, the function
$$n\mapsto\cos\frac{\pi}{n+1}$$
increases with $n$. Hence checking the first value where the inequality fails is sufficient. For $p=\frac43$, it succeeds at $n=3$ and fails at $n=4$. For $p=\frac65$, it succeeds at $n=4$ and fails at $n=5$. No intermediate cases can be missed.
Alternative Approaches
Instead of diagonalizing the matrix, one may study the leading principal minors. If $D_k$ denotes the determinant of the $k\times k$ leading principal submatrix, then
$$D_k=D_{k-1}-\frac{p^2}{4}D_{k-2}, \qquad D_0=D_1=1.$$
Solving this recurrence yields
$$D_k= \frac{\sin((k+1)\varphi)} {\sin\varphi} \left(\frac p2\right)^k, \qquad \cos\varphi=\frac1p.$$
Sylvester's criterion then reduces positivity to the sign of these determinants and leads to the same condition
$$p\cos\frac{\pi}{n+1}\le1.$$
A second approach uses the discrete sine transform. Expanding an arbitrary vector in the orthogonal basis
$$\sin\frac{ij\pi}{n+1}, \qquad 1\le j\le n,$$
diagonalizes the quadratic form directly. This is essentially the eigenvalue method written in Fourier language. The matrix approach is preferable because it identifies the relevant eigenvalues immediately and yields the classification with the least computation.