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

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

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

sumof the binary digits, rather than the number of 1's, since (i) it explains the notation "s" and (ii) the perspective of a sum of digits is how Legendre's formula for $v_2(n!)$ extends to $v_p(n!)$ for odd primes $p$. $\endgroup$