Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge XI: Harmonic Numbers

  1. Aug 20, 2013 #1

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    This challenge was suggested by jgens.

    The ##n##th harmonic number is defined by

    [tex]H_n = \sum_{k=1}^n \frac{1}{k}[/tex]

    Show that ##H_n## is never an integer if ##n\geq 2##.
     
  2. jcsd
  3. Aug 20, 2013 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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 Hn.
     
  4. Aug 20, 2013 #3

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Well done!
     
  5. Aug 20, 2013 #4

    Borek

    User Avatar

    Staff: Mentor

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

    [tex]H_n = \frac a b[/tex]

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

    [tex]H_2 = \frac 3 2[/tex]

    For obvious reasons

    [tex]H_{n+1} = H_n + \frac 1 n[/tex]

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

    For odd n

    [tex]\frac a b + \frac 1 n = \frac {na+b}{nb}[/tex]

    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

    [tex]\frac a {2c} + \frac 1 {2m} = \frac {2ma+2c}{4mc} = \frac {ma+c}{2mc}[/tex]

    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.
     
  6. Aug 20, 2013 #5

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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)
     
  7. Aug 21, 2013 #6
    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, ...,2k, ...,n where k is the largest power of 2 such that 2k is less than or equal to n. Remove the fraction with the 2k denominator and add together the remaining fractions. The result will be a fraction of the form

    [tex]\frac {P}{2^{k-1}Q}[/tex]
    where P is any integer and Q is an odd integer.

    Now add in the fraction [itex]\frac 1 {2^k}[/itex] and the result is
    [tex]\frac {2P+Q}{2^{k}Q}[/tex]
    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.
     
    Last edited: Aug 21, 2013
  8. Aug 21, 2013 #7

    Borek

    User Avatar

    Staff: Mentor

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

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

    [tex]\frac a b + \frac 1 n = \frac a{2^kc} + \frac 1{2^lm} = \frac {2^lma + 2^kc}{2^{k+l}mc}[/tex]

    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).
     
  9. Aug 21, 2013 #8
    What if k=l? Then we get

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

    The 2l s cancel to leave

    [tex]\frac{ma + c}{mc}[/tex]

    even divided by odd.
     
  10. Aug 21, 2013 #9

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

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

    [tex]\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}[/tex]
    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).
     
  11. Aug 21, 2013 #10
    Apologies, I made a boo-boo. (I'm getting carried away with this Tex business.)

    The fraction should be

    [tex]\frac {am+c}{2^{l}mc}[/tex]

    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!
     
  12. Aug 21, 2013 #11

    Borek

    User Avatar

    Staff: Mentor

    Next time you see me posting about math, just ban me [PLAIN]http://www.bpp.com.pl/IMG/grumpy_borek.png. [Broken]
     
    Last edited by a moderator: May 6, 2017
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge XI: Harmonic Numbers
  1. Master's Challenge (Replies: 15)

  2. A Euclidean Challenge (Replies: 10)

Loading...