7

I'm working on the following contest math problem:

Define an evil number to be any positive integer that contains the digit $9$. Show that

$$ \sum_{x} \frac{1}{x} < 80 $$

where the sum is over all non-evil positive integers $x$.

I'm very confused on where to begin. Initially, I tried to consider this sum as part of the sum of $1/x$ over all positive integers, namely by noting that

$$ \sum_{n=1}^{\infty} \frac{1}{n} = \sum_{x} \frac{1}{x} + \sum_{y} \frac{1}{y} $$

where the first summation on the right side is the same as in the problem statement and the second is the sum over all evil numbers. However, I can't seem to find a way to use this since the sum of the left diverges.

Could anyone lend a helping hand?

Martin Sleziak
  • 53,687
Ryan Cho
  • 71

1 Answers1

3

There are $8\cdot9^{k-1}$ $k$ digit numbers without a $9$. Even if we take $8\cdot9^{k-1}$ times the reciprocal of the smallest $k$ digit number, we get the overestimate $$ \begin{align} \sum_{j=10^{k-1}}^{10^{k-1}+8\cdot9^{k-1}-1}\frac1j &\le8\left(\frac9{10}\right)^{k-1} \end{align} $$ Add these up for $k\ge1$, we get $$ \begin{align} \sum_{k=1}^\infty8\left(\frac9{10}\right)^{k-1} &=8\frac1{1-\frac9{10}}\\ &=80 \end{align} $$

robjohn
  • 345,667