# Oddity of generalized Catalan numbers: Part I

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$$.

• I think this should be easy by using Lucas' congruence. – Zhi-Wei Sun Mar 6 at 22:23
• Tempting, yes.. Details? – T. Amdeberhan Mar 6 at 23:10
• According to the OEIS entry, the generating function $g(x) = \sum_{n=1}^\infty C_{2,n-1} x^n$ satisfies $g^4 - 2g^2 + g = x$. Reducing $\bmod 2$ gives $g^4 + g = x$, another Catalan variation with series $x - x^4 + 4 x^7 - 22 x^{10} + 140 x^{13} - 969 t^{16} + - \cdots$ whose coefficients are known in closed form as ${4m\choose m}/(3m+1)$ [OEIS A002293, see also math.harvard.edu/~elkies/Misc/catalan.pdf]. This should make it routine to deduce which $C_{2,n}$ are odd. – Noam D. Elkies Mar 7 at 4:19
• The denominator is $3m+1$, not $m+1$. Indeed I changed from $n$ to $m$ because the indices are different: note the exponents $1,4,7,10,13,\ldots$ in the solution of $g^4+g=x$. For example, the odd $969$ arises for $m=5$ as ${20 \choose 5} / 16$. – Noam D. Elkies Mar 7 at 4:40
• Again, note the indexing in A002293. The odd values of ${4m\choose m}/(3m+1)$ occur at $m = 1, 5, 21, 85, \ldots$ corresponding to $C_{2,n}$ with $n = 3m = 3, 15, 63, 255, \ldots = 2^{2j}-1$. – Noam D. Elkies Mar 7 at 4:58

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.

• Nice approach, Vince. Thanks. Good to see you here! – T. Amdeberhan Mar 7 at 15:27

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.

• Thank you for this solution. – T. Amdeberhan Mar 7 at 21:33