## How big is the infinity?

For sure we all remember from highschool (or university if you are not Romanian 🙂 ) that the harmonic series converges to infinity:

$\displaystyle\lim_{n \to \infty}\left( 1 + \frac{1}{2} + \cdots+ \frac{1}{n} \right) = \displaystyle\lim_{n \to \infty}\displaystyle\sum_{i=1}^{n}\frac{1}{i} = \infty$

This can be proved with Lagrange theorem  🙂  applied for logarithmic function. Maybe I’ll add a post with the proof later.

Years ago I meet a really interesting problem proposed at one of the calculus exams at Berkeley. Consider the set of all the positive integers that don’t contain the digit 9. In math notation:

$X = \left\{p \in \mathbb{N^*}| {p\;don't\;contain\;digit\;9} \right\}$

Then:

$\displaystyle\sum_{p \in X}\frac{1}{p} < \infty$

This is really interesting. Apparently the numbers that don’t contain the digit 9 are not so many, but if we don’t add their inverses to harmonic series we end up with a finite result. Even more, if we consider the sum of the inverses of numbers that contain the digit 9, this will converge to infinity.

To prove this, remember an old post related to how many numbers don’t contain the digit 9. I explained there that the count of numbers that don’t contain the digit 9, and having up to n digits is $9^n$. We also counted $0$, so the number of strictly positive integers is $9^n-1$. The sum we need to compute can be grouped based on the number of digits of the numbers:

$\displaystyle\sum_{p \in X}\frac{1}{p} = \left(\displaystyle\sum_{p \in X \cap [10^0, 10^1-1]}\frac{1}{p}\right)+\left(\displaystyle\sum_{p \in X \cap [10^1, 10^2-1]}\frac{1}{p}\right)+\left(\displaystyle\sum_{p \in X \cap [10^2, 10^3-1]}\frac{1}{p}\right)+\cdots$

$= \displaystyle\sum_{i=1}^{\infty}\left(\displaystyle\sum_{p \in X \cap [10^{i-1}, 10^i-1]}\frac{1}{p}\right)$

A term of the above summation means actually the sum of the inverses of positive integers having i digits and that don’t contain the digit 9. So each term consist of an other sum having $9^i-9^{i-1}$ terms. Then for each term we have the following inequality (if you understand it in less than 1 minute you are good 🙂 ):

$\displaystyle\sum_{p \in X \cap [10^{i-1}, 10^i-1]}\frac{1}{p} < \frac{9^i-9^{i-1}}{10^{i-1}} = 8\cdot{\left(9 \over 10\right)}^{i-1}$

Summing over i:

$\displaystyle\sum_{i=1}^{\infty}\left(\displaystyle\sum_{p \in X \cap [10^{i-1}, 10^i-1]}\frac{1}{p}\right)\le\displaystyle\sum_{i=1}^{\infty}8\cdot{\left(9 \over 10\right)}^{i-1}=8\cdot\frac{1}{1-\frac{9}{10}}=80$

Now it is clear that:

$\displaystyle\sum_{p \in X}\frac{1}{p} < \infty$

Even more, the sum is less than 80.

If you followed the proof up to this point then you probably noticed that:

$\displaystyle\lim_{n \to \infty}\displaystyle\sum_{i=1}^{n}\frac{1}{i}$ is the sum of inverses positive integers that CONTAIN digit 9 plus the sum of inverses of integers that DON”T CONTAIN digit 9. But we just proved that the sum of inverses of integers that don’t contain digit 9 is finite. Because the harmonic series is infinite it follows that the sum of inverses of integers that contain digit 9 converges to infinity? Yes, this is true, even if at first glance there seem to be more numbers that don’t contain digit 9 than numbers that contain digit 9. I’ll give details in my next post.