42nd Putnam 1981

------
 
 
Problem B1

Evaluate limn→∞ 1/n5 ∑ (5 r4 - 18 r2 s2 + 5 s4), where the sum is over all r, s satisfying 0 < r, s ≤ n.

 

Solution

Answer: - 1.

This seems curiously difficult for a qu 1, which makes me think I am missing something!

We need: ∑1n r2 = 1/3 n3 + 1/2 n2 + O(n), and ∑1n r4 = 1/5 n5 + 1/2 n4 + O(n3).

Applying these we get that the sum given is 5 (1/5 n5 + 1/2 n4 + O(n3) ) n - 18 (1/3 n3 + 1/2 n2 + O(n) )2 + 5 (1/5 n5 + 1/2 n4 + O(n3) ) n = (n6 + 5/2 n5 + O(n4) ) - (2n6 + 6n5 + O(n4) ) + (n6 + 5/2 n5 + O(n4) ) = - n5 + O(n4). So the required limit is   - 1.

The tricky part is proving the relation for ∑ r4. A fairly trivial induction gives that ∑ r(r+1)(r+2)...(r+s) = 1/(s+2) r(r+1)...(r+s+1). Hence ∑ rk = 1/(k+1) nk+1 + O(nk). Also ∑(r4 + 6r3 + O(r2) ) = 1/5 (n5 + 10 n4 +O(n3) ). Hence ∑ r4 = 1/5 n5 + 2n4 + O(n3) - 6(1/4 n4 + O(n3) ) - ∑ O(n2) = 1/5 n5 + 1/2 n4 + O(n3). The relation for ∑ r2 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