Collecting alternative proofs for the oddity of Catalan

Question

Consider the ubiquitous Catalan numbers $C_n=\frac1{n+1}\binom{2n}n$. In this post, I am looking for your help in my attempt to collect alternative proofs of the following fact: $C_n$ is odd if and only if $n=2^r-1$.

Proofs that I know:

1. an application (the case $p=2$) of Legendre's (Kummer) formula $\nu_2(C_n)=s(n+1)-1$, where $s(n)$ is the sum of the binary digits of $n$.

2. See E. Deutsch and B. Sagan, Congruences for Catalan and Motzkin numbers and related sequences.

3. See A. Postnikov and B. Sagan, What power of two divides a weighted Catalan number?

4. See O. Egecioglu, The parity of the Catalan number via lattice paths.

QUESTION. Do you know of or can provide a new proof that $C_n$ is odd if and only if $n=2^r-1$?

Answer 1

Taking the fact that Catalan numbers $C_n$ measure the number of binary trees on $n$ nodes, we can find an involution on the set of these trees: choose the lexicographically first node in the tree that's unbalanced (i.e., where the number of nodes in the left subtree is different from the number in the right subtree). Then partner this tree with the one where we swap the left and right subtrees. This involution is fixed-point-free except in the case where no node in our tree is unbalanced — that is, when we have the complete binary tree of $n=2^t-1$ nodes, where we have to pair this tree to itself.

Answer 2

Apparently not mentioned yet, though surely not new: use the quadratic equation satisfied by the generating function. Since we look for $n+1$ to be a power of $2$, we shift the index by $1$ and consider $$ F = \sum_{n=0}^\infty C_n x^{n+1} = x + x^2 + 2 x^3 + 5 x^4 + 14 x^5 + 42 x^6 + 132 x^7 + 429 x^8 + \cdots. $$ Then $F = x + F^2$. Instead of solving this quadratic equation, apply it recursively ${} \bmod 2$. Recall that for each $r=1,2,3,\ldots$ we have the congruence $(a+b)^{2^r} \equiv a^{2^r} + b^{2^r} \bmod 2$ (proof: induction, the case $r=1$ being $(a+b)^2 = a^2 + 2ab + b^2 \equiv a^2+b^2$). We obtain: $$ \begin{array}{rl} F \; = \!\! & x + F^2 \cr = \!\! & x + (x+F^2)^2 \equiv x + x^2 + F^4 \cr = \!\! & x + x^2 + (x+F^2)^4 \equiv x + x^2 + x^4 + F^8 \cr = \!\! & x + x^2 + x^4 + (x+F^2)^8 \equiv x + x^2 + x^4 + x^8 + F^{16} \cr = \!\! & \cdots \cr \equiv \!\! & x + x^2 + x^4 + x^8 + x^{16} + x^{32} + x^{64} + \cdots \cr \end{array} $$ so indeed $C_n$ is odd if and only if $n+1$ is a power of $2$, QED.

Answer 3

• A proof by Koshy and Salmassi starting from Segner's recurrence formula for the Catalan numbers.
• A proof by Ji and Wilf using the method of recursive palindromes.

Answer 4

Here is one I've thought of a while ago for my combinatorics classes, but never ended up using.

Let $C_{0},C_{1},C_{2},\ldots$ be the Catalan numbers. Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$.

Theorem 1. For each $n\in\mathbb{N}$, we have \begin{align*} C_{n+1}=\sum\limits_{k=0}^{\left\lfloor n/2\right\rfloor }2^{n-2k}\dbinom{n}{2k} C_{k}. \end{align*}

This is Theorem 6.1 in Elena Barcucci and M. Cecilia Verri, Some more properties of Catalan numbers, Discrete Mathematics 102, Issue 3, 22 May 1992, pp. 229--237. They ascribe the theorem to Touchard and give a combinatorial proof. Here is a simple bijective proof that is nowadays folklore:

Proof of Theorem 1 (sketched). Consider the set $\mathbb{Z}\times\mathbb{N}$ of all pairs $\left( i,j\right) $ of integers with $j\geq0$. View this set as a subset of the Cartesian plane $\mathbb{R}^{2}$. Consider paths on the set $\mathbb{Z}\times\mathbb{N}$ that consist of the following four kinds of steps:

• A U-step (short for up-step) is a step of the form $\left( i,j\right) \rightarrow\left( i+1,j+1\right) $.

• A D-step (short for down-step) is a step of the form $\left( i,j\right) \rightarrow\left( i+1,j-1\right) $.

• A G-step (short for green horizontal step) is a step of the form $\left( i,j\right) \rightarrow\left( i+1,j\right) $.

• An R-step (short for red horizontal step) is a step of the form $\left( i,j\right) \rightarrow\left( i+1,j\right) $.

Thus, G-steps and R-steps connect the same points, but we distinguish between them nevertheless. Paths using these steps (and starting and ending on the x-axis) are called bicolored Motzkin paths. Paths using only D-steps and U-steps (and starting and ending on the x-axis) are called Dyck paths. The number of Dyck paths from $\left( 0,0\right) $ to $\left( 2k,0\right) $ is known to be $C_{k}$.

Now, how many bicolored Motzkin paths are there from $\left( 0,0\right) $ to $\left( n,0\right) $ ? On the one hand, this number is $\sum\limits_{k=0} ^{\left\lfloor n/2\right\rfloor }\dbinom{n}{2k}2^{n-2k}C_{k}$, because we first choose how many U-steps our path will have (let's say this number will be $k$), then choose the positions of the $k$ U-steps and the $k$ D-steps (we need the same amount because the path has to start and end at the same height), then choose the "colors" of the remaining steps (i.e., which of them will be G-steps and which will be R-steps), and finally choose the U-steps and the D-steps (this is tantamount to choosing a Dyck path from $\left( 0,0\right) $ to $\left( 2k,0\right) $, because removing all the G-steps and R-steps will result in such a Dyck path). Thus, we get $\sum\limits_{k=0} ^{\left\lfloor n/2\right\rfloor }\dbinom{n}{2k}2^{n-2k}C_{k}$.

On the other hand, there is a bijection from the set $\left\{ \text{bicolored Motzkin paths from }\left( 0,0\right) \text{ to }\left( n,0\right) \right\} $ to the set $\left\{ \text{Dyck paths from }\left( 0,0\right) \text{ to }\left( 2n+2,0\right) \right\} $. Indeed, this bijection sends a bicolored Motzkin path $\mathbf{m}$ to a Dyck path $\mathbf{d}$ that is constructed as follows:

• Start with an U-step.

• Look at each step of $\mathbb{m}$ in order (from left to right). For each step of $\mathbf{m}$, make the following two steps: If the step of $\mathbf{m}$ is an U-step, then make two U-steps. If the step of $\mathbf{m}$ is a D-step, then make two D-steps. If the step of $\mathbf{m}$ is a G-step, then make a U-step followed by a D-step. If the step of $\mathbf{m}$ is an R-step, then make a D-step followed by a U-step.

• Finish with a D-step.

It is easy to see that the resulting path $\mathbf{d}$ will really be a Dyck path from $\left( 0,0\right) $ to $\left( 2n+2,0\right) $. (Note that each pair of steps of $\mathbf{d}$ coming from a step of $\mathbf{m}$ starts at odd height, so the initial D-step cannot lead you below the x-axis.) It is furthermore not hard to see that this assignment of $\mathbf{d}$ to $\mathbf{m}$ is a bijection. (Indeed, any pair of two consecutive steps of a Dyck path is either UU or DD or UD or DU; moreover, if we focus on the pairs consisting of a $2i$-th step and the $\left( 2i+1\right) $-st step for all $i\in\left\{ 1,2,\ldots,k\right\} $, then the number of DD pairs cannot exceed the number of UU pairs.) Thus, we have found a bijection from $\left\{ \text{bicolored Motzkin paths from }\left( 0,0\right) \text{ to }\left( n,0\right) \right\} $ to $\left\{ \text{Dyck paths from }\left( 0,0\right) \text{ to }\left( 2n+2,0\right) \right\} $. Hence, the number of bicolored Motzkin paths from $\left( 0,0\right) $ to $\left( n,0\right) $ is the number of Dyck paths from $\left( 0,0\right) $ to $\left( 2n+2,0\right) $; but the latter number is $C_{n+1}$.

Thus, we have counted the former number in two ways. Comparing the results, we find \begin{align*} C_{n+1}=\sum\limits_{k=0}^{\left\lfloor n/2\right\rfloor }\dbinom{n}{2k}2^{n-2k} C_{k}=\sum\limits_{k=0}^{\left\lfloor n/2\right\rfloor }2^{n-2k}\dbinom{n}{2k}C_{k}. \end{align*} This proves Theorem 1. $\blacksquare$

Now, let us fix an $n\in\mathbb{N}$, and ask ourselves when $C_{n+1}$ is odd. Theorem 1 yields \begin{align*} C_{n+1}=\sum\limits_{k=0}^{\left\lfloor n/2\right\rfloor }2^{n-2k}\dbinom{n}{2k} C_{k}. \end{align*} The $2^{n-2k}$ factors ensure that all addends on the right hand side of this equality are even, except possibly the addend for $k=n/2$ (because here the $2^{n-2k}$ factor becomes $1$). This latter addend only exists when $n$ is even, and in that case equals $\underbrace{2^{n-2\left( n/2\right) }} _{=1}\underbrace{\dbinom{n}{2\left( n/2\right) }}_{=1}C_{n/2}=C_{n/2}$. Thus, we conclude that

• the number $C_{n+1}$ is even when $n$ is odd;

• we have $C_{n+1}\equiv C_{n/2} \mod 2$ when $n$ is even.

Using these two facts, we can now easily prove (by induction on $r$ and strong induction on $m$) that

• the number $C_{2^{r}-1}$ is odd for each nonnegative integer $r$;

• the number $C_{m}$ is even whenever $m\in\mathbb{N}\setminus\left\{ 2^{r}-1\ \mid\ r\in\mathbb{N}\right\} $.

(Indeed, if $m\in\mathbb{N}\setminus\left\{ 2^{r}-1\ \mid\ r\in \mathbb{N}\right\} $, then either $m-1$ is even, or else $\left( m-1\right) /2\in\mathbb{N}\setminus\left\{ 2^{r}-1\ \mid\ r\in\mathbb{N}\right\} $, in which case we can apply the congruence $C_{n+1}\equiv C_{n/2} \mod 2$ for $n=m-1$ and then conclude using the induction hypothesis.)

I suspect that higher congruences for Catalan numbers (modulo $2^k$) can also be established using Theorem 1.