42nd Putnam 1981 Problem B1 Evaluate lim n→∞ 1/n 5 ∑ (5 r 4 - 18 r 2 s 2 + 5 s 4 ), where the sum is over all r, s satisfying 0 < r, s ≤ n. Solution
: - 1. This seems curiously difficult for a qu 1, which makes me think I am missing something! We need: ∑ 1 n r 2 = 1/3 n 3 + 1/2 n 2 + O(n), and ∑ 1 n r 4 = 1/5 n 5 + 1/2 n 4 + O(n 3 ). Applying these we get that the sum given is 5 (1/5 n 5 + 1/2 n 4 + O(n 3 ) ) n - 18 (1/3 n 3 + 1/2 n 2 + O(n) ) 2 + 5 (1/5 n 5 + 1/2 n 4 + O(n 3 ) ) n = (n 6 + 5/2 n 5 + O(n 4 ) ) - (2n 6 + 6n 5 + O(n 4 ) ) + (n 6 + 5/2 n 5 + O(n 4 ) ) = - n 5 + O(n 4 ). So the required limit is - 1. The tricky part is proving the relation for ∑ r 4 . A fairly trivial induction gives that ∑ r(r+1)(r+2)...(r+s) = 1/(s+2) r(r+1)...(r+s+1). Hence ∑ r k = 1/(k+1) n k+1 + O(n k ). Also ∑(r 4 + 6r 3 + O(r 2 ) ) = 1/5 (n 5 + 10 n 4 +O(n 3 ) ). Hence ∑ r 4 = 1/5 n 5 + 2n 4 + O(n 3 ) - 6(1/4 n 4 + O(n 3 ) ) - ∑ O(n 2 ) = 1/5 n 5 + 1/2 n 4 + O(n 3 ). The relation for ∑ r 2 can be obtained similarly, although most people probably remember the exact formula 1/6 n(n+1)(2n+1), which is easy to prove by induction. 42nd Putnam 1981 © John Scholes jscholes@kalva.demon.co.uk 16 Jan 2001