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!

Homework Help: Proof by induction

  1. Oct 18, 2015 #1
    1. The problem statement, all variables and given/known data
    Prove that [itex]\forall n\in \mathbb{N}[/itex]
    [tex]\sum\limits_{k=1}^{n}(-1)^{k+1}{n\choose k}\frac{1}{k}=1+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}[/tex]

    2. Relevant equations
    -Induction
    -Summation
    -Binomial coefficient

    3. The attempt at a solution

    For [itex]n=1[/itex] equality is true.

    For [itex]n=m[/itex]

    [itex]m-{m\choose 2}\frac{1}{2}+...+(-1)^{m+1}\frac{1}{m}=1+\frac{1}{2}+...+\frac{1}{m}[/itex]

    For [itex]n=m+1[/itex]

    [itex]\left(\sum\limits_{k=1}^{m}(-1)^{k+1}{m\choose k}\frac{1}{k}\right)+(-1)^{m+2}\frac{1}{m+1}=1+\frac{1}{2}+...+\frac{1}{m+1}[/itex]

    If [itex]m[/itex] is even, equality is true, but not if [itex]m[/itex] is odd.
    Is this correct?

    Could someone explain this in detail?
     
  2. jcsd
  3. Oct 18, 2015 #2

    Buzz Bloom

    User Avatar
    Gold Member

    Hi gruba:

    You have made some mistakes.

    (1) The series being added does not include (-1)k+1. That series should be 1-1/2+1/3-1/4...

    (2) The series being added does not include (m over k) with each of the fractions.

    Hint: For (m over k) see: https://en.wikipedia.org/wiki/Combination

    I hope this helps.

    Regards,
    Buzz
     
  4. Oct 18, 2015 #3
    Are you sure it is a mistake?
    I have some solution which I don't inderstand:

    [itex]\sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1} x^k = 1-(1-x)^n\tag{1}[/itex]
    [itex]\sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1}\frac{1}{k} = \int_{0}^{1}\frac{1-(1-x)^n}{x}\,dx= \int_{0}^{1}\frac{1-x^n}{1-x}\,dx\tag{2}[/itex]
    [itex]\sum_{k=1}^{n}\binom{n}{k}(-1)^{k+1}\frac{1}{k} = \int_{0}^{1}\left(1+x+\ldots+x^{n-1}\right)\,dx = 1+\frac{1}{2}+\ldots+\frac{1}{n}=H_n\tag{3}[/itex]
     
  5. Oct 18, 2015 #4

    Buzz Bloom

    User Avatar
    Gold Member

    Hi gruba:

    Your (1) is OK.
    The left hand equality in your (2) is OK. I don't see how you get the right hand equality in your (2).

    ADDED
    Ah. You substituted x -> (1-x). You forgot to also substitute dx -> -dx.

    Regards,
    Buzz
     
  6. Oct 18, 2015 #5
    This is my book's solution which I don't understand.
    Is there some approach which doesn't involve integration?
     
  7. Oct 18, 2015 #6

    Buzz Bloom

    User Avatar
    Gold Member

    Hi gruba:

    I edited a bit more to my last post after you responded. Please take another look at my previous post.

    Regards,
    Buzz
     
  8. Oct 18, 2015 #7

    Buzz Bloom

    User Avatar
    Gold Member

    Hi gruba:

    Sorry. My mistake. The missing minus sign is corrected by reversing the top and bottom limits of the integration.

    Regards,
    Buzz
     
  9. Oct 18, 2015 #8

    Buzz Bloom

    User Avatar
    Gold Member

    Hi gruba:

    My apologies for my earlier confusion.

    The derivation (1), (2) and (3) is a proof of the original equality. However it is not a proof by induction.

    Going back to your original post, after
    the (m over k) in the summation should be (m+1 over k).

    Regards,
    Buzz
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Loading...