Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How does one prove that for a prime $p \geq 5$ the sum : $$\sum\limits_{0 < k < \frac{2p}{3}} { p \choose k}$$ is divisible by $p^{2}$.

Since each term of $\displaystyle \sum\limits_{0 < k < \frac{2p}{3}} { p \choose k}$ is divisible by $p$, only thing remains is to prove that the sum $$\sum\limits_{ 0 < k < \frac{2p}{3}} \frac{1}{p} { p \choose k}$$ is divisible by $p$.

How to evaluate this sum: $\displaystyle \frac{1}{p} { p \choose k} = \frac{(p-1)(p-2) \cdots (p-k+1)}{1 \cdot 2 \cdot 3 \cdots k}$

share|improve this question
2  
This is identical to a problem that appeared on the Putnam exam a couple decades ago. –  whuber Sep 3 '10 at 14:47

2 Answers 2

up vote 7 down vote accepted

Since we are working in the field $\mathbb{F}_p$ we can write

$$\frac{(p-1)(p-2) \cdots (p-k+1)}{1 \cdot 2 \cdots k}$$ as

$$\frac{(-1)(-2) \cdots (-(k-1))}{1 \cdot2 \cdots k}$$

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

Let $N = [\frac{2p}{3}]$ and $M = [\frac{N}{2}]$

Thus what we need is

$$ \sum_{k=1}^{N} \frac{(-1)^{k-1}}{k}$$ $$ = \sum_{k=1}^{N} \frac{1}{k} - 2 \sum_{k=1}^{M}\frac{1}{2k}$$ $$ =\sum_{k=M+1}^{N}\frac{1}{k}$$

Now $N+M+1 =p$ so we can rewrite as

$$\frac{1}{N} + \frac{1}{M+1} + \frac{1}{N-1} + \frac{1}{M+2} + \cdots = $$

$$\frac{p}{N(M+1)} + \frac{p}{(N-1)(M+2)} + \cdots $$

which is $0$.

There are $N-M$ terms, which is even, so each term gets paired off.

share|improve this answer
    
Staggering proof! One question: What made you to think of an $N$ and $M$ like that. –  anonymous Sep 3 '10 at 7:59
4  
2p/3 is in the question you gave, and when you have alternating sums, it's natural to consider it as sum it all, and minus twice the negative terms. –  Soarer Sep 3 '10 at 8:32
    
@Chandru: Leaving the - signs wasn't going anywhere. Trying to get rid of them, you come up with the N and M. So yeah, what Soarer said. +1 to Soarer's comment. –  Aryabhata Sep 3 '10 at 13:34

From your last equation one gets $$\frac1p{p\choose k}\equiv(-1)^k\frac 1k\pmod p.$$ So the problem is equivalent to $$\sum_{0 < k < 2p/3}(-1)^k\frac1k\equiv0\pmod{p}.$$

The case $p=1979$ was set as the first problem at the 1979 IMO. The method used for this extends to all primes, and no doubt you can find solutions for the IMO problem out on the interweb.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.