# Modular congruences related to sums of Catalan numbers

I am curious if somebody can be helpful concerning the following experimental observation:

There exist two rational sequences $\alpha_0,\alpha_1,\dots$ and $\beta_0,\beta_1,\dots$, both with values in $\mathbb Z[1/3]$ such that $$\sum_{k=0}^{p-1}{2k\choose k}\frac{k^j}{k+1}\equiv \alpha_j+p\beta_j\pmod{p^2}$$ for every prime number $p\equiv 1\pmod 6$ and $$\sum_{k=0}^{p-1}{2k\choose k}\frac{k^j}{k+1}\equiv -(-1)^j-\alpha_j+p\beta_j\pmod{p^2}$$ for every prime number $p\equiv 5\pmod 6$.

(More precisely, the sequences $3^n\alpha_n$ and $3^n\beta_n$ are seemingly integral.)

The sequence $\alpha_0,\alpha_1,\dots$ starts as $$1, 0, -2/3, 4/3, -22/9, 140/27, -14, 1316/27, -17078/81, 87860/81, -1562042/243, 31323292/729, \dots$$ and the first terms $\beta_0,\beta_1,\dots$ are $$0,0,2/3,-2,14/3,-34/3,98/3,-350/3,1526/3,-2622,46634/3,-311734/3,2316158/3, -18920018/3,\dots$$

Let me end by remarking that one has as a special case a similar result when replacing Catalan numbers by central binomial coefficients.

Update: The existence of the sequence $\alpha_n$ is explained by the Zhi-Wei Sun paper, see the answer by dke below.

Experimentally, the quotient sequence $\frac{\beta_n}{\alpha_n}$ (defined for $n\geq 2$) seems to converge very quickly towards $-\frac{4\sqrt{3}\pi}{9}=-2.4183991523\dots$ (the error is smaller than $10^{-78}$ for $n=120$).

The sequence $\frac{\alpha_{n+1}}{\alpha_n}-\frac{\alpha_n}{\alpha_{n-1}}$ converges perhaps (fairly slowly) towards something like $-.72\dots$.

-
Roland, do you mean $-(-1)^j-\alpha_j+p\beta_j$ in the second congruence? –  Robin Chapman Aug 27 '10 at 17:49
Of course. Thank you Robin. –  Roland Bacher Aug 27 '10 at 19:37
Have you looked through the papers of Zhi-Wei Sun ? For instance, front.math.ucdavis.edu/0509.5648 contains some results about $\sum k^rC_k$ mod p which may help. –  dke Aug 27 '10 at 20:02
Indeed, this seems to explain a part of the story. –  Roland Bacher Aug 27 '10 at 21:23
Does anything interesting turn up when you factor the numerators? –  Gerry Myerson Aug 27 '10 at 22:26

Just a quick thought about showing that $3^n\alpha_n$ is integral. It's not too hard to prove via the Catalan number generating function that $$\sum_{k=0}^{p-1} C_kx^k\equiv \frac{1-(1-4x)^{(p+1)/2}}{2x}-x^{p-1}\quad\bmod (p,x^p).$$ Now apply $D=x\frac{d}{dx}$ a bunch of times and set $x=1$ to get the sums you want. Then by using $(-3)^{(p-1)/2}\equiv \left(\frac{p}{3}\right)\bmod p$ you can control the 3-adic valuation (you get an extra 3 for each differentiation) and see that the only dependence on $p$ is the Legendre symbol $\left(\frac{p}{3}\right)$ which furthermore depends only on $p$ modulo 3. There's also a 2 in the denominator but I guess by looking a bit more carefully you can show this cancels out for $p$ not equal to 3. This is a bit sketchy but hopefully the idea is there.

In particular, letting Sage do the work, I get $$\sum_{k=0}^{p-1}C_k\equiv \frac{{\left(\frac{p}{3}\right)}-1}{2}\quad\pmod p$$ $$\sum_{k=0}^{p-1}kC_k\equiv \frac{{-\left(\frac{p}{3}\right)}+1}{2}\quad\pmod p$$ $$\sum_{k=0}^{p-1}k^2C_k\equiv \frac{-{\left(\frac{p}{3}\right)}-3}{6}\quad\pmod p$$ which seem to fit your sequence as well as the results in the Zhi-Wei Sun paper.

I can't see how to get at the $\beta_j$ though.

Edited to add: one can maybe do the same trick using $$\sum_{k=0}^{p-1} C_kx^k\equiv \frac{1-(1-4x)^{(p^2+1)/2}}{2x}-px^{p-1}\quad\bmod (p^2,x^p)$$ to get the $\beta_j$ as well, though I'm not so convinced.

-

I wonder about the reason to consider $$A_j=\sum_{k=0}^{p-1}\frac{k^j}{k+1}\binom{2k}{k}$$ instead of $$\tilde A_j = \sum_{k=0}^{p-1} k^j \binom{2k}{k},$$ as $A_j\pm A_0$ ($+$ for odd $j$ and $-$ for even $j$) are reduced to linear combinations of the latter. Let me introduce the functions $$F_j(x)=\left(x\frac{d}{dx}\right)^j\sum_{k=0}^{p-1}\binom{2k}{k}x^k,$$ so that $\tilde A_j=F_j(1)$. Note that $$F_0(x)=F(x)=\sum_{k=0}^{p-1}\binom{2k}{k}x^k$$ satisfies the differential equation $$F(x)-\frac12(1-4x)F'(x)=\frac{(2p-1)!}{(p-1)!^2}x^{p-1}.$$ Here the coefficient on the right is $$\frac{(2p-1)!}{(p-1)!^2}\equiv p\pmod{p^4}$$ by Wolstenholme's theorem and we can write the equation in the form $$xF_0(x)-\frac12(1-4x)F_1(x)=\frac{(2p-1)!}{(p-1)!^2}x^p.$$ Applying repeatedly the operator $x\dfrac{d}{dx}$ to both sides of the identity produces, for each $j$, a relation of the form $$P_{0,j}(x)F_0(x)+P_{1,j}(x)F_1(x)+\dots+P_{j-1,j}(x)F_{j-1}(x)-\frac12(1-4x)F_j(x)=p^{j-1}\frac{(2p-1)!}{(p-1)!^2}x^p,$$ where all coefficients of the polynomials $P_{i,j}(x)$ are integral (and, of course, independent of $p$). This gives a way to express $\frac32F_j(1)=\frac32\tilde A_j$ as a $\mathbb Z$-linear combination of $\tilde A_0,\tilde A_1,\dots,\tilde A_{j-1}$ independently of $p$ modulo $p^j$. The remaining piece is to check that $\tilde A_0$ and $\tilde A_1$ as well as the starting $A_0$ do satisfy the "$p$-independence" property modulo $p^2$.

The construction above gives a recipe to construct recursively the sequence $\tilde A_j$ (hence $A_j$), although I do not try myself to figure out a closed-form evaluation of the auxilliary polynomials $P_{i,j}(x)$ and/or their values at $x=1$.

-