Show that for n > 1, (3n + 1)/(2n + 2) < ∑1n rn/nn < 2.
Suppose m <= n, then expanding by the binomial theorem, mn = ( (m-1) + 1)n = (m-1)n + n (m-1)n-1 + further positive terms > (m-1)n + n (m-1)n-1 > 2 (m-1)n. Hence nn > (n-1)n + (n-1)n > (n-1)n + (n-2)n + (n-2)n > ... > (n-1)n + (n-2)n + ... + 1n. So 2 nn > ∑1n rn, which is one of the two required inequalities.
The other is slightly harder. We approximate the integral of f(x) = xn between 0 and 1. We have to do slightly better than the usual Riemann sums. We also take into account the small triangles. The curve has increasing gradient, so the area under the curve between (r-1)/n and r/n is less than the area under the chord joining ( (r-1)/n, f( (r-1)/n ) ) and (r/n, f(r/n) ). Summing those areas gives: (1/n) ∑1n (r/n)n - (1/2n) ∑1n ( (r/n)n - ( (r-1)/n )n = (1/n) K - (1/2n) (n/n)n, where K = ∑1n (r/n)n. The integral is just 1/(n+1), so we have: 1/(n+1) < K/n - 1/(2n), or K > n/(n+1) + 1/2 = (3n+1)/(2n+2).
23rd Putnam 1962
© John Scholes
5 Feb 2002