p is a prime > 2. Prove that ∑0≤n≤p pCn (p+n)Cn = 2p + 1 (mod p2). [aCb is the binomial coefficient a!/(b! (a-b)!).]
Solution
Straightforward.
Let Dn = pCn (p+n)Cn, so that the required sum is ∑ Dn. We show that D0 = pC0 (mod p2), Dp = pCp + 1 (mod p2), and for the other terms Dn = pCn (mod p2). The result then follows since ∑ pCn = 2p.
For n = 0, it is obvious that D0 = 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(p2) = (p-1)! (mod p2), since (1 + 2 + ... + p-1) = p (p-1)/2. Hence, (2p-1)C(p-1) = 1 (mod p2). Hence 2pCp = 2p/p (2p-1)C(p-1) = 2 = 1 + pCp (mod p2).
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 p2), since p divides pCn, so Dn = (p+n)Cn pCn = pCn (mod p2).
© John Scholes
jscholes@kalva.demon.co.uk
24 Sep 1999