9
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think this should be easy by using Lucas' congruence. $\endgroup$ – Zhi-Wei Sun Mar 6 at 22:23
  • $\begingroup$ Tempting, yes.. Details? $\endgroup$ – T. Amdeberhan Mar 6 at 23:10
  • 2
    $\begingroup$ 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. $\endgroup$ – Noam D. Elkies Mar 7 at 4:19
  • $\begingroup$ 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$. $\endgroup$ – Noam D. Elkies Mar 7 at 4:40
  • $\begingroup$ 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$. $\endgroup$ – Noam D. Elkies Mar 7 at 4:58
12
$\begingroup$

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.

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

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.

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

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.