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

### 7 responses

1. Pingback: Richert Theorem | Gaurish4Math

2. gaurav1729 on said:

If I remember correclty, if we do not have the restriction that we need to choose consecutive reciprocals, then any integer can be represented by the sum of reciprocals. That is, N = sum (1/i) where {i} is some subset of the natural numbers.

Liked by 1 person

3. circlesandtrianglesblog on said:

whoops, I meant ‘if n is odd’ not ‘if t is odd’

Like

4. circlesandtrianglesblog on said:

Wow! That’s a neat solution. I think I solved it in a different way, but it involves some heavy technology…
Suppose for contradiction that 1/2 + 1/3 + … + 1/n = k for some integer k.
Multiply by n!. This gives n!/2 + n!/3 + … + n!/n = n!k.
Bertrand’s postulate – it’s been proved by Ramanujan! 🙂 – states that for each positive integer t, there exists a prime p greater than t and at most 2t. If n is even, we take t = n/2. If t is odd, we take t = (n – 1)/2. These both tell us that there exists a prime p greater than n/2 but at most n. Thus in the equation n!/2 + n!/3 + … + n!/n = n!k, every term is divisible by p except n!/p. This cannot be divisible by p as none of the integers 2, 3, … n are divisible by p except p itself, since n is less than 2p.
Now we have a contradiction since the right hand side of the equation n!/2 + n!/3 + … + n!/n = n!k. is divisible by p, but the left hand side is not.
Does that work? I’m sure there must be a way to do a similar proof without using Bertrand’s postulate…finding a prime that divides every term but one…

Liked by 1 person

• gaurish on said:

Sure the solution is correct. Just to complete, here is Erdős’s elementary proof of the postulate: https://gaurish4math.files.wordpress.com/2014/12/erdos.pdf

Before going through the solution from the book, I tried solving it by the method of contradiction. But I failed to achieve that using some high-school level arguments. I didn’t even imagine that Bertrand’s Postulate would be useful. If you find a way of achieving contradiction which avoids Bertrand’s postulate, do let me know.

Like