Approximating sum of absolute vales by a quadratic function

Question

Here's a really neat thing I just found:

Consider, for instance, $$\sum _{k=-20}^{20} \left| x-k\right|$$

It's plot (after adjusting scaling) looks like

This looks suspiciously quadratic, and we can in fact overlay $y = x^2 + 420$ to find that they line up quite nicely: .

Moreover, for integer values of $x$ within the domain $[-21,21]$, we find that the values reached by these two functions are equal.

I suspect that if we changed the summation step size to be smaller, we would find that it began to approximate even for non-integer values of $x$ as well.

Can someone explain why this property occurs?

Answer 1

Let's study what happens to the value of the summation as $x \rightarrow x+1$.

For every $k$ such that $k < x$, the value goes down by 1.
For every $k$ such that $k \geq x$, the value goes up by 1.
So $f(x+1)$ - $f(x) = \#(k \geq x) - \#(k < x)$.

Within $x \in [-20, 20]$, we have $\#(k < x) = 20 +x$ and $\#(k \geq x) = 21-x$. So $f(x+1) - f(x) = (21 - x) - (20 + x) = 2x + 1$.

Now let's set $g(x) = x^2 + c$, and study $g(x+1) - g(x)$. We have $(x+1)^2 + c - x^2 - c = 2x + 1$.

So within $x \in [-20, 20]$ we have $f(x+1) - f(x) = g(x+1) - g(x)$. So if we choose $c$ appropriately, for integer values $\in [-20, 20]$ we'll have $f = g$.

Answer 2

$$f(x) = \sum_{k=-n}^n|x-k| =\sum_{k=-n}^{0}|x-k| + \sum_{k=0}^n|x-k| - |x| $$ $$=\sum_{k=0}^n\left(|x-k+n| + |x-k|\right) -|x|$$

If $x\in\{0,1,2,...,n\}$

$$f(x) = \sum_{0\le k\le x}(2x-2k+n) + \sum_{x < k\le n}n\ - \ x$$

$$ = \left[2x(x+1)-x(x+1) +n(x+1)\right] + [(n-x)n] - x$$ $$ = x^2 + n(n+1)$$

And similarly if $-n \le x < 0$ (just some absolute value/index changes).

Answer 3

Hint:  take an $\,x \in [-20, 21)\,$, then $\,-20 \le m = \lfloor x \rfloor \lt 21\,$, and:

$$ \;|x-k| = \begin{cases} \;x - k \quad\text{for}\;\;-20 \le k \le m \\ \;k - x \quad\text{for}\;\;m+1 \le k \le 20 \end{cases} $$

It follows that (for $\,-20\le m\le20\,$):

$$ \begin{align} \sum _{k=-20}^{20} \left| x-k\right| &= \sum _{k=-20}^{m} (x-k) + \sum _{k=m+1}^{20} (k-x) \\[3px] &= (m+21)x - \sum _{k=-20}^{m} k + \sum _{k=m+1}^{20} k - (20-m)x \\[3px] &= (2m+1) x - (m+21)\cdot \frac{-20 + m}{2} + (20-m)\cdot\frac{m+1 + 20}{2} \\[3px] &= (2m+1)x + (m+21)(20-m) \\ &= (2 \lfloor x \rfloor+1)x - \lfloor x \rfloor^2 - \lfloor x \rfloor + 420 \end{align} $$

The latter expression explains the quadratic behavior, as well as the coincidence at integer $x\,$.

The quadratic behavior quickly degrades outside $\,(-21,21)\,$ as can be verified here.