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

• Really? It's not obvious? I am asking for a proof (or counterexample, if it's false). – Jeffrey Shallit May 5 '17 at 12:20
• It's worth to mention that the $a(n)$ form oeis.org/A001850 with tons of useful info and references. E.g., "$a(n)=P_n(3)$, where $P_n$ is $n$-th Legendre polynomial" sounds particularly relevant. – Max Alekseyev May 5 '17 at 13:39
• Out of curiosity, is there anything special about $3?$ Do you have results for any other prime (even or otherwise)? – Igor Rivin May 5 '17 at 15:06
• I have no results for anything other than 3. Maybe that is because of Alekseyev's observation? I don't know. – Jeffrey Shallit May 5 '17 at 15:13
• Perhaps the right generalization is that the sequence $f(n) = \nu_p(P_n (p))$, for $P_n$ the $n$'th Legendre polynomial, and $p$ is a prime $\geq 3$, is a $p$-regular sequence (in the sense of my paper with Allouche). I just tried it for $p = 5$ and it seems to satisfy relations like $f(5n+2) = f(5n)$, etc. – Jeffrey Shallit May 5 '17 at 15:30

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.

• Right! And then the generalization to odd $p$ (mentioned below) is $\nu_p (f(2n)) = \nu_p ({{2n} \choose n})$ and $\nu_p (f(2n+1)) = \nu_p(p(2n+1){{2n} \choose n})$. Very nice. Thanks so much. – Jeffrey Shallit May 6 '17 at 8:36
• And for $p = 2$ it is $\nu_2(L_n (2)) = (n \bmod 2)-\nu_2 (n!)$. – Jeffrey Shallit May 6 '17 at 9:31
• @Amdeberhan: Could you please mention the details of your proof? – Johann Cigler May 6 '17 at 12:45
• @Amdeberhan: Thank you for the details. But I still have difficulties if $n=6m+3$. – Johann Cigler May 7 '17 at 8:10

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