Cute problem solution

Yesterday I posed the following problem: If $S$ is the set of positive integers whose decimal expansion does not contain a 3, does

\[ \sum_{n\in S}\frac{1}{n} \]

converge or diverge? My solution is after the break.

The sum converges. To see this, we’ll partition $S$ into subsets $S_k$ so that each subset contains the numbers of $S$ with exactly $k$ decimal digits. For example:

\[ \begin{align*}
S_1 &= \{ 1 , 2, 4, 5, 6, 7, 8, 9 \} \\
S_2 &= \{ 10, 11, 12, 14, \dotsc, 99 \}
\end{align*} \]

Note that the size of $S_k$ is $8\cdot9^{k-1}$ since there are 8 possibilities for the first digit (anything except 0 and 3) and 9 possibilities for each of the remaining $k-1$ digits. Also note that the smallest number in $S_k$ is $10^{k-1}$, so $1/10^{k-1}$ is an upper bound on the reciprocal of numbers in $S_k$.

Now we split our sum using the specified partition of $S$ and use the $1/10^{k-1}$ upper bound on each term with $k$ digits in the denominator:

\[ \begin{align*}
\sum_{n\in S}\frac{1}{n} &= \sum_{k=1}^\infty\sum_{n\in S_k}\frac{1}{n} \\
&\leq \sum_{k=1}^\infty\frac{8\cdot9^{k-1}}{10^{k-1}} \\
&= 8\sum_{k=1}^\infty\Bigl(\frac{9}{10}\Bigr)^{k-1} \\
&= \frac{8}{1-9/10} \\
&= 80
\end{align*} \]

Where the final summation is simplified using the summation formula for a geometric series. By the comparison test the sum in question converges, as required.

Incidentally, the problem is not my own. It was mentioned in passing in a blog comment I happened to read.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>