Let $$a(n) = \sum_{0 \leq k \leq n} {n \choose k}{{n+k} \choose k},$$ and define $b(n) = \nu_3 \bigl(a(n)\bigr)$, where $\nu_3$ is the $3$-adic valuation. About twenty years ago or so, I discovered (empirically) the following conjectured expression for $b(n)$:

$$b(n) = \begin{cases} b\bigl(\lfloor n/3 \rfloor\bigr) + \bigl(\lfloor n/3 \rfloor \bmod 2\bigr), & \text{if $n \equiv 0,2$ (mod 3); } \\ b\bigl(\lfloor n/9 \rfloor\bigr) + 1, & \text{if $n \equiv 1$ (mod 3).} \end{cases} \tag{$*$}$$

But I have not been able to prove it.

For some background, the problem has some similarity to the following theorem, a weaker version of which was originally suggested by N. Strauss:

$$\text{If}\quad r(n) = \sum_{0 \leq i < n} {{2i} \choose i},\quad\text{then}\quad \nu_3 \bigl(r(n)\bigr) = \nu_3\left ( n^2 {{2n} \choose n}\right),$$ which I proved by a kind of tedious argument, with Jean-Paul Allouche. Later, another more elegant proof was given by Don Zagier. See here.

Can anybody prove $(*)$?

"$a(n)=P_n(3)$, where $P_n$ is $n$-th Legendre polynomial"sounds particularly relevant. $\endgroup$2more comments