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!

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
    -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
    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.

  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
    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).

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

  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
    Hi gruba:

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

  8. Oct 18, 2015 #7
    Hi gruba:

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

  9. Oct 18, 2015 #8
    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).

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted

Similar Discussions: Proof by induction
  1. Induction proof (Replies: 1)

  2. Proof By Induction (Replies: 2)

  3. Proof by induction (Replies: 1)

  4. Induction Proofs (Replies: 3)

  5. Induction Proof (Replies: 11)