Putnam 1996, Problem A-5

If \( p \) is a prime number greater than 3 and \( k = \lfloor 2p/3 \rfloor \), prove that the sum  
\[
\binom{p}{1} + \binom{p}{2} + \cdots + \binom{p}{k}
\]  
of binomial coefficients is divisible by \( p^2 \).

Solution:
(due to Lenny Ng) For \(1 \leq n \leq p - 1\), \(p\) divides \(\binom{p}{n}\) and  
\[
\frac{1}{p}\binom{p}{n} = \frac{1}{n} \cdot \frac{p - 1}{1} \cdot \frac{p - 2}{2} \cdots \frac{p - n + 1}{n - 1} \equiv \frac{(-1)^{n - 1}}{n} \pmod{p},
\]  
where the congruence \(x \equiv y \pmod{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 \pmod{p}.
\]  

We distinguish two cases based on \(p \pmod{6}\). First suppose \(p = 6r + 1\), so that \(k = 4r\). Then  
\[
\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 \pmod{p},
\]  
since \(p = 6r + 1\).  

Now suppose \(p = 6r + 5\), so that \(k = 4r + 3\). A similar argument gives  
\[
\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 \pmod{p}.
\]