### 23rd Putnam 1962

Problem B5

Show that for n > 1, (3n + 1)/(2n + 2) < ∑1n rn/nn < 2.

Solution

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).