1
$\begingroup$

Define the sequence $b_1=1$ and $$b_n=\sum_{k=1}^{n-1}\binom{n-1}k\binom{n-1}{k-1}b_kb_{n-k}.$$

By now, there is enough in the literature that $C_n$ is odd iff $n=2^k-1$ for some $k$ where $C_n$ are the Catalan numbers: $C_0=1$ and $$C_{n+1}=\sum_{k=0}^nC_kC_{n-k}.$$

In the same spirit, I ask:

QUESTION. is it true that $b_n$ is odd iff $n=2^k$ for some $k$?

$\endgroup$
2
1
$\begingroup$

The conjecture follows from the fact that, for any prime $p$ and any integers $m,r$, it holds that [1] $$b_{mp^r}=b_m\mod p,$$ $$b_m=0\mod p\;\;\text{for}\;\;p<m<2p.$$ Take $p=2$ and use $b_1=1$ to obtain the result that $b_m=1\mod 2$ if and only if $m$ is a power of 2.

[1] A sequence of integers related to the Bessel functions: equations 9 and 10. The sequence in this paper is the same sequence as in the OP, see OEIS:A002190.

$\endgroup$
1
$\begingroup$

You can argue combinatorially just like in the case of Catalan numbers, as done in Congruences for Catalan and Motzkin numbers and related sequences, by Deutsch and Sagan.

The recurrence relation allows you to interpret $b_n$ as a weighted sum over binary trees with $n$ leaves. Since the group of automorphisms of the full binary tree acts on these objects, the only way $b_n$ can be odd is if the action fixes one of the trees. It is easy to see that the only such fixed tree is the full binary tree itself, therefore we only need to check the parity of $b_n$ for $n=2^k$. The recurrence tells you that the contribution that comes from the full binary tree of depth $k$ has the same parity as the contribution from the full binary tree of depth $k-1$. This implies your conjecture.

$\endgroup$

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.