Odd Catalan numbers

The easiest way to do this for me was to use the recurrence $C_{n+1} = C_0 C_n + C_1 C_{n-1} + \cdots + C_n C_0.$ The terms pair off if $n$ is odd, and they pair off except for the middle term $C_{n/2}C_{n/2}$ if $n$ is even. So we get that $C_{n+1}$ is odd if and only if $n$ is even and $C_{n/2}$ is odd.

After that, it is straightforward to prove by induction that $C_n$ is odd if and only if $n = 2^k-1$ for some positive integer $k$ . The base cases $n = 0,1$ are easy, and now suppose that the result holds up to $n$ . Then $C_{n+1}$ is odd if and only if $n$ is even and $C_{n/2}$ is odd, which happens if and only if $n/2 = 2^k-1$ for some $k$ by the inductive hypothesis, which happens if and only if $n+1 = 2^{k+1}-1$ . So the result holds for $n+1$ .

The numbers of this form between $1{,}000$ and $100{,}000$ are $2^k-1$ , $10 \le k \le 16$ . There are $\fbox{7}$ of these.

If someone has a way to do the problem directly from the definition using powers of $2$ inside binomial coefficients, I'd like to see it. (Edit: see Shourya's solution.)

Here is a solution different from the solution that Patrick gave:

We know that $C(n) = \frac{2n \choose n}{n+1}$ and we also know that ${2n \choose n }= \frac{2^n 1.3.5......(2n-1)}{n!}$ , so that $C(n) = \frac {2^n}{(n+1)!} 1.3.5..... .(2n-1)$ .

Thus $C(n)$ is odd if and only if the highest power of $2$ in $(n+1)!$ is $n$ .

The highest power of $2$ in $k!$ is equal to $k - b(k)$ , where $b(k)$ is the number of $1$ s in the binary expansion of $k$

Therefore, we want $n = n+1 -b(n+1)$ , or $b(n+1) = 1$ , which means $n+1$ is a power of $2$ , so $n = 2^{p} - 1$ , for some non-negative integer $p$ .

There are $7$ such numbers between $1000$ and $100000$ .

This paper describes why a Catalan number $C_n$ is odd if and only if $n$ is 1 less than some power of 2.

There are only 7 such numbers in the given interval.

Catalan numbers are only odd if and only if $n=2a^2-1$ , for $a \in \mathbb {Z^{+}}$

What I did was keep values of a to find first four n, which were 1, 7, 17, 31.

This help me create a sequence for finding such values of n as $a_{k+1}=a_{k}+4k+2$ where $a_{1}=1$

This can be simplified to get ( by applying sums on both sides from k=1, x):

$\large {a_{x+1}=a_{1}+2x(x+1)+2x=1+2x(x+2)}$

Now I started keeping values of x such that I get $a_{x+1}$ such that they satisfy the condition in the question and there were total 7 values.