Modular congruences related to sums of Catalan numbers - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T17:34:41Z http://mathoverflow.net/feeds/question/36900 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/36900/modular-congruences-related-to-sums-of-catalan-numbers Modular congruences related to sums of Catalan numbers Roland Bacher 2010-08-27T16:28:36Z 2010-10-12T11:47:44Z <p>I am curious if somebody can be helpful concerning the following experimental observation: </p> <p>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$.</p> <p>(More precisely, the sequences $3^n\alpha_n$ and $3^n\beta_n$ are seemingly integral.)</p> <p>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$$</p> <p>Let me end by remarking that one has as a special case a similar result when replacing Catalan numbers by central binomial coefficients.</p> <p>Update: The existence of the sequence $\alpha_n$ is explained by the Zhi-Wei Sun paper, see the answer by dke below.</p> <p>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$).</p> <p>The sequence $\frac{\alpha_{n+1}}{\alpha_n}-\frac{\alpha_n}{\alpha_{n-1}}$ converges perhaps (fairly slowly) towards something like $-.72\dots$.</p> http://mathoverflow.net/questions/36900/modular-congruences-related-to-sums-of-catalan-numbers/36992#36992 Answer by dke for Modular congruences related to sums of Catalan numbers dke 2010-08-28T20:04:12Z 2010-08-29T15:25:39Z <p>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 <code>$\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).$</code> 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.</p> <p>In particular, letting Sage do the work, I get <code>$\sum_{k=0}^{p-1}C_k\equiv \frac{{\left(\frac{p}{3}\right)}-1}{2}\quad\bmod p$</code> <code>$\sum_{k=0}^{p-1}kC_k\equiv \frac{{-\left(\frac{p}{3}\right)}+1}{2}\quad\bmod p$</code> <code>$\sum_{k=0}^{p-1}k^2C_k\equiv \frac{-{\left(\frac{p}{3}\right)}-3}{6}\quad\bmod p$</code> which seem to fit your sequence as well as the results in the Zhi-Wei Sun paper.</p> <p>I can't see how to get at the $\beta_j$ though.</p> <p>Edited to add: one can maybe do the same trick using <code>$\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)$</code> to get the $\beta_j$ as well, though I'm not so convinced.</p> http://mathoverflow.net/questions/36900/modular-congruences-related-to-sums-of-catalan-numbers/41887#41887 Answer by Wadim Zudilin for Modular congruences related to sums of Catalan numbers Wadim Zudilin 2010-10-12T09:03:36Z 2010-10-12T11:47:44Z <p>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 <a href="http://mathoverflow.net/questions/26137/" rel="nofollow">Wolstenholme's theorem</a> 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 <em>integral</em> (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$.</p> <p>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$.</p>