The best notation for this identity involving pentagonal numbers $\omega(n)$ and the $3x+1$ map

Question

Let the $3x+1$ map

$$ f(n) = \begin{cases} 3n+1 & \text {if $n$ is odd} \\ \frac{n}{2} & \text {if $n$ is even} \end{cases} .$$

Now we read the Wikipedia's page for the Collatz problem, also known by several names.

Example. Since $f(1)=4$, $f(4)=2$ and $f(2)=1$, the integer $n=1$ is not a counterexample for the Collatz conjecture (in other words, is the easier example of an integer satisfying the conjecture).

In the other hand we know that the pentagonal numbers of the form $$\omega(n)=\frac{3n^2-n}{2}$$ (related with partitions) are defined as $$\omega(n)=\sum_{k=0}^{n-1}(3k+1).$$

Thus if $n-1$ is odd (this is the first case of two, the second case with $n-1$ even) one can deduce easily combining previous and the definition of the $3x+1$ map that $$\omega(n)=1+\sum_{k\in \left\{ 1,3,5,\ldots,n-1 \right\}}f(k)+6\left(\sum_{k\in \left\{ 2,4,6,\ldots,n-2 \right\}}f(k)\right)+\sum_{k\in \left\{ 2,4,6,\ldots,n-2 \right\}}1.$$

Question. I am stuck to get the best concise formula ( I say the previous last identity, if it is neccesary by cases to get also the case $n-1$ is even) with the right notation. I don't know if I should be to use counting funtions to count the number of odd positive integers $\leq n-1$ (respectively even positive integers) or ceil and floor functions. Can you help to get this simple proposition, both cases, with a good notation Thanks in advance.

Answer 1

At first some notes: We usually regard the closed formula \begin{align*} \omega(n)=\frac{3n^2+n}{2}\qquad\qquad\qquad\qquad\qquad n\geq 1\tag{1} \end{align*} as simpler than the summation formula \begin{align*} \omega(n)=\sum_{k=0}^{n-1}(3k+1)\qquad\qquad\qquad\qquad\quad n\geq 1\tag{2} \end{align*} So, if we want to represent $\omega(n)$ by the function \begin{align*} f(n)=\begin{cases} 3n+1\qquad & n \text{ odd}\\ \frac{n}{2}\qquad & n \text{ even} \end{cases}\qquad\qquad n\geq 1 \end{align*} we would rather try to avoid sums and start from (1). Another aspect is there is no best notation. An appropriate notation is usually application dependent and may vary according to different needs. But we can try to do some simplifications which are typically useful.

First variant: Expressing $f(n)$ by (2)

We start similar as OP did.

We obtain \begin{align*} \omega(n)&=\sum_{k=0}^{n-1}(3k+1)\\ &=\sum_{{k=0}\atop{k \text{ odd}}}^{n-1}(3k+1)+\sum_{{k=0}\atop{k \text{ even}}}^{n-1}(6\cdot\frac{k}{2}+1)\tag{3}\\ &=\sum_{{k=0}\atop{k \text{ odd}}}^{n-1}f(k)+\sum_{{k=0}\atop{k \text{ even}}}^{n-1}(6f(k)+1)\tag{4}\\ &=\sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}f(2k-1) +\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}(6f(2k)+1)\tag{5}\\ &=\sum_{k=0}^{\left\lfloor\frac{n}{2}\right\rfloor-1}f(2k+1) +6\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}f(2k)+\left\lfloor\frac{n-1}{2}\right\rfloor+1\tag{6}\\ &=\sum_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor}\left(f(2k+1)+6f(2k)\right)\\ &\qquad\qquad+\left\lfloor\frac{n-1}{2}\right\rfloor+1-f(2\left\lfloor\frac{n-1}{2}\right\rfloor+1)\cdot\frac{1-(-1)^n}{2}\tag{7}\\ \end{align*}

Comment:

• In (3) we split the sum in odd and event parts of the index $k$

• In (4) we use the function $f(n)$

• In (5) we use the floor function to set the upper limit of $k$. For the odd part we use the substitution $k \rightarrow 2k-1$ and for the even part we use the substitution $k \rightarrow 2k$.

• In (6) we shift the index of the left sum by one to start with $k=0$ and we extract the constant $1$ from the right sum and get $\left\lfloor\frac{n-1}{2}\right\rfloor+1$.

• In (7) we can further reduce the number of summation symbols (if we like) by observing that \begin{align*} \left\lfloor\frac{n-1}{2}\right\rfloor=\begin{cases} \left\lfloor\frac{n}{2}\right\rfloor &\qquad n \text{ odd}\\ \left\lfloor\frac{n}{2}\right\rfloor-1 &\qquad n \text{ even}\\ \end{cases} \end{align*} So, we can use one summation symbol and a common upper limit $\left\lfloor\frac{n-1}{2}\right\rfloor$. Since in the odd case we have one more than in the even case we have to subtract the last element. We do this by subtracting $f(2\left\lfloor\frac{n-1}{2}\right\rfloor+1)$ and multiplying it with \begin{align*} \frac{1-(-1)^n}{2}=\begin{cases} 1\qquad& n\text{ odd}\\ 0\qquad& n\text{ even} \end{cases} \end{align*}

Second variant: Expressing $f(n)$ by (1)

Since it is usually more convenient to avoid summation symbols if possible at all we start now from (1). Here is one from many different possibilities.

We obtain \begin{align*} \omega(n)&=\frac{3n^2-n}{2}\\ &=(3n+1)\frac{n}{2}-n\\ &=\begin{cases} f(n)\frac{n}{2}-n\qquad & n\text{ odd}\\ (3n+1)f(n)-2f(n)\qquad& n\text{ even} \end{cases}\tag{8}\\ &=\begin{cases} f(n)\frac{n}{2}-n\qquad\qquad\qquad & n\text{ odd}\\ (3n-1)f(n)\qquad\qquad\qquad& n\text{ even} \end{cases}\\ &=(3n-1)f(n)\cdot\frac{1+(-1)^n}{2}+\frac{n}{2}\left(f(n)-2\right)\frac{1-(-1)^n}{2}\tag{9}\\ &=\frac{1}{4}\left(7n-2+(5n-2)(-1)^n\right)f(n)-\frac{n}{2}\left(1-(-1)^n\right)\tag{10} \end{align*}

Comment:

• In (8) we use $f(n)$ according to odd and even $n$

• In (9) we put odd and even cases together using a technique as we did in (7)

• In (10) we do some final rearrangement