Jun25

Finite Sum & Divisibility

Posted on by
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. 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. Pingback: Finite Sum & Divisibility – 2 | Gaurish4Math

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

    • 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