Let $ n \geq 3 $ be an integer and let \begin{align*} x_1,x_2, \ldots, x_n \end{align*}be $ n $ distinct integers. Prove that \begin{align*} (x_1 - x_2)^2 + (x_2 - x_3)^2 + \ldots + (x_n - x_1)^2 \geq 4n - 6. \end{align*}
Problem
Source:
Tags: sa, Sequences
04.08.2018 01:16
Solution: We will use induction. For the base case $ n = 2 $ we have \begin{align*} (x_1 - x_2)^2 + (x_2 - x_1)^2 & \geq 2 \\ & = 4 \cdot 2 - 6. \\ \end{align*}Now, assume that for $ n = k $ the following holds \begin{align*} \sum_{i = 1}^{k} ( x_i - x_{i + 1} )^2 \geq 4n - 6, \end{align*}for any $ x_1, \ldots , x_k $ distinct integers. We prove the case for $ n = k + 1 $. Let us consider arbitrary distinct integers $ x_1, \ldots , x_{k + 1} $. Denote \begin{align*} u_i = x_i - x_{i + 1} \quad \text{for all} \quad 1 \leq i \leq k + 1. \end{align*}Then, we have \begin{align*} \sum_{i = 1}^{k + 1} u_i^2 & = u_k^2 + u_{k + 1}^2 + \sum_{i = 1}^{k - 1} u_i^2 \\ & = u_k^2 + u_{k + 1}^2 - (u_k + u_{k + 1})^2 + \sum_{i = 1}^{k} z_i^2 \\ \end{align*}where \begin{align*} z_i = \begin{cases} u_i ,& 1 \leq i \leq k - 1 \\ u_k + u_{k + 1} ,& i = k \end{cases} \end{align*}From the inductive hypothesis, and the definition of $ z_i $, \begin{align*} \sum_{i = 1}^{k} z_i^2 \geq 4k - 6. \end{align*}Hence, \begin{align*} \sum_{ i = 1 }^{ k +1 } u_i^2 & = \sum_{i = 1}^{k}( z_i^2 ) + u_k^2 + u_{k + 1}^2 - (u_k + u_{k + 1})^2 \\ & \geq 4k - 6 +u_k^2 + u_{k + 1}^2 - (u_k + u_{k + 1})^2 \\ & = 4k - 6 - 2 u_k u_{k + 1} \\ \end{align*}Without loss of generality, we can assume that $ x_{k + 1} = \min \{ x_i \mid i \in \{1, \ldots, k + 1 \} \}$(why?). Most importantly, we only need to show that $ (x_k - x_{k + 1})(x_{k + 1} - x_1) \leq - 2 $ in order to finish our inductive step. We proceed as follows: \begin{align*} x_k -x_{ k + 1 } > 0 \quad \text{and} \quad x_{ k + 1 } - x_1 < 0. \end{align*}from the minimality of $ x_{ k + 1 } $ and $ x_i \neq x_j $ for all $ 1 \leq i \neq j \leq k + 1 $. So, our term is negative. The only possible case left to check is if \begin{align*} ( x_k - x_{k + 1} )( x_{k + 1} - x_1 ) = - 1. \end{align*}However, this would imply \begin{align*} (x_k - x_{k + 1})(x_1 - x_{k + 1}) =1. \end{align*}But by definition, we know that $ x_k \neq x_1 $ and hence our two positive terms $ x_k - x_{k + 1}, \quad x_1 - x_{k + 1} $ are distinct, hence, their product is greater than $2 \cdot 1$ and we are done. Thus \begin{align*} \sum_{i = 1}^{k +1} u_i^2 & \geq 4k - 6 - 2u_{k}u_{k + 1} \\ & \geq 4k - 6 + 4 \\ & = 4(k + 1) - 6. \\ \end{align*}The inductive step is complete and the problem is solved. $\blacksquare$ Tags: Solution, mathematical induction Remark: Moreover, we may find a sequence for which the equality holds: In ascending order, all the even numbers from $2$ to $n$, and then continue by adjoining the odd elements in descending order from $n$ to $1$.
20.05.2022 21:34
Call the expresion $S.$ Clearly $S$ is even. Suppose wlog that $x_{n}=\max (x_{1},x_{2},...,x_{n})$ and let $x_{j}=\min (x_{1},x_{2},...,x_{n}).$ Then $1\le j\le n-1$ and $x_{n}-x_{j}\ge n-1.$ Now by Cauchy: \[S=\Big( (x_{n}-x_{1})^{2}+(x_{1}-x_{2})^{2}+...+(x_{j-1}-x_{j})^{2}\Big) +\Big((x_{j+1}-x_{j})^{2}+...+(x_{n}-x_{n-1})^{2}\Big)\]\[\ge \frac{(x_{n}-x_{j})^{2}}{j}+\frac{(x_{n}-x_{j})^{2}}{n-j}=\frac{n(x_{n}-x_{j})^{2}}{j(n-j)}\ge \frac{n(n-1)^{2}}{j(n-j)}\ge _{AM-GM}\frac{4(n-1)^{2}}{n}>4\cdot \frac{(n-1)^{2}-1}{n}=4n-8\]and since $S$ is even, we see that $S\ge 4n-6.$