Minimum of $f_n(x)= \sum\limits_{i=0}^{n} (-1)^{i} |x+i|$

Question

How does one systematically find the minimum of

$$f(x)= \sum_{i=0}^{n} (-1)^{i} |x+i|$$

where $x \in \mathbf{R}$? Experimentation on Wolfram Alpha shows a specific pattern, but I'm thinking about using bounding arguments. If $f(x)= \sum_{i=0}^{n} |x+i|$, then repeated uses of the triangle inequality works, but I can't seem to use the triangle inequality to bound $\sum_{i=0}^{n}(-1)^{i} |x+i|$.

Answer 1

Let $n=2m-1$ be odd. The simple function $$\phi(x):=|x|-|x+1|=\left\{\eqalign{&\ \quad1\qquad\quad(x\leq-1) \cr &-2x-1\quad(-1\leq x\leq0)\cr&\quad-1\qquad\ \ (x\geq0)\cr}\right.$$ is $\equiv1$ for $x\leq-1$, then has a ramp of slope $-2$ in the interval $[{-1},0]$, and is $\equiv-1$ for all $x\geq0$.

Since $$f_{2m-1}(x)=\sum_{j=0}^{m-1} \phi(x+2j)$$ the function $f_{2m-1}$ is a sum of $m$ copies of $\phi$ translated to the left by amounts $2j\geq0$ $(0\leq j\leq m-1)$. It therefore has $m$ such descending ramps, the leftmost beginning at $-1-2(m-1)=-(2m-1)$. It follows that $f_{2m-1}$ is monotonically decreasing and takes its minimum $-m$ in all points $x\geq0$.

Now $$f_{2m}(x)=f_{2m-1}(x)+|x+2m|\ .$$ Here the term $|x+2m|$ is decreasing with slope $-1$ for $x\leq-2m$ and increasing with slope $1$ for $x\geq2m$. In the interval $[{-2m},0]$ this steady increase of $x\mapsto |x+2m|$ interferes with the cascade of ramps of $f_{2m-1}$, resulting in a horizontal zigzag of period $2$ and amplitude $1$. At $x=0$ we are at the lower end of the last ramp, and from then on $f_{2m}$ will definitely increase with slope $1$. The minimum of $f_{2m}$ can therefore be found by computing $f_{2m}(0)$, and is found to be $$f_{2m}(0)=f_{2m-1}(0)+|0+2m|=-m+2m=m\ .$$

Answer 2

We can consider the derivative of $f$ on $\mathbb R\setminus\{-n,-n+1,\ldots,0\}$ and use that $f$ is continuous.

First, consider that $n$ is odd.

In that case we get $$ f'(x)=\begin{cases} 0 & x<-n\\ -2 & x\in(-n,-n+1)\\ 0 & x\in(-n+1,-n+2)\\ -2 & x\in(-n+2,-n+3)\\ \vdots\\ 0 & x>0 \end{cases} $$ Therefore $f$ is piecewise constant or decreasing. Hence $f$ is minimal for $x\geq 0$ with the minimal value $$ f(0)=\sum_{i=0}^n(-1)^ii=-\frac{n+1}2. $$ Next, consider that $n$ is even.

In that case we get $$ f'(x)=\begin{cases} -1 & x<-n\\ 1 & x\in(-n,-n+1)\\ -1 & x\in(-n+1,-n+2)\\ 1 & x\in(-n+2,-n+3)\\ \vdots\\ 1 & x>0 \end{cases} $$ Since $f$ increases with same speed form $-n$ to $-n+1$ as it decreases form $-n+1$ to $-n+2$ you see that $f(-n)=f(-n+2)$ while $f(x)>f(-n)$ for $x\in(-n,-n+1)$. Therefore you can conclude $$ f(-n)=f(-n+2)=f(-n+4)=\ldots=f(0) $$ while $f(x)\geq f(-n)$ on $[-n,0]$. Since $f$ is increasing for $x>0$ you get that $f$ is minimal on $\{-n,-n+2,-n+4,\ldots,0\}$ with the minimal value $$ f(-n)=\sum_{i=0}^n(-1)^i(n-i)=\frac{n}2. $$