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: Induction proof

  1. Mar 2, 2010 #1
    1. The problem statement, all variables and given/known data
    This is my first proof by induction so I need some assistance

    If n is a positive integer, then [tex]\sum1/(k(k+1))[/tex]from k=1 to n is equal to n/(n+1)



    2. Relevant equations
    I'm not sure if this is useful for this proof but we are given the proposition:
    let n be a positive integer. Then the sum of the first n positive integers is equal to (n(n+1))/2.


    3. The attempt at a solution
    (1) Let S be the set of all positive integers k such that 1/2+1/6+...+1/k(k+1)= n/(n+1)
    (2) 1 is in S because 1/1(1+1)=1/2 which is in S (not sure if this is the correct approach)
    (3) Let n be any element of S and let t=n+1

    Am I on the right track? For my next step would I just substitute t=n+1 and solve?
    Thanks
     
  2. jcsd
  3. Mar 2, 2010 #2

    statdad

    User Avatar
    Homework Helper

    Try decomposing

    [tex]
    \frac{1}{k(k+1)}
    [/tex]

    into partial fractions, and writing your original sum in terms of those partial fractions.
     
  4. Mar 2, 2010 #3
    Thank you statdad I believe this helped but am still curious about my step (2).
    Here is what I have changed:

    (1)Let S be the set of all positive integers k such that 1/2+(1/2)(1/3)+...+(1/k)(k+1)= n/(n+1)
    (2) 1 is in S because (1/1)(1/2)=1/2 which is in S (not sure if this is the correct approach)
    (3) Let n be any element of S and let t=n+1
    (4) (1/1)(1/2)+(1/2)(1/3)+...+(1/n)(1/n+1)+(1/t)(1/t+1)=(n/(n+1))+(1/t)(1/t+1)
    (5) n=t-1
    (6) Substituting this into the right hand side leads to: t/(t+1)

    I'm pretty sure that's the way to do it I did the algebra for step 6 but did not want to include all the steps. Is (2) correctly justified?

    Thanks again
     
  5. Mar 2, 2010 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Step (2) in your proof is hard to argue with. There's only one term in the sum which is 1/(1*2) And your formula for the sum of the series F(n)=n/(n+1) is also 1/2. I'm not really following what you did for the other steps. You want to prove F(n+1)-F(n)=1/((n+1)*(n+2)), right? Since that's the extra term you added on to the series. I'm pretty unclear on what algebra you actually did. BTW statdad was pointing out a noninductive way to prove it using telescoping series.
     
    Last edited: Mar 2, 2010
  6. Mar 3, 2010 #5
    No, I do not want to prove F(n+1)-F(n)=1/((n+1)*(n+2)).

    Here is my algebra for my last step, maybe it will clarify things:

    once we let n=t-1 and plug it into (n/(n+1))+(1/t)(1/t+1) we get the following:
    ((t-1)/t)+(1/(t(t+1))) finding a common denominator gives ((t+1)(t-1)+1)/(t(t+1))

    Multiplying out the numerator gives t2/(t(t+1))

    A t in the numerator and denominator cancel giving t/(t+1)
    Therefore t is in the form we are looking to prove therefore meaning that t=n+1 exists in S.

    Does this make sense now?
     
  7. Mar 3, 2010 #6

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Ah, I see. Your n/(n+1) is my F(n). Your (1/t)(1/t+1) is my 1/((n+1)*(n+2)). Your t/(t+1) is my F(n+1). So you've proved F(n)+1/((n+1)*(n+2))=F(n+1). Same thing. Sorry, I think the t was throwing me off.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook