### 42nd Putnam 1981

**Problem B5**

f(n) is the number of 1s in the base 2 representation of n. Let k = ∑ f(n) / (n + n^{2}), where the sum is taken over all positive integers. Is e^{k} rational?

**Solution**

Answer: yes.

Obviously f(2n+1) = f(2n) + 1 (because the base 2 representation for 2n+1 is the same as that for 2n with an additional 1 at the end). Note also that f(2n) = f(n).

Let us look at the adjacent terms f(2n) /( 2n(2n + 1) ), and f(2n + 1) / ( (2n+1)(2n+2) ). They sum to 1/ ( (2n+1)(2n+2) ) + 2 f(2n) / ( 2n(2n+2) ) = 1/ ( (2n+1)(2n+2) ) + 1/2 f(n) / ( n(n+1) ). Thus we get k = f(1)/2 + ∑_{1}^{∞} ( 1/ ( (2n+1)(2n+2) ) + 1/2 f(n) / ( n(n+1) ) = (1 - 1/2 + 1/3 - 1/4 + ... ) + 1/2 k [since 1/( (2n+1)(2n+2) ) = 1/(2n+1) - 1/(2n+2) ]. Thus k = 2 ln 2 = ln 4. So e^{k} = 4.

42nd Putnam 1981

© John Scholes

jscholes@kalva.demon.co.uk

16 Jan 2001