# A binomial convolution of Catalan numbers vs "utterly odd numbers"

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.

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