Maths Olympiad Prep

Library / /45 of 64

Algebra Difficulty 8.1 Shortlist Find the answer

Fix an integer b2b \geq 2. Let f(1)=1f(1) = 1, f(2)=2f(2) = 2, and for each n3n \geq 3, define f(n)=nf(d)f(n) = n f(d), where dd is the number of base-bb digits of nn. For which values of bb does n=11f(n)\sum_{n=1}^\infty \frac{1}{f(n)} converge?

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

The sum converges for b=2b=2 and diverges for b3b \geq 3. We first consider b3b \geq 3. Suppose the sum converges; then the fact that f(n)=nf(d)f(n) = n f(d) whenever bd1nbd1b^{d-1} \leq n \leq b^{d} - 1 yields n=11f(n)=d=11f(d)n=bd1bd11n.\sum_{n=1}^\infty \frac{1}{f(n)} = \sum_{d=1}^\infty \frac{1}{f(d)} \sum_{n=b^{d-1}}^{b^d - 1} \frac{1}{n}. However, by comparing the integral of 1/x1/x with a Riemann sum, we see that n=bd1bd11n>bd1bddxx=log(bd)log(bd1)=logb,\sum_{n=b^{d-1}}^{b^d - 1} \frac{1}{n} > \int_{b^{d-1}}^{b^d} \frac{dx}{x} = \log (b^d) - \log (b^{d-1}) = \log b, where log\log denotes the natural logarithm. Thus the sum diverges for b3b \geq 3. For b=2b=2, we have a slightly different identity because f(2)2f(2)f(2) \neq 2 f(2). Instead, for any positive integer ii, we have n=12i11f(n)=1+12+16+d=3i1f(d)n=2d12d11n.\sum_{n=1}^{2^i-1} \frac{1}{f(n)} = 1 + \frac{1}{2} + \frac{1}{6} + \sum_{d=3}^i \frac{1}{f(d)} \sum_{n=2^{d-1}}^{2^d - 1} \frac{1}{n}. Again comparing an integral to a Riemann sum, we see that for d3d\geq 3, n=2d12d11n<12d112d+2d12ddxx=12d+log218+log2<1.\sum_{n=2^{d-1}}^{2^d - 1} \frac{1}{n} < \frac{1}{2^{d-1}} - \frac{1}{2^d} + \int_{2^{d-1}}^{2^d} \frac{dx}{x} = \frac{1}{2^d} + \log 2 \leq \frac{1}{8} + \log 2 < 1. Put c=18+log2c = \frac{1}{8} + \log 2 and L=1+12+16(1c)L = 1+\frac{1}{2} + \frac{1}{6(1-c)}. Then we can prove that n=12i11f(n)<L\sum_{n=1}^{2^i-1} \frac{1}{f(n)} < L for all i2i \geq 2 by induction on ii. The case i=2i=2 is clear. For the induction, note that n=12i11f(n)<1+12+16+cd=3i1f(d)<1+12+16+c16(1c)=1+12+16(1c)=L,\sum_{n=1}^{2^i-1} \frac{1}{f(n)} < 1 + \frac{1}{2} + \frac{1}{6} + c \sum_{d=3}^i \frac{1}{f(d)} < 1 + \frac{1}{2} + \frac{1}{6} + c \frac{1}{6(1-c)} = 1 + \frac{1}{2} + \frac{1}{6(1-c)} = L, as desired. We conclude that n=11f(n)\sum_{n=1}^\infty \frac{1}{f(n)} converges to a limit less than or equal to LL.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.