# [poem] Harmonic Noise

Standard

———-
Harmonic Noise

One day I heard something musical,
It sounded to me mystical.
Since it was ordered,
A harmonic pattern was being followed.
The pattern was elegant,
It was inverse of each natural number element.
I made the number elements bigger hero,
The pattern approached symmetrical zero.
When I summed up the pattern without bound,
I got only noise without any musical sound.

-Gaurish
————
For more details about Harmonic series refer Wikipedia: https://en.wikipedia.org/wiki/Harmonic_series_(mathematics)

Edit (20 May 2018): A video by Marc Chamberland discussing a puzzle involving harmonic series.

# Kempner Series & MMC

Standard

In Madhava Mathematics Competition 2015 (held in January 2015), we were asked to prove the convergence of Kempner Series (first time proved in 1914). Recently I discovered the paper by A. J. Kempner (http://www.jstor.org/stable/2972074), so in this blog post I will state and prove that problem.

The basic idea behind proof is to divide whole series into chunks (finding symmetry) and then construct a converging geometric series which will act as upper bound of Kempner Seires.

A detailed study of this cartoon has been done by Ben Orlin (http://bit.ly/1KD4shF)

Theorem (Kempner Series, 1914). Harmonic Series,$\sum_{k=1}^{\infty} \frac{1}{k} = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} +\ldots$, converge, if the denominators do not include all natural numbers $1,2,3,\ldots$, but only those numbers which do not contain any figure 9.

Proof: Given Series is:
$K = \frac{1}{1}+\ldots +\frac{1}{8}+\frac{1}{10}+\ldots +\frac{1}{18}+\frac{1}{20} + \ldots + \frac{1}{28}+\frac{1}{30}+\ldots +\frac{1}{38}+\frac{1}{40}+\ldots +\frac{1}{48}+\frac{1}{50} + \ldots + \frac{1}{58}+\frac{1}{60}+\ldots+\frac{1}{68}+\frac{1}{70}+\ldots +\frac{1}{78}+\frac{1}{80} + \ldots + \frac{1}{88}+\frac{1}{100}+\ldots$
Now we can rewrite above series as:
$S = a_1 + a_2 + \ldots + a_n + \ldots$
where $a_n$ is the sum of all terms in $K$ of denominator $d$ with $10^{n-1} \leq d < 10^{n}$.
Observe that, each term of $K$ which forms part of $a_n$, is less than or equal to $1/10^{n-1}$.

Now count the number of terms of $K$ which are contained in $a_1$, in $a_2$, $\ldots$, in $a_n$. Clearly, $a_1$, consists of 8 terms, and $a_1 < 8 \cdot 1 < 9$. In $a_2$ there are, as is easily seen, less than $9^2$ terms of $K$, and $a_2 < (9^2/10)$. Altogether there are in $K$ less than $9^2 + 9$ terms with denominators under 100.

Assume now that we know the number of terms in $K$ which are contained in $a_n$ to be less than $9^n$, for $n = 1, 2, 3, \ldots, n$. Then, because each term of $K$ which is contained in $a_n$ is not greater than $1/10^{n-1}$, we have $a_n < (9^n/10^{n-1})$, and the total number of terms in $K$ with denominators under $10^n$ is less than $9^n + 9^{n-1} + 9^{n-2} + \ldots + 9^2 + 9$.

Now, let’s go for induction. For $n = 1$ and $n = 2$ we have verified all this, and we will now show that if it is true for $n$, then $a_{n+1} < (9^{n+1}/10^n)$. $a_{n+1}$ contains all terms in $K$ of denominator $d$, $10^n \leq d < 1^{n+1}$. This interval for $d$ can be broken up into the nine intervals,  $\alpha \cdot 10^n \leq d < (\alpha + 1)10^n$, $\alpha = 1,2, \ldots, 9$. The last interval does not contribute any term to $K$, the eight remaining intervals contribute each the same number of terms to $K$, and this is the same as the number of terms contributed by the whole interval $0 < d < 10^n$, that is, by assumption, less than $9^n + 9^{n-1} + 9^{n-2} + \ldots + 9^2 + 9$.

Therefore, $a_{n+1}$ contains less than $8(9^n + 9^{n-1} + 9^{n-2} +\ldots + 9^2 + 9) < 9^{n+1}$ terms of $K$, and each of these terms is less than or equal to $1/10$, we have $a_{n+1} < (9^{n+1}/10^n)$.

Hence, $S = a_1 + a_2 + a_3 + \ldots < 9 + \frac{9}{10} + \ldots + \frac{9^{n+1}}{10^n}+ \ldots = 90$
Thus, $S$ converges, and since, $K=S$, $K$ also converges.

——————————–
Note: There is nothing special about 9 here, the above method of proof holds unchanged if, instead of 9, any other figure $1, 2, \ldots, 8$ is excluded, but not for the figure $0$.