Minimizing sum $\sum_{k=1}^n |x_k-a|$, $a=\text{median}_{k}(x_k)$ I was trying to prove some theorem on my way. So the problem was:

Theorem: Let $x_1, x_2, ..., x_n$ be the rising sorted sequence of numbers. The 
  $ \sum_{k=1}^n |x_k-a|$  reaches it minimum if $a=median(x_1, x_2,..., x_n)$.

Proof:
First we need to look at that sum if $n=2$. Then we have $$|x_1-a|+|x_2-a|\geqslant|x_2-x_1|=x_2-x_1,$$ because the sequence is rising. So we have that the minimum of that sum is if $$a\in[x_1,x_2]$$
And we know that the median of sequence in that case is really in that interval.
Now let $n$ be any number greater than 2. And lets look first of all at the "boundaries" of the sum, to be more specific $$|x_1-a|+|x_n-a|\geqslant x_n-x_1$$
So as in the case, when $n$ was 2, we get:
$$a\in[x_1,x_n]$$
Now let us look some closer parts - $x_2$ and $x_{n-1}$.
Repeating our thoughts, we get 
$$a\in[x_2, x_{n-1}]$$ 
Which is the sub-interval of the first sum we look it, that means that the $$|x_1-a|+|x_n-a|$$
is still minimal of all possibles. Now we repeat that until we get:


*

*if $n=2k$
$$a\in[x_k,x_{k+1}]$$
Where we can find the median.

*if $n=2k+1$
$$a=x_{k+1}$$
Which is the median.
Now, if we try to get another $a$, suppose $a\in[x_3,x_{n-2}]$, but $a\notin[x_4,x_{n-3}]$, our sum will be the same until $x_4$ but after that it will rise.
So if we get any other number the sum will be greater thus this sum reaches its minimum if $a$ is what we get.   $\square$
So is this a good proof or I am missing something? Thanks in advance!
 A: Your proof seems perfectly fine, except that you need to prove that $\mid x_1 - a \mid + \mid x_2 - a \mid$ has minimum when $x_1\le a \le x_2$.
Actually all that those subinterval thins are not needed. If $n=2k$ assume that $x_{k} \le a \le x_{k+1}$ and then since the sequence is sorted, we have: $x_i \le a \le x_{n-i+1}$ $\forall i \in [1,k]$. Then from the previous statement we have that all sums $\mid x_i - a \mid + \mid x_{n-i} - a \mid$ are minimized. Now the median of the sequence is $x_{k+1}$, and certainly $x_k\le x_{k+1} \le x_{k+1}$ holds and so all the sums are minimized.
Simularly if $n=2k+1$ set $a=x_{k+1}$ and since $x_i \le a \le x_{n-i+1}$ $\forall i \in [1,k]$, the sums are all minimized and also the lone sum $\mid x_{k+1} - a \mid$ reaches its minimum of 0. Hence the proof.
A: I like your approach, and it works in principle.
I think you should take a couple of lines at the top to show / state the obvious for the $n=1$ case, that the minimum value of $0$ is obtained at $a=x_1$. Then demonstrate more thoroughly (as Stefan also says) that the minimum value for $n=2$ actually does occurs when $x_1\le a\le x_2$. You could consider at least one case where $a$ is outside this interval and compare.
Your closing statement could also use a little work, it's not entirely clear to me what that is adding.
It has a form that would work well as an inductive proof.
