Oddity of generalized Catalan numbers: Part I

Question

The famous (classical) Catalan numbers $C_{1,n}=\frac1{n+1}\binom{2n}n$ satisfy the following well-known arithmetic property: $$\text{$C_{1,n}$ is odd iff $n=2^j-1$ for some $j$}.\tag1$$ Consider the "second generation" of Catalan numbers $C_{2,n}$ which can be found on OEIS with A236339. One possible expression is given in the manner $$C_{2,n}=\frac1{n+1}\sum_{k=0}^{\lfloor n/3\rfloor}(-1)^k\binom{2n-2k}{n-2k}\binom{n-2k}k2^{n-3k}.$$ Working in the spirit of (1), I was curious to find any perpetual behavior. Here is my observation:

QUESTION 1. Is this true? If so, how does the proof go? $$\text{$C_{2,n}$ is odd iff $n=2^{2j}-1$ for some $j$}.$$

The $2$-adic valuation of $x\in\mathbb{N}$ is the highest power $2$ dividing $x$, denoted by $\nu(x)$. Let $s(x)$ stand for the sum of the binary digits of $x$. We may now state a stronger claim:

QUESTION 2. Is this true? $$\nu(C_{2,n})= \begin{cases} s(3m+1)-1 \qquad \, \text{if $n=3m$}, \\ s(3m-1)+2 \qquad \,\text{if $n=3m-1$}, \\ s(3m-1) \qquad \qquad \text{if $n=3m-2$}. \end{cases}$$

NOTE. Evidently, Question 2 implies Question 1. A related fact: $\nu(C_{1,n})=s(n+1)-1$.

Answer 1

I believe the answer to Question 1 is "yes". The easiest proof I know for the parity of the regular Catalan numbers uses the recurrence $$ C_n=C_0C_{n-1}+C_1C_{n-2}+\cdots+C_{n-1}C_0. $$ From this it follows quickly that for $C_n$ to be odd, $n$ must be odd (otherwise the terms pair off). In the case $n$ is odd, the same recurrence shows that the parity of $C_n$ is equal to the parity of $C_{(n-1)/2}$, and then it follows that $C_n$ is odd if and only if $n=2^m-1$.

In trying to adapt this proof to the numbers $C_{2,n}$, I found the following recurrence on the OEIS entry: $$ C_{2,n}=2\sum_{i+j=n} C_{2,i}C_{2,j}-\sum_{i+j+k+\ell=n} C_{2,i}C_{2,j}C_{2,k}C_{2,\ell}. $$ However, this recurrence applies to a shifted version of your sequence. In what follows I will not re-shift this recurrence, but instead prove that $C_{2,n}$ as defined above is odd if and only if $n=4^m$. For example, for $n=4$, the recurrence gives $$ C_{2,4} = 2\left(C_{2,1}C_{2,3}+C_{2,2}C_{2,2}+C_{2,3}C_{2,1}\right)-C_{2,1}^4 = 2(8+4+8)-1 = 39. $$

In a proof by induction, we can assume the only odd terms that will arise in the second sum are when $i$, $j$, $k$, and $\ell$ are powers of $4$. Moreover, you can pair off the terms where $i$, $j$, $k$, and $\ell$ are not all the same power of $4$. This leaves the only possible odd contribution to the sum as when $i$, $j$, $k$, and $\ell$ are all the same power of $4$, in which case $n=4^m$, as desired.

Answer 2

The answer to QUESTION 1 is Yes.

The following proof simplifies my suggestion in the comments.

According to the OEIS entry, the shifted generating function $$ g(x) = \sum_{n=0}^\infty C_{2,n} x^{n+1} = x + 2x^2 + 8x^3 + 39x^4 + \cdots $$ satisfies $g^4 - 2g^2 + g = x$. Reducing $\bmod 2$ gives $g^4 + g = x.$ Therefore, modulo 2 we have $$\begin{eqnarray} g &=& x + g^4 = x + (x+g^4)^4 \cr &=& x + x^4 + g^{16} = x + x^4 + (x+g^4)^{16} \cr &=& x + x^4 + x^{16} + (x+g^4)^{64} = \cdots, \end{eqnarray}$$ whence $$ g = x + x^4 + x^{16} + x^{64} + \cdots = \sum_{j=0}^\infty x^{2^{2j}}. $$ Therefore $C_{2,n}$ is odd if and only if $n+1 = 2^{2j}$ for some $j=0,1,2,3,\ldots$, QED

Remark. A similar proof can be given for the characterization of odd Catalan numbers, starting from the equation $c-c^2=x$ satisfied by the shifted generating function $c = \sum_{n=0}^\infty C_{1,n} x^{n+1}$. The coefficients of the solution $$x - x^4 + 4 x^7 - 22 x^{10} + 140 x^{13} - 969 t^{16} + - \cdots$$ of $g^4+g = x$ can also be given in closed form $-$ the $x^{3m+1}$ coefficient is $$\frac{(-1)^m}{3m+1} {4m\choose m}$$ found at OEIS A002293; see also the link here $-$ but getting the parity from that formula is not as easy as using $g^4+g=x$ directly.