p is a prime > 2. Prove that ∑_{0≤n≤p} pCn (p+n)Cn = 2^{p} + 1 (mod p^{2}). [aCb is the binomial coefficient a!/(b! (a-b)!).]

**Solution**

*Straightforward.*

Let D_{n} = pCn (p+n)Cn, so that the required sum is ∑ D_{n}. We show that D_{0} = pC0 (mod p^{2}), D_{p} = pCp + 1 (mod p^{2}), and for the other terms D_{n} = pCn (mod p^{2}). The result then follows since ∑ pCn = 2^{p}.

For n = 0, it is obvious that D_{0} = 1 = pC0.

n = p is slightly trickier. Notice that we can write (p-1)! (2p-1)C(p-1) as (1 + p)(2 + p)(3 + p) ... (p-1 + p). Expanding, we get (p-1)! + (1 + 2 + ... + p-1) p + O(p^{2}) = (p-1)! (mod p^{2}), since (1 + 2 + ... + p-1) = p (p-1)/2. Hence, (2p-1)C(p-1) = 1 (mod p^{2}). Hence 2pCp = 2p/p (2p-1)C(p-1) = 2 = 1 + pCp (mod p^{2}).

For 0 < n < p, pCn = 0 (mod p) [because all the factors in n!(p - n)! are < p and hence relatively prime to p, so the factor p in the denominator p! remains after dividing by n!(p - n)!]. Also p + i = i ≠ 0 (mod p), so (p + n) ... (p + 2)(p + 1) = n! (mod p) and hence (p+n)Cn = 1 (mod p) for 0 < n < p. In other words, (p+n)Cn = kp + 1 for some integer k. But kp pCn = 0 (mod p^{2}), since p divides pCn, so D_{n} = (p+n)Cn pCn = pCn (mod p^{2}).

© John Scholes

jscholes@kalva.demon.co.uk

24 Sep 1999