3-adic valuation of a sum involving binomial coefficients 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: 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)$.
A: 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.
