2023-01-07

Sum of harmonic series without 9s

Yesterday, I stumbled across the following question:

Does the following sum converge if you exclude all terms that don't include a 99?

∑n=1∞1n. \sum_{n=1}^{\infty}\frac{1}{n}.

A little dash of anthropic reasoning suggests yes. Why would anyone have written the question on a poster and fixed it to the wall if otherwise? The base rate for chaotic trolls who also like math puzzles seems pretty low.

Fortunately, we can do better than anthropic reasoning, and, after thinking about it for a bit with Matt MacDermott, we found the answer:

First, let's rewrite the sum as

S=∑n=1∞1nIn, S = \sum_{n=1}^{\infty} \frac{1}{n} I_n,

where InI_n is an indicator function,

In={1if 9 is a digit of n,0otherwise. I_{n}= \begin{cases} 1 & \text{if }9\text{ is a digit of }n,\\ 0 & \text{otherwise.} \\ \end{cases}

The trick is to convert this sum over numbers into a sum over numbers of digits, then find an upper bound:

∑n=1∞1nIn=∑d=0∞∑n′=10d10d+11n′In′<∑d=0∞∑n′=10d10d+1110dIn′=∑d=0∞110dNd, \sum_{n=1}^{\infty}\frac{1}{n} I_{n}= \sum_{d=0}^{\infty} \sum\limits_{n'=10^{d}}^{10^{d+1}}\frac{1}{n'} I_{n'} < \sum_{d=0}^{\infty} \sum\limits_{n'=10^{d}}^{10^{d+1}} \frac{1}{10^{d}}I_{n'} = \sum_{d=0}^{\infty} \frac{1}{10^{d}} N_d,

where NdN_{d} is the number of numbers with dd digits that don't contain 99, which we can compute by straightforward combinatorics,

Nd=∑n′=10d10d+1In′=8×9d−1. N_d=\sum\limits_{n'=10^{d}}^{10^{d+1}} I_{n'} = 8 \times 9^{d-1}.

So we end up with a new infinite sum for an upper bound to our original sum:

∑n=1∞1nIn<∑d=0∞8×9d−110d<∑d=0∞(910)d=11−910=10, \sum\limits_{n=1}^{\infty} \frac{1}{n} I_{n} < \sum\limits_{d=0}^{\infty} \frac{8 \times 9^{d-1}}{10^{d} }<\sum\limits_{d=0}^{\infty} \left(\frac{9}{10}\right)^{d}= \frac{1}{1-\frac{9}{10}} = 10,

which converges.