Collecting alternative proofs for the oddity of Catalan 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:

*

*an application 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$.


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


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


*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$?


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.
