Prove that the sum from k = 0 to n of (2n+1)C(2k+1) 23k is not divisible by 5 for any non-negative integer n. [rCs denotes the binomial coefficient r!/(s!(r-s)!) .]
Solution
Let k = √8. Then (1 + k)2n+1 = a + bk, where b is the sum given in the question. Similarly, (1 - k)2n+1 = a - bk. This looks like a dead end, because eliminating a gives an unhelpful expression for b. The trick is to multiply the two expressions to get 72n+1 = 8b2 - a2. This still looks unhelpful, but happens to work, because we soon find that 72n+1 ≠ ±2 (mod 5). So if b was a multiple of 5 then we would have a square congruent to ±2 (mod 5) which is impossible.
Solutions are also available in: Samuel L Greitzer, International Mathematical Olympiads 1959-1977, MAA 1978, and in István Reiman, International Mathematical Olympiad 1959-1999, ISBN 189-8855-48-X.
© John Scholes
jscholes@kalva.demon.co.uk
10 Oct 1998