# 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

## 2 Answers

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
• Thanks to Takahiro Waki for the correction (and Fermaxplanation). – Noam D. Elkies Nov 21 '16 at 3:20
• Dear Noam Elkies: I have a chess-related question here (link) which I would love to know the answer to. I figure that if anyone can answer it, it is you. Could you please consider answering it, or if it's a known result linking a paper with the solution(s)? – MathematicsStudent1122 Dec 28 '16 at 11:36
• @MathematicsStudent1122 I saw your question there already but had nothing to say about it. Other people here might, though. If a week goes by with no useful answer on the chess site, post it at MO (noting that it came up empty on chess stackexchange despite the rare bounty); it's really a math question, not chess. – Noam D. Elkies Dec 28 '16 at 16:31

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*}