An integer is called utterly odd if the terminal string of $1$’s in its binary representation has odd length. A number $2^{k+1}m+(2^k-1)$ where $m\geq0$ (every non-negative integer has this form) is utterly odd iff $k$ is odd. The first few utterly odd positive numbers $1,5,7,9,13,17,21,23,25,29,31,\dots$ are listed on OEIS.

QUESTION. Let $C_n=\frac1{n+1}\binom{2n}n$ be the Catalan numbers. Is this true? $$a_n:=\sum_{k=0}^n\binom{n}kC_k\equiv0\mod 2 \qquad \text{iff} \qquad \text{$n$ is an utterly odd number}.$$

This is supported experimentally.


1 Answer 1


$C_k$ is odd iff $k=2^s-1$, $s=0,1,\ldots$. $\binom{n}{2^s-1}$ is odd iff $s$ terminal binary digits of $n$ are 1's (by Kummer's theorem). Thus the result.


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.