Among many descriptions of the Catalan numbers $C_n$, let's use the recursive format $C_0=1$ and $$C_{n+1}=\sum_{i=0}^nC_iC_{n-i}.$$ Then, the $2$-adic valuation of $C_n$ is computed by $\nu_2(C_n)=s(n+1)-1$ where $s(x)$ denotes the number of $1$’s in the $2$-ary (binary) expansion of $x$. In particular, $C_n$ is odd or $C_n\equiv 1\mod 2$ iff $n=2^k-1$ for some integer $k$.

Fix $t\in\mathbb{N}$. Now, let's tweak this a little so as to generate the sequence $u_{0,t}=1$ and $$u_{n+1,t}=\sum_{i=0}^nu_{i,t}^tu_{n-i,t}^t.$$ Note. $u_{n,1}=C_n$.

QUESTION. Is the following true? If $t$ is odd then $\nu_2(u_{n,t})=s(n+1)-1$. If $t$ is even then $\nu_2(u_{n,t})=(C_n\mod2)+2s(n+1)-3$. Equivalently, if $t$ is even then $$\nu_2(u_{n,t})=\begin{cases} 2s(n+1)-2 \qquad\text{if $n=2^k-1$} \\ 2s(n+1)-3 \qquad\text{otherwise}. \end{cases}$$

Remark. Unsurprisingly, for each $t$ we have $u_{n,t}$ is odd iff $n=2^k-1$ for some $k\in\mathbb{Z}$.

  • $\begingroup$ how does definition of $u_{n,t}$ depend on $t$? $\endgroup$ Jan 3, 2021 at 19:03
  • $\begingroup$ @FedorPetrov: thank you, typo fixed. $\endgroup$ Jan 3, 2021 at 19:05

1 Answer 1


This is not true. In fact, we can show that $\nu_2(u_{6,t}) = t+1$.

Indeed, computing first terms modulo $2^{t+2}$ for $t\geq 2$, we have \begin{split} u_{0,t} &= 1,\\ u_{1,t} &= 1,\\ u_{2,t} &= 2,\\ u_{3,t} &= 1 + 2^{t+1},\\ u_{4,t} &= 2+2^{t+1}+O(2^{t+2}),\\ u_{5,t} &= 2 + 2^{t+1} + O(2^{t+2}),\\ u_{6,t} &= 2^{t+1} + O(2^{t+2}). \end{split}


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.