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

  • 3
    $\begingroup$ Really? It's not obvious? I am asking for a proof (or counterexample, if it's false). $\endgroup$ May 5, 2017 at 12:20
  • 3
    $\begingroup$ 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. $\endgroup$ May 5, 2017 at 13:39
  • 1
    $\begingroup$ Out of curiosity, is there anything special about $3?$ Do you have results for any other prime (even or otherwise)? $\endgroup$
    – Igor Rivin
    May 5, 2017 at 15:06
  • 1
    $\begingroup$ I have no results for anything other than 3. Maybe that is because of Alekseyev's observation? I don't know. $\endgroup$ May 5, 2017 at 15:13
  • 2
    $\begingroup$ 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. $\endgroup$ May 5, 2017 at 15:30

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$ May 6, 2017 at 8:36
  • $\begingroup$ And for $p = 2$ it is $\nu_2(L_n (2)) = (n \bmod 2)-\nu_2 (n!)$. $\endgroup$ May 6, 2017 at 9:31
  • $\begingroup$ @Amdeberhan: Could you please mention the details of your proof? $\endgroup$ May 6, 2017 at 12:45
  • $\begingroup$ @Amdeberhan: Thank you for the details. But I still have difficulties if $n=6m+3$. $\endgroup$ May 7, 2017 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)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.