1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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...