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

Let $p\ge 5$ be a prime number. Show that $$\sum_{i=1}^{\frac{p-1}{2}}\binom{2i}{i}\equiv 0 \text{ or } -2\pmod p .$$

Examples:

If $p=5$, then $$f=\sum_{i=1}^{\frac{p-1}{2}}\binom{2i}{i}=\binom{2}{1}+\binom{4}{2}=8\equiv -2\pmod 5 .$$

If $p=7$, then $$f=\sum_{i=1}^{\frac{p-1}{2}}\binom{2i}{i}=\binom{2}{1}+\binom{4}{2}+\binom{6}{3}=28\equiv 0\pmod 7 .$$

If $p=11$, then $$f=\sum_{i=1}^{\frac{p-1}{2}}\binom{2i}{i}=\binom{2}{1}+\binom{4}{2}+\binom{6}{3}+\binom{8}{4}+\binom{10}{5}=350\equiv -2 \pmod{11} .$$

• It's worth noting (and perhaps also a direction towards solution), that if $p\equiv1\pmod6$ then $\sum\equiv0\pmod{p}$, and if $p\equiv-1\pmod6$ then $\sum\equiv-2\pmod{p}$. – barak manos Nov 9 '16 at 9:14
• If the upper limit of summation is replaced by $p-1$ (which doesn't change the value modulo $p$), the congruence actually holds modulo $p^2$. A proof is given here. – Julian Rosen Jan 7 '17 at 17:10

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.
• I later noticed that this all comes down to the following simpler argument: write $p=2n+1$; then ${2i\choose i} \equiv (-4)^i {n \choose i}$ for each $i$; so $\sum_{i=0}^n {2i \choose i}$ is congruent with the binomial expansion of $(1-4)^n$, which is the Legendre symbol $(-3/p)$. Likewise $\sum_{i=0}^n {2i \choose i} x^i \equiv (1-4x)^n$. I see that meanwhile Zander posted, but for some reason deleted, the same proof (working out the congruence ${2i\choose i} \equiv (-4)^i {n \choose i}$ in some detail). – Noam D. Elkies Nov 15 '16 at 14:38