63rd Putnam 2002 Problem A6 b > 1 is an integer. For any positive integer n, let d(n) be the number of digits in n when it is written in base b. Define the sequence f(n) by f(1) = 1, f(2) = 2, f(n) = n f( d(n) ). For which values of b does 1/f(1) + 1/f(2) + 1/f(3) + ... converge? Solution
: only for b = 2. We have ∑ 1/f(n) = ∑ ( 1/f(d) ∑ d digits 1/n ). But ∑ d digits 1/n > ∫ dx/x, where the integral is taken between b d-1 and b d , = ln b. Hence ∑ 1/f(n) > ln b ∑ 1/f(d). If b >= 3, then ln b > 1, so if ∑ 1/f(n) converges to k, then we have k > k. Contradiction. So for b ≥ 3, the sum does not converge. For b = 2, we have f(1) = 1, f(2) = 2, f(3) = 6, f(4) = 24, f(5) = 30, f(6) = 36, f(7) = 42. So 1/f(1) + 1/f(2) + ... + 1/f(2 n -1) = 1 + 1/2 + 1/6 + ∑ 3 n (1/f(d) ∑ d digits 1/m ). Now ln 2 = ∫ dx/x > 1/(2 d-1 + 1) + ... + 1/2 d , where the integral is from 2 d-1 to 2 d . Hence ln 2 + 1/2 d-1 - 1/2 d ≥ ∑ d digits 1/m. But ln 2 + 1/2 d-1 - 1/2 d = ln 2 + 1/2 d < ln 2 + 1/8 < 0.9 for d ≥ 3. Hence 1/f(1) + 1/f(2) + ... + 1/f(2 n -1) < 1 + 1/2 + 1/6 + 0.9 ∑ 3 n 1/f(d) (*). We claim that ∑ 1/f(n) < 4. We use induction on the finite sum. Clearly it is true for 3 terms. Now by (*) if it is true for n terms, then the sum of 2 n -1 terms is less than 1 + 1/2 + 1/6 + 0.9 2.5 < 4, so it is true for 2 n - 1 terms. 63rd Putnam 2002 © John Scholes jscholes@kalva.demon.co.uk 11 Dec 2002