binomial congruence $\sum_{i=1}^{\frac{p-1}{2}}\binom{2i}{i}\equiv 0~or (-2)\pmod p$

Solution 1:

It's more convenient to start the sum at $i=0$ instead of $i=1$, adding the term ${0 \choose 0} = 1$ and aiming for $$ \sum_{i=0}^{(p-1)/2} {2i \choose i} \equiv \pm 1 \bmod p. $$ To prove this, note that ${2i \choose i} \equiv 0 \bmod p$ for $(p-1)/2 < i \leq p-1$. Therefore $$ \left( \sum_{i=0}^{(p-1)/2} {2i \choose i} \right)^2 = \sum_{i=0}^{(p-1)/2} \, \sum_{j=0}^{(p-1)/2} {2i \choose i} {2j \choose j} \equiv \mathop{\sum\sum}_{i,j \geq 0}^{i+j \leq p-1} {2i \choose i} {2j \choose j} \bmod p. $$ But $\sum_{i+j = n} {2i \choose i} {2j \choose j} = 4^n$ because $2i\choose i$ is the $x^i$ coefficient of $(1-4x)^{-1/2}$. Hence $$ \left( \sum_{i=0}^{(p-1)/2} {2i \choose i} \right)^2 \equiv \sum_{n=0}^{p-1} 4^n = 1 + \sum_{n=1}^{p-1} 4^n \bmod p. $$ Since we assumed $p \geq 5$, the last sum is $4 \cdot (4^{p-1}-1)/(4-1) \equiv 0 \bmod p$ (by Fermat little theorem), so $\sum_{i=0}^{(p-1)/2} {2i \choose i}$ is a square root of $1 \bmod p$, QED.

barak manos observes in a comment that the sign $1$ or $-1$ seems to match the residue of $p \bmod 6$ (equivalently, of $p \bmod 3$ because $p$ is odd). I have checked this experimentally for all $p < 1000$. Proving it will likely require a different approach.

Postscript not so different, as it turns out. Consider the polynomial $$ P(x) = \sum_{i=0}^{(p-1)/2} {2i \choose i} (x/4)^i \bmod p. $$ The same argument as before shows that $P(x)^2 \equiv (x^p - 1) / (x-1) \bmod p$ identically; but that means $P(x)^2 \equiv (x-1)^{p-1}$, so $P(x) = \pm (x-1)^{(p-1)/2}$ (which can then also be seen directly). Comparing the coefficients of $x^{(p-1)/2}$ (or more simply, of $x$) we soon see that the sign is the Legendre symbol $(-1/p)$. Substituting some $x \bmod p$ into $(x-1)^{(p-1)/2}$ yields the Legendre symbol $((x-1)/p)$. Here $x=4$ so we get $(-1/p) (3/p) = (-3/p)$, which by quadratic reciprocity is $1$ or $-1$ according as $p$ is $1$ or $-1 \bmod 3$, QED.

Solution 2:

My solution:\begin{align*}&\sum_{i=0}^{\frac{p-1}{2}}\binom{2i}{i}=\sum_{i=0}^{\frac{p-1}{2}}\binom{2i}{i}\left(\dfrac{1}{2}+\frac{1}{2}\right)^{i} =\sum_{i=0}^{\frac{p-1}{2}}\binom{2i}{i}\sum_{j=0}^{i}\binom{i}{j}\dfrac{1}{2^i}\\ &=\sum_{i=0}^{\frac{p-1}{2}}\sum_{j=0}^{i}\dfrac{(2i)!}{2^i\cdot i!\cdot j!(i-j)!}\\ &=\sum_{i=0}^{\frac{p-1}{2}}\sum_{j=0}^{i}\dfrac{(2i-1)!!}{j!(i-j)!}\\ &\equiv\sum_{i=0}^{\frac{p-1}{2}}\sum_{j=0}^{i}\dfrac{(-1)^i(p-1)(p-3)(p-5)\cdots(p-2i+1)}{j!(i-j)!}\\ &=\sum_{i=0}^{\frac{p-1}{2}}\sum_{j=0}^{i}\dfrac{(-1)^i2^i\left(\frac{p-1}{2}\right)!}{\left(\frac{p-1-2i}{2}\right)!j!(i-j)!}\\ &=\sum_{i=0}^{\frac{p-1}{2}}\sum_{j=0}^{i}(-2)^i\binom{\frac{p-1}{2}}{i}\binom{i}{j}\\ &=\sum_{i=0}^{\frac{p-1}{2}}(-4)^i\binom{\frac{p-1}{2}}{i}\\ &=(1-4)^{\frac{p-1}{2}}\\ &=(-3)^{\frac{p-1}{2}}\\ &\equiv \pm 1\pmod p \end{align*}