6
$\begingroup$

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.

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ wow, Is it possible to improve my question and guess, more meaningful? $\endgroup$ – HyperGroups Jul 9 '13 at 15:13
  • $\begingroup$ It's not clear what you mean by your "guess." There are certainly better lower bounds for the left side of this inequality. $\endgroup$ – Thomas Andrews Jul 9 '13 at 15:18
  • $\begingroup$ For example adjust the number $n-1$ of the right side to other number? I'd like to see some tricks and methods used in example 1 and example 2 also suit for summation of n terms... $\endgroup$ – HyperGroups Jul 9 '13 at 15:21
  • $\begingroup$ @HyperGroups $|x-(n-1)|+|x-2| \geq n-3$... $|x-k|+|x-n-k| \geq n-2k$ add those you get that your LHS is $\geq (n-1)+(n-3)+(n-5)+...$. $\endgroup$ – N. S. Jul 9 '13 at 15:23
  • 1
    $\begingroup$ Yes, it turns out, the minimum value is taken when $x=\frac{1+n}{2}$. $\endgroup$ – Thomas Andrews Jul 9 '13 at 15:28
7
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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}

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ If $x$ is in the center, the sum is $\approx 2(1+2+...+(n/2)) = 2\frac{(n/2)(n/2+1)}{2} = \frac{n^2+2n}{4}$. $\endgroup$ – marty cohen Jul 10 '13 at 6:29
  • $\begingroup$ @marty cohen: That was a blunder; I have edited my answer accordingly. $\endgroup$ – Christian Blatter Jul 10 '13 at 8:18
  • $\begingroup$ So the minimum is $\left\lfloor\frac{n^2}{4}\right\rfloor$, which is greater or equal to $n-1$ for integer $n\ge1$. $\endgroup$ – robjohn Jul 10 '13 at 10:16
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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