Challenge XI: Harmonic Numbers

[micromass]

This challenge was suggested by jgens.

The $n$th harmonic number is defined by

$$H_n = \sum_{k=1}^n \frac{1}{k}$$

Show that $H_n$ is never an integer if $n\geq 2$.

 

[mfb]

For a fixed n>5, consider the largest prime number $p \leq n$. According to Bertrand's postulate, $p>\frac{n}{2}$. Therefore, apart from p itself no other number $i \leq n$ is divisible by p.

$H_n \frac{n!}{p}$ has only integer summands - with the only exception of $\frac{1}{p}\frac{n!}{p}$ as n! just has one factor of p. Therefore, $H_n \frac{n!}{p}$ is not an integer.
If $H_n$ would be integer, $H_n \frac{n!}{p}$ would be integer as well -> contradiction.

For 1<n<6, just calculate H_n.

 

[micromass]

Well done!

 

[Borek]

Math is not something I feel confident about, but I think I have a very elementary proof. Every harmonic number is a rational number:

$$H_n = \frac a b$$

For n=2 denominator is an even number, and numerator is an odd number:

$$H_2 = \frac 3 2$$

For obvious reasons

$$H_{n+1} = H_n + \frac 1 n$$

We can use the induction to show all harmonic numbers for n≥2 have odd numerators and even denominators.

For odd n

$$\frac a b + \frac 1 n = \frac {na+b}{nb}$$

where na is odd and b is even, so denominator nb is again even and numerator na+b is again odd. For even n we can write b=2c and n=2m, then

$$\frac a {2c} + \frac 1 {2m} = \frac {2ma+2c}{4mc} = \frac {ma+c}{2mc}$$

where again ma+c is odd and 2mc is even. So all harmonic numbers for n≥2 have odd numerators and even denominators, and neither can be an integer.

I got the clue about odd/even thing from http://mathworld.wolfram.com/HarmonicNumber.html.

 

[mfb]

I don't see why ma+c has to be odd. a is odd, but we have no information about m and c.

(I expect that your observation is true, but I don't see how your post proves this)

 

[mathsman1963]

There is a way of proving that all the harmonic numbers greater than 1 are fractions with an odd numerator and an even denominator.

Consider the denominators 1, 2, ...,2^k, ...,n where k is the largest power of 2 such that 2^k is less than or equal to n. Remove the fraction with the 2^k denominator and add together the remaining fractions. The result will be a fraction of the form

$$\frac {P}{2^{k-1}Q}$$
where P is any integer and Q is an odd integer.

Now add in the fraction $\frac 1 {2^k}$ and the result is
$$\frac {2P+Q}{2^{k}Q}$$
an odd numerator divided by an even denominator. Therefore it cannot be an integer.

Apologies for the lack of tex, I've not used it before.

 

[Borek]

I don't see why ma+c has to be odd. a is odd, but we have no information about m and c

Good point. mathsman1963 already posted another approach, here is my attempt to plug the hole:

For even n we have b=2^kc and n=2^lm (where c and m are odd), so

$$\frac a b + \frac 1 n = \frac a{2^kc} + \frac 1{2^lm} = \frac {2^lma + 2^kc}{2^{k+l}mc}$$

After canceling powers of 2 numerator is odd (either because ma is odd or because c is odd) and denominator is even (as k+l is greater than k and l).

 

[mathsman1963]

Good point. mathsman1963 already posted another approach, here is my attempt to plug the hole:

For even n we have b=2^kc and n=2^lm (where c and m are odd), so

$$\frac a b + \frac 1 n = \frac a{2^kc} + \frac 1{2^lm} = \frac {2^lma + 2^kc}{2^{k+l}mc}$$

After canceling powers of 2 numerator is odd (either because ma is odd or because c is odd) and denominator is even (as k+l is greater than k and l).

What if k=l? Then we get

$$\frac a b + \frac 1 n = \frac a{2^kc} + \frac 1{2^lm} = \frac {2^l(ma + c)}{2^{l}mc}$$

The 2^l s cancel to leave

$$\frac{ma + c}{mc}$$

even divided by odd.

 

[mfb]

What if k=l? Then we get

$$\frac a b + \frac 1 n = \frac a{2^kc} + \frac 1{2^lm} = \frac {2^l(ma + c)}{2^{l}mc}$$

The exponent in the denominator is l+k, you get 2l:

$$\frac a b + \frac 1 n = \frac a{2^kc} + \frac 1{2^{l}m} = \frac {2^l(ma + c)}{2^{2l}mc} = \frac {ma + c}{2^{l}mc}$$
We might get more factors of 2, but we still don't know how many factors of 2 we have in ma+c.

Your direct approach works, and it looks similar to my proof (just with powers of 2 instead of a prime number).

 

[mathsman1963]

Apologies, I made a boo-boo. (I'm getting carried away with this Tex business.)

The fraction should be

$$\frac {am+c}{2^{l}mc}$$

The numerator is clearly even but, as you say, there is no evidence for the factors of 2. If it could be shown that k can never equal l it would prove the assertion.

I tell you, I'm mastering Tex today, it'll be the Riemann Hypothesis tomorrow!

 

[Borek]

Next time you see me posting about math, just ban me [PLAIN]http://www.bpp.com.pl/IMG/grumpy_borek.png.