# Finite Sum & Divisibility – 2

Standard

Earlier this year I discussed a finite analogue of the harmonic sum. Today I wish to discuss a simple fact about finite harmonic sums.

If $p$ is a prime integer, the numerator of the fraction $1+\frac{1}{2}+\frac{1}{3}+\ldots + \frac{1}{p-1}$ is divisible by $p$.

We wish to treat the given finite sum modulo $p$, hence we can’t just add up fractions. We will have to consider each fraction as inverse of an integer modulo p. Observe that for $0, we have inverse of each element $i$ in the multiplicative group $\left(\mathbb{Z}/p\mathbb{Z}\right)^\times$, i.e. there exist an $i^{-1}$ such that $i\cdot i^{-1}\equiv 1 \pmod p$.

For example, for $p=5$, we have $1^{-1}=1, 2^{-1}=3, 3^{-1}=2$ and $4^{-1}=4$.

Hence we have
$\displaystyle{i\cdot \frac{1}{i}\equiv 1 \pmod p ,\qquad (p-i)\cdot \frac{1}{p-i} \equiv 1 \pmod p }$
for all $0.

Hence we have:
$\displaystyle{i\left(\frac{1}{i}+\frac{1}{p-i}\right)\equiv i\cdot \frac{1}{i} - (p-i)\cdot \frac{1}{p-i} \equiv 0 \pmod p}$

Thus we have:
$\displaystyle{\frac{1}{i}+\frac{1}{p-i}\equiv 0 \pmod p}$

The desired result follows by summation.

We can, in fact, prove that the above harmonic sum is divisible by $p^2$, see section 7.8 of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers for the proof.

# Finite Sum & Divisibility

Standard

I wish to discuss a small problem from The USSR Olympiad Problem Book (problem 59) about the finite sum of harmonic series. The problem asks us to prove that

$\displaystyle{\sum_{k=2}^{n} \frac{1}{k}}$  can never be an  integer for any value of $n$.

I myself couldn’t think much about how to prove such a statement. So by reading the solution, I realised that how a simple observation about parity leads to this conclusion.

Firstly, observe that among the natural numbers from 2 to $n$ there is exactly one natural number which has the highest power of 2 as its divisor. Now, while summing up the reciprocals of these natural numbers we will get a fraction as the answer. In that fraction, the denominator will be an even number since it’s the least common multiple of all numbers from 2 to $n$. And the numerator will be an odd number since it’s the sum of $(n-2)$ even numbers with one odd number (corresponding to the reciprocal of the number with the highest power of 2 as the factor). Since under no circumstances an even number can completely divide an odd number, denominator can’t be a factor of the numerator. Hence the fraction can’t be reduced to an integer and the sum can never be an integer.

# [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$.