Why does this nested absolute value function seem to behave the following way?

Question

Just out of curiosity, I defined a nested absolute value function called $altab(n)$ whose input is a natural number $n \geqslant 1$ and works as follows:

$altab(n) = \lvert 1-\lvert2+\lvert3-\lvert\ldots\pm\lvert n\rvert\ldots\rvert\rvert\rvert\rvert$

More clearly, it's defined as:

$altab(n) = \lvert 1+(-1)^1\lvert2+(-1)^2\lvert3+(-1)^3\lvert\ldots+(-1)^{(n-1)}\lvert n\rvert\ldots\rvert\rvert\rvert\rvert$

It's basically a series of nested absolute values where the sign in front changes in an alternating fashion. To evaluate it, you work from the inside out. For example, to evaluate $altab(3)$, the procedure is as follows:

$\lvert 1 - \lvert 2 + \lvert 3 \rvert\rvert\rvert \hspace{5px}=\hspace{5px} \lvert 1 - \lvert 5 \rvert\rvert \hspace{5px}=\hspace{5px} \lvert -4\rvert \hspace{5px}=\hspace{5px} 4$

I wrote a program to automatically evaluate $altab(n)$ for the first 20 values of n and the following appears to be true:

$$ altab(n) = \left\{ \begin{array}{ll} \frac{n}{2} & \quad when \hspace{5px} n \hspace{5px} is \hspace{5px} even. \\ \frac{3n-1}{2} & \quad when \hspace{5px} n \hspace{5px} is \hspace{5px} odd. \end{array} \right. $$

Analyzing nested absolute value functions is hard, so I want to know two things - whether this is correct and if so, why $altab(n)$ behaves this way.

Answer 1

First, note in your statement

$altab(n) = \lvert 1+(-1)^1\lvert2+(-1)^2\lvert3+(-1)^3\lvert\ldots+(-1)^n\lvert n\rvert\ldots\rvert\rvert\rvert\rvert$

the power of $1$ is the same as the term on the left, e.g., $1 + (-1)^1$, $2 + (-1)^2$, etc. This means the power of $-1$ which multiplies $n$ must be the same as the term to its left, i.e., $n-1$, and not $n$ as you've shown. I spent a few minutes trying to solve your problem using your result but got different results and then saw the mistake.

Next, consider a function defined for $1 \le k \le n$ where

$$f(k) = \lvert k+(-1)^{k}\lvert k + 1 +(-1)^{k+1}\lvert k + 2 +(-1)^{k+2}\lvert\ldots+(-1)^{n-1}\lvert n\rvert\ldots\rvert\rvert\rvert\rvert \tag{1}\label{eq1A}$$

In this case, $f(1)$ is your $\operatorname{altab}(n)$. Also, you can define $f(k)$ recursively in terms of $f(k+1)$ as

$$f(k) = \lvert k + 1^{k+1}f(k + 1)\rvert \tag{2}\label{eq2A}$$

This shows how you can calculate $f(k)$ for any $k \le n$ by calculating $f(n)$ and then calculating $f$ for each smaller value, i.e., $f(n-1)$, $\ldots$, $f(k+1)$ and $f(k)$.

As you've noticed, it's helpful to consider the cases of $n$ being even and odd separately. Since $f(n) = n$ in both cases, I won't consider it separately in those other cases. Instead, I will consider the values of $k$ going from $n-1$ to $n-4$.

---

Case $1$: $n$ is even

$$f(n-1) = \lvert n - 1 - n \rvert = 1 \tag{3}\label{eq3A}$$ $$f(n-2) = \lvert n - 2 + 1 \rvert = n - 1 \tag{4}\label{eq4A}$$ $$f(n-3) = \lvert n - 3 - (n - 1) \rvert = 2 \tag{5}\label{eq5A}$$ $$f(n-4) = \lvert n - 4 + 2 \rvert = n - 2 \tag{6}\label{eq6A}$$

As you can see, $f((n - 1) - 2) = 1 + 1$ and $f((n-2) - 2) = (n - 1) - 1$. In particular, $f(n-k) - f(n-k-2)$ is $(-1)^{k}$. You can use induction to prove for odd $k$ that

$$f(n-k) = \frac{k+1}{2} \tag{7}\label{eq7A}$$

First note have proven the base case of $k = 1$ already in \eqref{eq3A}. Assume it's true for all $k \le m$ for some odd $m \ge 1$. For $k = m$, you then have $f(n - m) = \frac{m + 1}{2}$ and, since $n - m - 1$ is even,

$$\begin{equation}\begin{aligned} f(n-m-1) & = \left\lvert n - m - 1 + \frac{m+1}{2}\right\rvert \\ & = \left\lvert n + \frac{2(-m - 1) + (m + 1)}{2}\right\rvert \\ & = \left\lvert n - \frac{m + 1}{2}\right\rvert \\ & = n - \frac{m + 1}{2} \end{aligned}\end{equation}\tag{8}\label{eq8A}$$

Since $m \lt n$, then $\frac{m+1}{2} \lt \frac{n+1}{2} \lt n$, so when taking absolute values you get the last line above. Next, using \eqref{eq8A}, you have for $k = m + 2$ that

$$\begin{equation}\begin{aligned} f(n-m-2) & = \left\lvert n - m - 2 - \left(n - \frac{m + 1}{2}\right)\right\rvert \\ & = \left\lvert n - m - 2 - n + \frac{m + 1}{2}\right\rvert \\ & = \left\lvert \frac{2(-m - 2) + (m + 1)}{2}\right\rvert \\ & = \left\lvert \frac{-m - 3}{2}\right\rvert \\ & = \frac{m + 3}{2} \end{aligned}\end{equation}\tag{9}\label{eq9A}$$

Note this matches \eqref{eq7A} since replacing $k$ with $m + 2$ gives

$$f(n - (m + 2)) = \frac{(m + 2) + 1}{2} = \frac{m + 3}{2} \tag{10}\label{eq10A}$$

This means \eqref{eq7A} has been proven by induction, so you then have

$$f(n - (n - 1)) = \frac{(n-1) + 1}{2} = \frac{n}{2} \tag{11}\label{eq11A}$$

with this matching your result for $\operatorname{alttab}(n)$ for even $n$.

---

Case $2$: $n$ is odd

$$f(n-1) = \lvert n - 1 + n \rvert = 2n - 1 \tag{12}\label{eq12A}$$ $$f(n-2) = \lvert n - 2 - (2n - 1) \rvert = \lvert -n - 1 \rvert = n + 1 \tag{13}\label{eq13A}$$ $$f(n-3) = \lvert n - 3 + (n + 1) \rvert = 2n - 2 \tag{14}\label{eq14A}$$ $$f(n-4) = \lvert n - 4 - (2n - 2) \rvert = \lvert -n - 2 \rvert = n + 2 \tag{15}\label{eq15A}$$

As you can see with $f(n-k)$, increasing $k$ by $2$ decreases the result by $1$ if $k$ is odd, so you get $f(n-k) = 2n - \frac{k+1}{2}$, while it increases the result by $1$ if $k$ is even, so you get $f(n-k) = n + \frac{k}{2}$.

In this case you want to use the situation for even $k$ since $1 = n - (n-1)$ with $n-1$ being even for odd $n$. As such, you want to prove for even $k$ that

$$f(n-k) = n + \frac{k}{2} \tag{16}\label{eq16A}$$

I'll leave it to you prove this, such as by induction similar to what I did in case #$1$. This then gives

$$\begin{equation}\begin{aligned} f(1) & = f(n - (n-1)) \\ & = n + \frac{n-1}{2} \\ & = \frac{2n + n - 1}{2} \\ & = \frac{3n - 1}{2} \end{aligned}\end{equation}\tag{17}\label{eq17A}$$

with this matching your result for $\operatorname{alttab}(n)$ for odd $n$.

Answer 2

The assertion follows from the identity $$(-1)^{n-2}|(n-1)+(-1)^{n-1}|n+x||=x+1$$ which holds for every even $n>0\in\Bbb N$ and every $x\geq 0$.

---

More precisely, for every $n\in\Bbb N$ let \begin{align} &\sigma_n(x)=(-1)^{n-1}|n+x|& &\varphi_n=\sigma_1\circ\cdots\circ\sigma_n \end{align} then the claim is $$\varphi_n(0)=\operatorname{altab}(n)= \begin{cases} \frac n2&2|n\\ \frac{3n-1}2&2\nmid n \end{cases}$$ or, equivalently, $\varphi_{2n}(0)=n$ and $\varphi_{2n+1}(0)=3n+1$.

A direct computation shows that for every $n>0$ and $x\geq 0$ we have $$(\sigma_{2n-1}\circ\sigma_{2n})(x)=x+1$$ Since $\varphi_{2n}=\varphi_{2(n-1)}\circ\sigma_{2n-1}\circ\sigma_{2n}$, by induction on $n$ we get $\varphi_{2n}(x)=x+n$. On the other hand $$\varphi_{2n+1}(x)=(\varphi_{2n}\circ\sigma_{2n+1})(x)=\varphi_{2n}(2n+1+x)=3n+1+x$$ which proves the assertion.