13
$\begingroup$

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} .$$

$\endgroup$
  • 2
    $\begingroup$ 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}$. $\endgroup$ – barak manos Nov 9 '16 at 9:14
  • $\begingroup$ 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. $\endgroup$ – Julian Rosen Jan 7 '17 at 17:10
14
+25
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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). $\endgroup$ – Noam D. Elkies Nov 15 '16 at 14:38
  • $\begingroup$ Thanks to Takahiro Waki for the correction (and Fermaxplanation). $\endgroup$ – Noam D. Elkies Nov 21 '16 at 3:20
  • $\begingroup$ 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)? $\endgroup$ – MathematicsStudent1122 Dec 28 '16 at 11:36
  • $\begingroup$ @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. $\endgroup$ – Noam D. Elkies Dec 28 '16 at 16:31
5
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.