• Support PF! Buy your school textbooks, materials and every day products Here!

Induction proof

  • Thread starter scottstapp
  • Start date
  • #1
40
0

Homework Statement


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)



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


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
 

Answers and Replies

  • #2
statdad
Homework Helper
1,495
35
Try decomposing

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

into partial fractions, and writing your original sum in terms of those partial fractions.
 
  • #3
40
0
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
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
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:
  • #5
40
0
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?
 
  • #6
Dick
Science Advisor
Homework Helper
26,258
618
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.
 

Related Threads on Induction proof

  • Last Post
Replies
6
Views
748
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
9
Views
949
  • Last Post
Replies
2
Views
807
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
1
Views
763
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
15
Views
3K
Top