3-adic valuation of a sum involving binomial coefficients

Question

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 $(*)$?

Answer 1

The $3$-adic evaluation you seek is compactly given by $$\nu_3(a_{2n})=\nu_3\left(\binom{2n}n\right) \qquad \text{and} \qquad \nu_3(a_{2n+1})=\nu_3\left(3(2n+1)\binom{2n}n\right),$$ which can be proved inductively using the well-known recurrence $$na_n=3(2n-1)a_{n-1}-(n-1)a_{n-2}$$ according to the parity of $n$. To address Cigler's request, here is an illustration for the case even: $(2n)a_{2n}=3(4n-1)a_{2n-1}-(2n-1)a_{2n-2}$ and by induction assumption $$\nu_3(3(4n-1)a_{2n-1})=\nu_3\left(9(4n-1)(2n-1)\binom{2n-2}{n-1}\right) \qquad\text{and}\qquad \nu_3((2n-1)a_{2n-2})=\nu_3\left((2n-1)\binom{2n-2}{n-1}\right).$$ So, $\nu_3(3(4n-1)a_{2n-1})>\nu_3((2n-1)a_{2n-2})$ and $\nu_3((2n)a_{2n})=\nu_3((2n-1)\binom{2n-2}{n-1})$; or, \begin{align} \nu_3(a_{2n})&=\nu_3\left(\frac{(2n-1)}{2n}\binom{2n-2}{n-1}\right) =\nu_3\left(\frac14\binom{2n}n\right)=\nu_3\left(\binom{2n}n\right) \end{align} as desired.

Answer 2

Indeed, the observation by Max Alexseyev seems to provide the idea I need!

The conjecture I made above can be generalized as follows:

Let p > 2 be a prime, and let $L_n (x)$ be the Legendre polynomial. Define $f(n) = \nu_p (L_n (p))$ for $n \geq 0$. Then for $n \geq 0$ and $0 \leq a < p$ we have $f(pn+a) = \begin{cases} f(n) + (n \bmod 2), & \text{if $a$ even}; \\ f(n) + 1 - (n \bmod 2), & \text{if $a$ odd}. \end{cases}$

I will now try to prove this more general statement, which I suspect will actually be easier. It probably follows from Bonnet's recursion formula for the Legendre polynomials $(n+1)P_{n+1}(x)=(2n+1)xP_{n}(x)-nP_{n-1}(x)$.