Why Is the Sum of Certain Binomial Coefficients Divisible by \( p^2 \)?

[Ackbach]

Here is this week's POTW:

-----

If $p$ is a prime number greater than 3 and $k = \lfloor 2p/3
\rfloor$, prove that the sum
\[
\binom p1 + \binom p2 + \cdots + \binom pk
\]
of binomial coefficients is divisible by $p^2$.

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 224 - Jul 13, 2016

This was Problem A-5 in the 1996 William Lowell Putnam Mathematical Competition.

No one solved this week's POTW. The solution (due to Lenny Ng) follows :

Spoiler

$\def\mymod#1{\,\,({\rm mod}\, #1)}$
For $1 \leq n \leq p-1$, $p$ divides $\binom pn$ and
\begin{align*}
\frac{1}{p} \binom pn &= \frac{1}{n} \frac{p-1}{1} \frac{p-2}{2} \cdots
\frac{p-n+1}{n-1} \\
&\equiv \frac{(-1)^{n-1}}{n} \mymod{p},
\end{align*}
where the congruence $x \equiv y \mymod{p}$ means that $x-y$ is a
rational number whose numerator, in reduced form, is divisible by $p$.
Hence it suffices to show that
\[
\sum_{n=1}^k \frac{(-1)^{n-1}}{n} \equiv 0 \mymod{p}.
\]
We distinguish two cases based on $p \mymod{6}$. First suppose $p =
6r+1$, so that $k = 4r$. Then
\begin{align*}
\sum_{n=1}^{4r} \frac{(-1)^{n-1}}{n}
&= \sum_{n=1}^{4r} \frac{1}{n} - 2 \sum_{n=1}^{2r} \frac{1}{2n} \\
&= \sum_{n=1}^{2r} \left( \frac{1}{n} - \frac{1}{n} \right)
+ \sum_{n=2r+1}^{3r} \left( \frac{1}{n} + \frac{1}{6r+1-n} \right) \\
&= \sum_{n=2r+1}^{3r} \frac{p}{n(p-n)} \equiv 0 \mymod{p},
\end{align*}
since $p = 6r+1$.

Now suppose $p = 6r+5$, so that $k = 4r + 3$. A similar argument gives
\begin{align*}
\sum_{n=1}^{4r+3}\ \frac{(-1)^{n-1}}{n}
&= \sum_{n=1}^{4r+3} \frac{1}{n} + 2 \sum_{n=1}^{2r+1} \frac{1}{2n} \\
&= \sum_{n=1}^{2r+1} \left( \frac{1}{n} - \frac{1}{n} \right)
+ \sum_{n=2r+2}^{3r+2} \left( \frac{1}{n} + \frac{1}{6r+5-n} \right) \\
&= \sum_{n=2r+2}^{3r+2} \frac{p}{n(p-n)} \equiv 0 \mymod{p}.
\end{align*}