Counting even and odd numbers in the columns of a triangular arrangement of the integers

158 Views Asked by At

I write the positive numbers starting at $1$ in a triangle:$$\mathbb{N}_\triangle = \begin{matrix} &&&&&21&\ldots \\ &&&&15&20&\ldots \\ &&&10&14&19&\ldots \\ &&6&9&13&18&\ldots \\ &3&5&8&12&17&\ldots \\ 1&2&4&7&11&16&\ldots \end{matrix}$$

I would like some help proving the following claim

I denote the count of even numbers in column $n$ of $\mathbb{N}_\triangle$ by $e(n)$. Then for $n>1$ $$e(n) = \Bigg\lfloor{n+2 \above 1.5pt 4}\Bigg\rfloor+\Bigg\lfloor{n+1 \above 1.5pt 4}\Bigg\rfloor$$ Note the $n^{th}-column$ of $\mathbb{N}_\triangle$ has $n$ integers so I can set $f(n)$ to count the number of odd integers in $\mathbb{N}_\triangle$ and $$f(n) = n-e(n)$$ It appears that $e(n)\in$ A004524

This is being driven by hunches and computer checks. $e(n)$ can be simplified but I think it is easier to remember it the way it is written.

1

There are 1 best solutions below

8
On BEST ANSWER

Note that each column forms an interval of integers, and so the numbers in the column alternate between being odd and even.

Hence if $n$ is even, so that there are an even number of integers in the $n$th column, exactly half of them will be even, so $e(2k) = k$ for every $k \in \mathbb{N}$.

If $n$ is odd, there will either be $\frac{n-1}{2}$ or $\frac{n+1}{2}$ even numbers, depending on whether the column starts with an odd or even number respectively. Notice that the difference between the initial numbers of the $2k-1$st and $2k+1$st columns is $4k-1$, since the $2k-1$st column has $2k-1$ numbers, and the $2k$th column in between has a further $2k$ numbers. As $4k-1$ is odd, that means that the initial numbers in the $2k-1$st and $2k+1$st odd columns have different parities.

Hence the first odd column starts with an odd number (namely $1$), the next odd column starts with an even number, the next odd column after that starts with an odd number again, and so on. This means we have the formula

$$\begin{array}{c|cccccccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & ... & 4k + 1 & 4k + 2 & 4k + 3 & 4k + 4 & ... \\ \hline e(n) & \frac{n-1}{2} & \frac{n}{2} & \frac{n+1}{2} & \frac{n}{2} & \frac{n-1}{2} & \frac{n}{2} & \frac{n+1}{2} & \frac{n}{2} & ... & 2k & 2k + 1 & 2k + 2 & 2k + 2 & ... \\ e(n) - \frac{n}{2} & - \frac12 & 0 & \frac12 & 0 & - \frac12 & 0 & \frac12 & 0 & ... & - \frac12 & 0 & \frac12 & 0 & ... \end{array}. $$

As you can see, $e(n) - \frac{n}{2}$ is periodic with period $4$, as explained by the dependence on the parity of $n$, and then the alternating behaviour in the odd case. Your formula captures this periodicity, and is correct. Other ways to express it, which I find delightfully ridiculous, include $$ e(n) = \frac12 \operatorname{Re} \left( n + i^{n+1} \right) = \frac12 \left( n - \sin \left(\frac12 n \pi\right)\right). $$