Source

I got this problem from Rustan Leino, who got it from Rajeev Joshi.

I solved it and wrote up my solution.

Problem

The harmonic series (i.e., $1/1 + 1/2 + 1/3 + 1/4 + \ldots$) diverges. That is, the sum isn't finite. This differs from, e.g., a geometric series like $(1/2)^0 + (1/2)^1 + (1/2)^2 + (1/2)^3 + \ldots,$ which coverges, i.e., has a finite sum.

Consider the harmonic series, but drop all terms whose denominator represented in decimal contains a 9. For example, you'd drop terms like $1/9, 1/19, 1/90, 1/992,$ and $1/529110.$ Does the resulting series converge or diverge?

Solution
Reveal

It converges. Here's a proof that it does.

Let $\cal N$ be the set of nine-free positive integers. For any $d,$ let ${\cal N}_d$ be the set of nine-free positive integers with exactly $d$ digits.

Define $H$ as the sum in question, i.e., $H = \sum_{n \in {\cal N}} (1/n).$ For any $d \geq 1,$ define $H_d = \sum_{n \in {\cal N}_d} (1/n).$ We can see that $H = \sum_{d=1}^{\infty} H_d.$

Now, observe that for any $d > 1$ and any number $n \in {\cal N}_d,$ the first $d-1$ digits of $n$ form a nine-free positive integer and the last digit of $n$ is a digit between 0 and 8, inclusive. Also, if you take any nine-free positive integer of length $d-1$ and concatenate any digit between 0 and 8, inclusive, you get a nine-free positive integer of length $d.$ Thus, ${\cal N}_d = \bigcup_{i=0}^8 \{ 10n + i \mid n \in {\cal N}_{d-1} \}.$

This means that, for $d > 1,$ \begin{eqnarray*} H_d & = & \sum_{n \in {\cal N}_d} 1/n \\ & = & \sum_{i=0}^8 \sum_{n \in {\cal N}_{d-1}} \frac{1}{10n + i} \\ & \leq & \sum_{i=0}^8 \sum_{n \in {\cal N}_{d-1}} \frac{1}{10n} \\ & = & \sum_{i=0}^8 (1/10) \sum_{n \in {\cal N}_{d-1}} 1/n \\ & = & \sum_{i=0}^8 (1/10)H_{d-1} \\ & = & (9/10) H_{d-1}. \end{eqnarray*}

This means that, for all $d \geq 1,$ $H_d \leq (9/10)^{d-1} H_1.$ Thus, \begin{eqnarray*} H & = & \sum_{d=1}^{\infty} H_d \\ & \leq & \sum_{d=1}^{\infty} (9/10)^{d-1} H_1 \\ & = & \frac{H_1}{1 - 9/10} \\ & = & 10 H_1. \end{eqnarray*} $H_1$ is clearly finite, since it's just the sum of the first eight terms of the harmonic series. Since $H \leq 10 H_1$, we see that $H$ is finite and the sum converges. $\Box$