Prime binomial sum [Solution]

The problem was to show that

$$\sum_{k=1}^{\lfloor 2p/3 \rfloor} \binom{p}{k}$$

is divisible by $p^2$ for a prime $p \ge 5$.

Solution

---

Now working in the field $F_p$  (where division makes sense) we have that

$$\frac{\binom{p}{k}}{p} = \frac{(p-1)!}{k! (p-k)!}  = \frac{(p-1)(p-2)\dots(p-k+1)}{k!}$$

$$= \frac{(-1)(-2)\dots(-(k-1))}{k!} = \frac{(-1)^{k-1}}{k}$$


Let $T = {\lfloor 2p/3 \rfloor}, U = \lfloor \frac{T}{2} \rfloor$

Thus the sum we need to show divisible by $p$ (note that we divided by $p$ already) is

$$\sum_{k=1}^{T} \frac{(-1)^{k-1}}{k}$$


$$=  \sum_{k=1}^{T} \frac{1}{k} - 2\sum_{k=1}^{U} \frac{1}{2k}$$

$$= \sum_{k=U+1}^{T} \frac{1}{k}$$

Now $T + U + 1 = p$ so this sum becomes

$$\frac{1}{T} + \frac{1}{U+1} + \frac{1}{T-1} + \frac{1}{U+2} + \dots$$

(by coming terms from the ends)

$$= \frac{p}{T(U+1)} + \frac{p}{(T-1)(U+2)} + \dots$$

which is divisible by $p$.