16
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Really? It's not obvious? I am asking for a proof (or counterexample, if it's false). $\endgroup$ – Jeffrey Shallit May 5 '17 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$ – Max Alekseyev May 5 '17 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 '17 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$ – Jeffrey Shallit May 5 '17 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$ – Jeffrey Shallit May 5 '17 at 15:30
11
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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