# Tweaking the Catalan recurrence and $2$-adic valuations

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

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

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