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!

Discrete Math Problem : Mathematical Induction

  1. Mar 14, 2010 #1
    1. The problem statement, all variables and given/known data

    Prove that H1 +H2 +...+Hn = (n +1)(Hn-n)?

    2. Relevant equations

    Hn denotes the nth harmonic number.

    The nth harmonic number is the sum of 1+1/2+...1/n,
    which is n / n +1.

    I'm not really sure if Hn = (1/ n) .

    Prove by Mathematical Induction

    Hn denotes the nth harmonic number.

    3. The attempt at a solution

    Basis Step : P(1) = Hn = (n +1)(Hn-n)
    (1 / n) = (n +1) ( (1 / n) -n)
    (1) = ( 1 + 1) (1-1)
    1 = (2) (0)
    1 = 0, which is false

    or
    Basis Step:
    P(1) = Hn = Hn = (n +1)(Hn-n)
    ( n / n + 1) = (n + 1) ( (n / n + 1) -1)

    P(1) is false, because 1/ 2 does not equal to - 1
     
  2. jcsd
  3. Mar 14, 2010 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Well, it can't be both [itex]n/(n+1)[/itex] and [itex]1/n[/itex]. In fact, I don't think it is either one. As far as I know, there is no simple formula for [itex]H_n[/itex].

    Let's start with the induction hypothesis. Namely, we need to check that the formula is correct for [itex]n = 1[/itex]. Plugging in [itex]n = 1[/itex], the formula reduces to

    [tex]H_1 = (1 + 1)(H_1 - 1)[/tex]

    Is this correct?
     
  4. Mar 15, 2010 #3
    How would I know if its correct or not if there is no simple formula for H_n ??
     
  5. Mar 15, 2010 #4

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    There may not be a simple formula for [itex]H_n[/itex] in general, but what's [itex]H_1[/itex]? Isn't it simply 1? (Look at the defining sum.)
     
  6. Mar 15, 2010 #5
    I think H1= (1 / n) = 1
     
  7. Mar 15, 2010 #6

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Right, so is the formula correct for [itex]n = 1[/itex]? i.e. is it true that

    [tex]H_1 = (1+1)(H_1 - 1)[/tex]

    If not, then there is something wrong with the problem statement.
     
  8. Mar 15, 2010 #7
    No, its not true because Hn = 1
    and (1+1)(1-1) = 0

    So, there's no way to prove H1 +H2+...+Hn = (n +1) (Hn - n)
    is true, right??
     
  9. Mar 15, 2010 #8

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Correct. If it isn't even true for [itex]n = 1[/itex] then it's certainly not a valid formula.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Discrete Math Problem : Mathematical Induction
Loading...