Prove:$|x-1|+|x-2|+|x-3|+\cdots+|x-n|\geq n-1$

Question

Prove:$|x-1|+|x-2|+|x-3|+\cdots+|x-n|\geq n-1$

example1: $|x-1|+|x-2|\geq 1$

my solution：(substitution)

$x-1=t,x-2=t-1,|t|+|t-1|\geq 1,|t-1|\geq 1-|t|,$

square,

$t^2-2t+1\geq 1-2|t|+t^2,\text{Since} -t\leq -|t|,$

so proved.

question1 : Is my proof right? Alternatives?

one reference answer:

$1-|x-1|\leq |1-(x-1)|=|1-x+1|=|x-2|$

question2 : prove:

$|x-1|+|x-2|+|x-3|\geq 2$

So I guess:( I think there is a name about this, what's that? wiki item?)

$|x-1|+|x-2|+|x-3|+\cdots+|x-n|\geq n-1$

How to prove this? This is question3. I doubt whether the two methods I used above may suit for this general case.

Of course, welcome any interesting answers and good comments.

Answer 1

Actually, $|x-n| + |x-1| = |n-x| + |x-1| \geq |n-1|=n-1$. Don't need the other terms.

Your first proof is correct. You have to take some care moving from $U^2\geq V^2$ to $U\geq V$, but in this case, $U=|t-1|$ is non-negative.

Answer 2

After the answer of Thomas Andrews my answer appears to be dispensable. But I'll leave it here as a poor alternative. Here a proof valid for any $ x $ since $ n $ is even. For the case $ n $ odd simply discard the parcel | x-n |. \begin{align} |x-1|+|x-2|+|x-3|+\ldots+|x-n| = & |x-1|+|2-x|+|x-3|+ \\ + & \ldots+|(-1)^{n+1}x+(-1)^{n}n| \\ \geq & \bigg[(1-x)+(x-2)+(3-x)+ \\ + & \ldots+(-1)^{n}x+(-1)^{n+1}n\bigg] \\ = & (-1)^1+(-1)^{2}2+(-1)^{3}3+(-1)^{4}4+\ldots \\ + & (-1)^{(n-1)}(n-1)+n(-1)^{n} \\ = & \frac{n}{2}+n(-1)^{n}= \frac{n}{2}+n\geq n \end{align}

Answer 3

Note that the sum $F(x)=|x-1|+|x-2| +\cdots +|X-n|$ is the sum of the distances from $x$ to the points $1,2,\dots,n$. Draw the $n$ points $1,2,3,\dots,n$ on the number line, taking $n$ say $7$ or $8$.

Imagine that a particle $P$ starts far to the left of $1$, and travels to the right.

Until it hits $x=1$, the sum is of the distances of $P$ from $1,2,\dots, n$ is decreasing. At $x=1$ it becomes $1+2+\cdots+(n-1)$.

As we travel from $1$ to $2$, the function $F(x)$ is decreasing. For each tiny step $s$ we take to the right increases our distance from $1$ by $s$, but it decreases our distance from each of $2, 3,\dots,n$ by $s$. So each tiny step $s$ we take decreases $F(x)$ by $(n-1)s-s$.

If $n$ is not too small, this decrease continues. For each small step $s$ we take from $2$ towards $3$ increases our distance from $1$ and $2$ by $s$, and decreases our distance from each of the other points by $s$, for a decrease of $(n-2)s-2s$.

If $n$ is odd, $F(x)$ keeps decreasing until $x=\frac{n+1}{2}$, and then by symmetry $F(x)$ starts to increase. If $n$ is even, then $F(x)$ reaches a minimum at all points between $\frac{n}{2}$ and $\frac{n+1}{2}$.

For $n$ odd, say $n=2k+1$, the minimum value of $F(x)$ is $2(1+2+3+\cdots +k)$. This is $k(k+1)$. For $n$ even, say $n=2k$, the minimum value of $F(x)$ is $(1+2+\cdots +(k-1))+(1+2+\cdots +k)$. This is $k^2$.

Back to the question in the post.

We want to show that if $n$ is odd, say $n=2k+1$, then $k(k+1) \ge 2k$, and that if $n$ is even, say $2k$m then $k^2\ge 2k-1$. Both of these are obvious.

Remark: We wrote out a solution in order to emphasize the geometry of the situation.

Generalization: Suppose that instead of $1,2,\dots,n$ we have numbers $a_1 \le a_2\le a_3\le \cdots \le a_n$.

Play the same walking game. If $n=2k+1$ is odd, then $F(x)$ reaches its minimum at $x=k+1$. The number $a_{k+1}$ is the median of our $n$ numbers $a_1,\dots, a_n$.

If $n$=2k is even, then $F(x)$ reaches a minimum at all points between $x=k$ and $x=k+1$. Any such $x$ can be viewed as a median of the $a_i$.

Answer 4

You want $S(x) =\sum_{i=1}^n |x-i|$.

I will show

$\begin{cases} \text{if } x \le 1&S(x) \ge \dfrac{n(n-1)}{2}\\ \text{if } x \ge n &S(x) \ge \dfrac{n(n-1)}{2}\\ \text{otherwise} &S(x) \ge \dfrac{n^2-1}{4} \end{cases} $

Exact results are

$\begin{cases} \text{if } x \le 1, & S(x) = n(1-x) + \dfrac{n(n-1)}{2}\\ \text{if } x \ge n, & S(x) = n(x-n)+ \dfrac{n(n-1)}{2}\\ \text{if } j\le x < j+1 \text{ where } 1 \le j < n, &S(x) = \dfrac{n^2+(n-2x+1)^2-(1-2y)^2}{4}\text{ where } y=x-j \end{cases} $

As a check, these are correct for $x=0, 1, n$, and $n+1$.

We consider three cases: $x \le 1$, $x \ge n$, and $1 < x < n$.

If $x \le 1$, then $|x-i| = -x+i$, so

$\begin{align} S(x) &= \sum_{i=1}^n (-x+i)\\ &=-nx + \frac{n(n+1)}{2}\\ &=n(1-x)-n+ \frac{n(n+1)}{2}\\ &=n(1-x) +\frac{n(n-1)}{2}\\ \end{align} $

If $x \ge n$, then $|x-i| = x-i$, so

$\begin{align} S(x) = \sum_{i=1}^n (x-i) &=nx - \frac{n(n+1)}{2}\\ &=n(x-n)+n^2 - \frac{n(n+1)}{2}\\ &=n(x-n) \frac{2n^2-n(n+1)}{2}\\ &= n(x-n)+\frac{n^2-n}{2}\\ &= n(x-n)+\frac{n(n-1)}{2}\\ \end{align} $

If $j \le x < j+1$ where $1 \le j < n$, let $y = x-j$, so $0 \le y < 1$. Then

$\begin{align} S(x) &=\sum_{i=1}^n |x-i|\\ &=\sum_{i=1}^n |j+y-i|\\ &=\sum_{i=1}^j |j+y-i|+\sum_{i=j+1}^n |j+y-i|\\ &=\sum_{i=1}^j (j+y-i)+\sum_{i=j+1}^n -(j+y-i)\\ &=\sum_{i=1}^j (j+y-i)+\sum_{i=j+1}^n (i-j-y)\\ &=jy+\sum_{i=0}^{j-1} (i)-(n-j)y+\sum_{i=1}^{n-j} (i)\\ &=(2j-n)y+\frac{j(j-1)+(n-j)(n-j+1)}{2}\\ &=(2j-n)y+\frac{j^2-j+(n-j)^2+(n-j)}{2}\\ &=(2j-n)y+\frac{(n^2+(n-2j)^2)/2+(n-2j)}{2}\quad (*)\\ &=(2j-n)y+\frac{n^2+(n-2j)^2+2(n-2j)}{4}\\ &=\frac{n^2+(n-2j)^2+2(n-2j)-4y(n-2j)}{4}\\ &=\frac{n^2+(n-2j)^2+2(1-2y)(n-2j)}{4}\\ &=\frac{n^2+(n-2j+1-2y)^2-(1-2y)^2}{4}\\ &=\frac{n^2+(n-2x+1)^2-(1-2y)^2}{4}\\ &\ge \frac{n^2-1}{4}\\ \end{align} $

Note: The line marked "(*)" used $a^2+b^2 = \dfrac{(a+b)^2+(a-b)^2}{2}$.

Answer 5

(Edited)

Given a real-valued data set ${\bf y}=(y_k)_{1\leq k\leq n}$ the function $$f(x):=\sum_{k=1}^n |x-y_k|$$ assumes its minimum at the median $\mu$ of ${\bf y}$. When $y_1\leq y_2\leq \ldots\leq y_n$ and $n=2m+1$ then $\mu=y_{m+1}$ (the "middle value"), and if $n=2m$ then $f$ is actually constant on the interval $[y_m,y_{m+1}]$, and one defines $\mu:=(y_m+y_{m+1})/2$.

Proof. When there are $r$ more $y_k$ to the right of $x$ than to the left of $x$ then increasing $x$ by $\Delta x$ will decrease $f$ by $r\cdot\Delta x$, and similarly, when there are $r$ more $y_k$ to the left of $x$ than to the right of $x$ then increasing $x$ by $\Delta x$ will increase $f$ by $r\cdot \Delta x$.$\qquad\square$

It follows that your sum $s(x)$ is minimal at $x={n+1\over2}$. It is then easily computed to $s_{\min}=n^2/4$ when $n$ is even and $s_{\min}=(n^2-1)/4$ when $n$ is odd.

When $n=1$ we have $s_{\min}=0=n-1$, and in the case $n=2$ we have $s_{\min}=1=n-1$. For $n\geq3$ we can argue as follows: $$s_{\min}\geq{n^2-1\over 4}={(n-2)^2-1\over4}+n-1\geq n-1\ .$$