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