Tag Archives: harmonic series

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<i<p, 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<i<p.

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)

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.